[Haskell-cafe] Re: Leaves of a Tree

Chad Scherrer chad.scherrer at gmail.com
Wed Feb 21 18:07:58 EST 2007


I think inserting elements would be a lot faster than multiple unions.
I would try:

leafList :: Tree -> [Int]
leafList (Leaf n) = [n]
leafList (Branch left right) = leafList left ++ leafList right

leaves = fromList . leafList

If you're writing many functions on Trees (or maybe even if you're
not), you might consider writing a fold function and putting leafList
in terms of this. Do you have experience with folds?


> 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

More information about the Haskell-Cafe mailing list