[Haskell-cafe] Tree Semantics and efficiency

[Antoine Latter]

On Wed, Jun 17, 2009 at 9:24 AM, Miguel Mitrofanov<miguelimo38 at 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