[Haskell-cafe] Re: Tree Guidance

[apfelmus]

Hans van Thiel wrote:
> Both CFP and SOE have chapters on trees and there is a standard library
> Data.Tree. I expected to find all kinds of functions there, as in
> Data.List, but instead the functions are defined as instances of more
> general structures.

Well, Data.Tree is not much in use since one almost always needs some
special kind of tree and because it's so easy to roll your own.

> import Control.Applicative (Applicative(..), (<$>))
> import Data.Foldable (Foldable(foldMap), toList)
> import Data.Traversable (Traversable(traverse))

The papers mentioned on the haddock for Data.Traversable are good start.
Basically, these concepts are a generalization of the good old "fold"
from lists to arbitrary trees (=> Foldable) and from pure functions to
general computations (=> Applicative Functors, Traversable).

> There is a Zipper

http://en.wikibooks.org/wiki/Haskell/Zippers

> Ideally I would want a N-ary tree, where the branches are what's
> actually the represented data, and so I would like to access it both
> from the root and the leaves. In an imperative language I would just add
> an up-pointer in each node, but I have no idea how expensive this would
> be in Haskell, or if it's necessary at all.

Up-pointers won't work in Haskell, you'll need a different approach. Can
you elaborate on what your tree looks like and what it stores?

Regards,
apfelmus