Neil,
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 []
where
f rest (Leaf n) = n : rest
f rest (Branch l r) = f (f rest r) l
-Chad
-------------------------------
(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 []
where
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.
Thanks
Neil
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
