Alternatively, the definition of your tree could include a list of linked lists, one for each level of the tree. Then you could just select the last list and it's the same as saving only the leaves from a complete inorder walk of the tree. data AltTree a = AltTree { tree_structure :: Tree a, nodes :: [[a]] } On Wednesday 21 February 2007 14:31, Tom Hawkins wrote:

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.

-Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

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