[Haskell-cafe] Leaves of a Tree

Tom Hawkins tomahawkins at gmail.com
Wed Feb 21 14:31:48 EST 2007


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.


More information about the Haskell-Cafe mailing list