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

Felipe Lessa wrote:

On Thu, May 1, 2008 at 9:44 AM, Felipe Lessa wrote:

...

On Thu, May 1, 2008 at 9:32 AM, Edsko de Vries 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.