[Haskell-cafe] Re: Leaves of a Tree

Chad Scherrer chad.scherrer at gmail.com
Thu Feb 22 00:57:03 EST 2007

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:


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


More information about the Haskell-Cafe mailing list