[Haskell-cafe] Leaves of a Tree

[Donald Bruce Stewart]

tomahawkins:
> 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,

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=binarytrees&lang=ghc&id=3

-- Don