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

[Derek Elkins]

On Fri, 2008-05-02 at 00:10 +0400, Daniil Elovkov wrote:
> Felipe Lessa wrote:
> > 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.
> > 
> 
> I think that consuming heap instead of stack is the best we can do.
> 
> I may be wrong, but it seems to be more or less impossible to traverse a 
> tree in constant memory. Well, if the tree structure doesn't have back 
> links (apart from left, right).
> 
> The thing is we have to remember nodes to return and remember if we went 
> to the left or to the right. The left or right biased tree is just a 
> list-like structure, where we don't have to remember anything, we can 
> just proceed. That's why it easy to traverse them in constant memory.
> 
> Maybe, in a C program we could traverse a tree without back links in 
> constant memory by XORing pointers and left-right booleans. That would 
> employ the property of xor that (a xor b) xor a = b. But I'm not sure.
> 
> Well, anyway, that's not about Haskell.

http://www.cs.indiana.edu/~jsobel/Recycling/recycling.html