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 http://en.wikibooks.org/wiki/Haskell/Zippers 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. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com