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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
