[Haskell-cafe] Leaves of a Tree

Donald Bruce Stewart dons at cse.unsw.edu.au
Wed Feb 21 17:58:00 EST 2007

> 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.

Also, just check the strictness on the traversal function. 

A slightly different tree here might give some hints,


-- Don

More information about the Haskell-Cafe mailing list