[Haskell-beginners] Re: Fast tree manipulation
apfelmus at quantentunnel.de
Thu Feb 4 05:26:36 EST 2010
> 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.
More information about the Beginners