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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe