[Haskell-cafe] Re: Understanding tail recursion and trees

[Felipe Lessa]

On Thu, May 1, 2008 at 9:44 AM, Felipe Lessa <felipe.lessa at gmail.com> wrote:
> On Thu, May 1, 2008 at 9:32 AM, Edsko de Vries <devriese at cs.tcd.ie> wrote:
>  >  So then the question becomes: what *is* the best way to write this function?
>
>  I guess it would be simpler to have the counter on the data type and a
>  smart branch constructor:

Under more careful analysis, it seems I just moved the stack overflow
from the counter function to the generator =). Modifying the data type
to

> data Tree = Leaf Integer | Branch !Integer Tree Tree

also won't work in this example (although it seems to fail earlier).
However, I'd expect the data type above to work nicely with most real
applications (that doesn't construct the entire tree in one go), such
as Data.Map[1].

But the answer to your original question really seems to be using an
explicit stack created in the heap. This technique is used in Data.Map
in a certain case[2] and, although has received a lot of attention on
a thread that sparked some time ago (I think it was [3]) for being
merely a workaround over the limited stack, it seems to me it's a
compulsory workaround for the time being when working with problems
like yours.

HTH,

[1] http://haskell.org/ghc/docs/latest/html/libraries/containers/src/Data-Map.html#Map
[2] http://haskell.org/ghc/docs/latest/html/libraries/containers/src/Data-Map.html#fromDistinctAscList
[3] http://www.haskell.org/pipermail/haskell-cafe/2008-February/039104.html

-- 
Felipe.