[Haskell-cafe] Re: Leaves of a Tree

[apfelmus at quantentunnel.de]

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