[Haskell-cafe] Re: Leaves of a Tree

[Chad Scherrer]

Hi Tom,

Tom Hawkins wrote:
> 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.

This is a problem of tail recursion and lazy evaluation not playing
nicely. See this page:

http://www.haskell.org/haskellwiki/Stack_overflow

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

I think something like this could be done, if there's some invariants
maintained by the data structure. Is there any additional structure
you're imposing beyond that required for the "data" line?

-Chad