[Haskell-cafe] Growing Trees

robert dockins robdockins at fastmail.fm
Thu Sep 22 16:48:49 EDT 2005

It sounds like you are porting an algorithm which does destructive 
updates on this tree.  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 

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).

You might consider:


Without knowing what you are doing with this tree its hard to be more 

Tom Hawkins wrote:

> I'm porting an ML program to Haskell, but am having difficulty with 
> particular data structure: a tree where each node has references to the 
> children as well as the parent...
> data Tree a
>   = TreeRoot { stuff    :: a
>              , children :: [Tree]
>              }
>   | TreeNode { stuff    :: a
>              , parent   :: Tree
>              , children :: [Tree]
>              }
> But because of these bidirectional links, every time I add a node I must 
> reconstructing the entire tree.  There is also the add coding complexity 
> of threading the tree through various functions to simulate state.
> What are my [monadic] options?
> -Tom
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list