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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
