Re: [Haskell-cafe] Tree Semantics and efficiency
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 jake.mcart...@gmail.comwrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tree Semantics and efficiency
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
Re: [Haskell-cafe] Tree Semantics and efficiency
On Wed, Jun 17, 2009 at 9:24 AM, Miguel Mitrofanovmiguelim...@yandex.ru wrote: 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-Tree-Zipper.html 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tree Semantics and efficiency
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
