Alternatively, the definition of your tree could include a list of linked lists, one for each level of the tree. Then you could just select the last list and it's the same as saving only the leaves from a complete inorder walk of the tree.
data AltTree a = AltTree { tree_structure :: Tree a, nodes :: [[a]] } On Wednesday 21 February 2007 14:31, Tom Hawkins wrote: > Hello, > > Any recommendations for speeding up extracting the set of leaves from a > tree? > > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > > My slow, naive function: > > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) > > In my case, many of the branches in the tree are the same. I suspect > the fixed point operation mentioned in the thread "speeding up > fibonacci with memoizing" is applicable, but I'm having a tough time > making the connection. > > -Tom > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe