[Haskell-cafe] Re: Leaves of a Tree

[Tom Hawkins]

On 2/21/07, Chad Scherrer <chad.scherrer at gmail.com> wrote:
> Tom,
>
> I think inserting elements would be a lot faster than multiple unions.
> I would try:
>
> leafList :: Tree -> [Int]
> leafList (Leaf n) = [n]
> leafList (Branch left right) = leafList left ++ leafList right
>
> leaves = fromList . leafList
>
> If you're writing many functions on Trees (or maybe even if you're
> not), you might consider writing a fold function and putting leafList
> in terms of this. Do you have experience with folds?

Folding was my first approach:

leaves :: Tree -> Set Int
leaves tree = accumLeaves Set.empty tree

accumLeaves :: Set Int -> Tree -> Set Int
accumLeaves set (Leaf n) = insert n set
accumLeaves set (Branch l r) = foldl accumLeaves set [l,r]

However, with this approach I quickly ran out of stack space.  I found
this odd, since I thought this program was tail recursive and
shouldn't be using the stack.

My next attempt was to use some form of memorization.  Since many of
the branches in my trees are equal, memorization should prevent
following branches that have already been calculated.  My question is,
what is the best way to transform the original function to incorporate
memorization?

-Tom

> >
> > 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
>