Tom Hawkins wrote:
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.
What do you mean? The 'leaves' function itself cannot be made faster for it has to touch every leaf of the tree at least once. How large is your tree? But your tree could in reality be a DAG (directed acyclic graph), i.e. there are many shared subtrees. In this case, you'd have to fuse the tree generation and the tree destruction together. In the resulting function, you have a chance to exploit sharing. Here's an example with the fibonacci numbers: -- unfused fibtree 0 = Leaf 1 fibtree 1 = Leaf 1 fibtree n = Branch (fibtree (n-1)) (fibtree (n-2)) sumtree (Leaf x) = x sumtree (Branch x y) = sumtree x + sumtree y fib = sumtree . fibtree Here, 'sumtree' is equivalent to your 'leaves' and it's impossible to speed 'fib' up by changing 'sumtree' alone. Fusing the concatenation by equational reasoning yields fib' 0 = sumtree (fibtree 0) = sumtree (Leaf 1) = 1 fib' 1 = sumtree (fibtree 1) = sumtree (Leaf 1) = 1 fib' n = sumtree (fibtree n) = sumtree $ Branch (fibtree (n-1)) (fibtree (n-2)) = (sumtree $ fibtree (n-1)) + (sumtree $ fibtree (n-2)) = fib' (n-1) + fib' (n-2) Now, you can optimize the result by memoizing fib'. Regards, apfelmus