[Haskell-beginners] Re: Fast tree manipulation

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Feb 4 05:26:36 EST 2010

Gabi wrote:
> Maybe Data.Sequence is a good option. Seems to be designed to give
> good performance when mutating
> If trees could be represented using Data.Sequence, I think that tree
> manipulation performance would be bearable.
> Any other libraries that might be useful?

I don't see why you would want to use Data.Sequence for representing trees.

Trees are usually represented as

    data Tree a b = Leaf b | Branch a (Tree a b) (Tree a b)

While trees are persistent, they are also shared; "mutating" a tree will
only change a small part of it. And if you are doing a lot of local
operations, a zipper may help


In any case, I'd recommend to go ahead and use the simplest possible
representation of trees for a small prototype. If any performance
problems crop up, ask the list again.

Heinrich Apfelmus


More information about the Beginners mailing list