[Haskell-cafe] Growing Trees

[robert dockins]

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

You might consider:

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Tree.html


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


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