Re: [Haskell-cafe] Leaves of a Tree

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