robert dockins wrote:
It sounds like you are porting an algorithm which does destructive updates on this tree.
Yes, "parent" and "children" were mutable fields.
If so, you can use the ST (or IO) monad and use STRef (IORef).
data Tree a = TreeRoot { stuff :: STRef a , children :: STRef [Tree] } .....
you would get at the data like so:
doStuff node = do s <- readSTRef (sutff node) children <- readSTRef (children node) ..... writeSTRef (children node) newChildren
This is probably the most direct translation from a destructive update setting.
As you said, having the upward pointers causes the entire tree to be recomputed when you make a change. If you want to move to a pure data structure with good sharing properties you will need to remove the upward pointers, at which point you have a pretty basic rose tree. (I suppose you could remove the downward pointers instead, but you'd have a very strange kind of tree; really, it would be a collection of lists with a common tail element).
Actually, using upward pointers would get me close. Most of the additions to the tree are new leaves or sub-branches -- updates that could be done in O(n) with the number of leaves. However, sometimes a new root node is planted at the top, which would cause the whole tree to be rebuilt. The other sticking point is that new "stuff" is added to the nodes every now and then. BTW, information is only added to the tree; it's never removed. Only after the entire tree is built, do I start querying the tree for information. If I can find a convenient data structure to absorb the initial tree growth (ie, new leaves, roots, and "stuff"), I can convert this tree into another structure with bidirectional links, making the tree traversals easier for queries. -Tom