Hi,

I've been playing around with immutable data structures (at least, as 
immutable as one gets).

I came across an interesting algorithm for rebalancing a binary tree, 
invented by Day, Stout and Warren. It's an in-place pointer-swizzler 
that, with constant additional space, rebalances a tree in linear time. 
Of course, it operates on a mutable structure.

So I had an idea: I could "ringfence" the mutation: from my immutable 
structure, create a mutable copy, tear it to bits and then recreate a 
new, immutable, balanced, tree.

So I wrote, in addition to my ZTree node class, a MutableZTree subclass. 
It has the same shape as its parent (no new instvars), and a bunch of 
extra mutating methods.

There are some costs involved in this, of course: I create two entire 
copies of the tree. One, making the mutable copy, seems unavoidable: you 
cannot simply un-immutable the tree, because you have no idea what other 
objects might have a reference to parts of the tree, and they all assume 
the tree's immutable. The other, however... well, we don't care about 
references to the mutable structure because there should be no 
references to it. It's purely an internal, interim structure.

So I thought, well, wouldn't it be nice if one could _change the class_ 
of the MutableZTrees so they all magically turn into nice immutable ZTrees.

I'm sure there's some trickery one could do, but quite what that 
trickery would be, I'm not sure. Any ideas? (Or, just as importantly, 
good reasons why the above is completely insane?) It would be nice to 
turn the O(3n) space requirement into O(2n)...

frank