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
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
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
On 9/22/05, Tom Hawkins
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?
You can't do trees with mutable references in Haskell without doing it a state monad (ST, or IO, basically). However, it is possible to use laziness in order to have bidirectional "links", but doing so is kinda tedious (you can't pattern match on one constructor, you need to pattern match against two "levels" so you can construct the parent and the child at the same time). Here's a binary tree I threw together just now (not thouroughly tested!) where each node has a link to its parent. Note how laziness is used to make the parent refer to the child and the child refer to the parent. Some code could be saved by stating that a Root is just a Node with a Nil parent, but I didn't want to complicate it too much. ----------- data TreeParent a = Root a (TreeParent a) (TreeParent a) | Node a (TreeParent a) (TreeParent a) (TreeParent a) | Nil insert :: Ord a => TreeParent a -> a -> TreeParent a insert (Root a Nil Nil) k = parent where parent | k < a = Root a child Nil | otherwise = Root a Nil child child = Node k parent Nil Nil insert (Root a Nil t2) k | k < a = parent | otherwise = Root a Nil (insert t2 k) where parent = Root a child t2 child = Node k parent Nil Nil insert (Root a t1 Nil ) k | k < a = Root a (insert t1 k) Nil | otherwise = parent where parent = Root a t1 child child = Node k parent Nil Nil insert (Root a t1 t2) k | k < a = Root a (insert t1 k) t2 | otherwise = Root a t1 (insert t2 k) insert (Node a p Nil Nil) k = parent where parent | k < a = Node a p child Nil | otherwise = Node a p Nil child child = Node k parent Nil Nil insert (Node a p Nil t2) k | k < a = parent | otherwise = Node a p Nil (insert t2 k) where parent = Node a p child t2 child = Node k parent Nil Nil insert (Node a p t1 Nil ) k | k < a = Node a p (insert t1 k) Nil | otherwise = parent where parent = Node a p t1 child child = Node k parent Nil Nil insert (Node a p t1 t2) k | k < a = Node a p (insert t1 k) t2 | otherwise = Node a p t1 (insert t2 k) insert Nil k = Root k Nil Nil toList Nil = [] toList (Node a _ t1 t2) = toList t1 ++ [a] ++ toList t2 toList (Root a t1 t2) = toList t1 ++ [a] ++ toList t2 ----------- /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
[Previously sent only to the OP -- oops] Tom Hawkins wrote:
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.
If you don't want to use IORefs or STRefs, you could try The Zipper: http://www.haskell.org/hawiki/TheZipper or you could represent the tree as type Tree a = Data.Map.Map Int (Node a) data Node a = TreeRoot { stuff :: a, children :: [Int] } | TreeNode { stuff :: a, parent :: Int, children :: [Int] } -- Ben
participants (4)
-
Ben Rudiak-Gould -
robert dockins -
Sebastian Sylvan -
Tom Hawkins