[Haskell-cafe] Re: Understanding tail recursion and trees
derek.a.elkins at gmail.com
Fri May 2 01:12:19 EDT 2008
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.
> > 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 and, although has received a lot of attention on
> > a thread that sparked some time ago (I think it was ) 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.
More information about the Haskell-Cafe