Tree Semantics and efficiency
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.
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
On Wed, Jun 17, 2009 at 9:24 AM, Miguel Mitrofanov
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.
The advantage zippers have over knot-tying is that I can create updates of zipper-viewed data structures. It looks like there's already something on HAckage for this: http://hackage.haskell.org/packages/archive/rosezipper/0.1/doc/html/Data-Tre... The idea is that you can use the following function to created the zipper-view of your tree:
fromTree :: Tree a -> TreeLoc a
and then use the functions on 'TreeLoc' types to traverse and modify the tree, and then call
toTree :: TreeLoc a -> Tree a
to go back to the 'Tree a' representation of your data. Antoine
Rouan van Dalen wrote:
It is important to store only a reference to the parent and not a copy of the entire parent for efficiency.
Others have already recommended the rosezipper package, which gives you what you want, but I want to address one thing. foo = <stuff> bar = foo In most implementations (including GHC, which I assume you are using), `bar` will *not* be an actual copy of `foo`. In fact, GHC will not make a deep copy of a structure unless you pattern match all the way down and reconstruct it all the way back up yourself. If you use a zipper, like Data.Tree.Zipper mentioned already, moving around will not create and destroy tons of data. It will only create and destroy the spine of the tree local to the current "pointer" into the tree, which is not a lot of data. If you are holding on to older versions of the zipper, of course, they won't even be destroyed. - Jake
Moreover, copying is not even meaningful in a functional setting. A data
structure is indistinguishable from a copy of the data structure. In
languages that allow mutation of data, one has to carefully copy data to
avoid accidental mutation by other computations. Disallow data mutation,
and the problem disappears.
- Conal
On Wed, Jun 17, 2009 at 7:44 AM, Jake McArthur
Rouan van Dalen wrote:
It is important to store only a reference to the parent and not a copy of the entire parent for efficiency.
Others have already recommended the rosezipper package, which gives you what you want, but I want to address one thing.
foo = <stuff> bar = foo
In most implementations (including GHC, which I assume you are using), `bar` will *not* be an actual copy of `foo`. In fact, GHC will not make a deep copy of a structure unless you pattern match all the way down and reconstruct it all the way back up yourself.
If you use a zipper, like Data.Tree.Zipper mentioned already, moving around will not create and destroy tons of data. It will only create and destroy the spine of the tree local to the current "pointer" into the tree, which is not a lot of data. If you are holding on to older versions of the zipper, of course, they won't even be destroyed.
- Jake
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (5)
-
Antoine Latter -
Conal Elliott -
Jake McArthur -
Miguel Mitrofanov -
Rouan van Dalen