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 <[EMAIL PROTECTED]> wrote: > >> On Thu, May 1, 2008 at 9:32 AM, Edsko de Vries <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
