You can use the standart "tying the knot"-technique. For example:
data Tree = TreeNode String (Maybe Tree) [Tree] -- what's the parent of the
root node?
test :: Tree
test =
let parent = TreeNode "I'm parent" Nothing [child1, child2]
child1 = TreeNode "I'm child1" (Just parent) []
child2 = TreeNode "I'm child2" (Just parent) []
in parent
But there are other possibilities worth considering. Zippers, for example,
would be likely useful.
IORefs are most certainly an overkill.
Rouan van Dalen wrote on 17.06.2009 18:15:
Hi everyone.
I would like to confirm the following semantics.
I want a tree which can be traversed both downwards and upwards.
To do this i need to store the following for each node:
o) a reference to the parent node (so we can traverse up the tree). This must
be a reference as i dont want to copy the parent node each time)
o) a list of child nodes that belong to this node.
It is important to store only a reference to the parent and not a copy of the
entire parent for efficiency.
How would one write this in Haskell so that it has the above mentioned
semantics.
Or does GHC do that automatically for me so I don't need to do it explicitly?
I am thinking of writing something like this (naive implementation) :
Tree = TreeNode String Tree [Tree] -- TreeNode <data> <ParentReference>
<ChildNodes>
OR (implementation using IORef for parentNode reference)
Tree = TreeNode String (IORef Tree) [Tree] -- TreeNode <data>
<ParentReference> <ChildNodes>
Thanks in advance
Rouan.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
