On Sun, 1 May 2011, Frank Shearar wrote:

> Ah, that might be exactly the hammer I'm looking for. Thanks!
>
> I don't want to add the balancing protocol to ZTree because then I'm allowing 
> the mutation of a ZTree, which means that clients of ZTree can't assume that 
> it's immutable.
>
> Well. To be picky, ZTree _does_ have the balancing protocol, in the sense 
> that it responds to #balance. The implementation of #balance, however, makes 
> a MutableZTree copy, balances that, and returns an immutable version of the 
> newly balanced tree. ZTree just doesn't permit the necessary mutating like 
> setting a subtree and the like. ("Necessary" because the DSW algorithm makes 
> extensive use of mutation.)

You shouldn't be that strict IMHO. You can mutate the state of the nodes 
as long as it has no side effects. So if you copy all nodes, then you can 
freely mutate the state of them before giving any of them to the user.

If you want to create efficient immutable data structures in smalltalk 
then you should use different techniques than with modern functional 
programming languages. For example smalltalk VMs won't detect that you 
created a copy of something that won't be used anymore, therefore you 
should avoid creating such copies.

If you don't want to expose state mutating methods to the user, then 
you can use separate tree and node objects, like I did with LLRBT, which 
is a persistent balanced binary tree implementation. An old version is 
available at http://leves.web.elte.hu/squeak/LLRBT-ul.7.mcz . It has 
LLRBTree which is the class for the tree object and there are two classes 
for nodes, LLRBTreeNode and LLRBExtremalTreeNode.
Users only have direct access to tree objects in this case.


Levente

>
> frank
>
>