[Haskell-cafe] Re: Leaves of a Tree

Chad Scherrer chad.scherrer at gmail.com
Wed Feb 21 22:07:54 EST 2007


I think this idea is better than what I had suggested, but as it
stands it doesn't typecheck. Did you mean something like this?

leaves :: Tree -> [Int]
leaves = f []
      f rest (Leaf n) = n : rest
      f rest (Branch l r) = f (f rest r) l

(from Neil Mitchell)

Hi Tom

> 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 mailing list