[Haskell-cafe] Leaves of a Tree
ndmitchell at gmail.com
Wed Feb 21 18:49:47 EST 2007
> data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord)
> leaves :: Tree -> Set Int
> leaves (Leaf n) = singleton n
> leaves (Branch left right) = union (leaves left) (leaves right)
The standard method for a traversal over leaves with accumulation is:
leaves :: Tree -> Set Int
leaves x = f 
f (Leaf n) rest = n : rest
f (Branch l r) rest = f l (f r rest)
This makes the construction of the list quite cheap.
Then you can do the fromList trick, and that might give you a speed up.
More information about the Haskell-Cafe