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