[Haskell-cafe] Growing Trees

[Tom Hawkins]

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