[Haskell-cafe] Tree Semantics and efficiency

Jake McArthur jake.mcarthur at gmail.com
Wed Jun 17 10:44:14 EDT 2009


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


More information about the Haskell-Cafe mailing list