[Haskell-cafe] Re: simple function: stack overflow in hugs vsnonein
apfelmus at quantentunnel.de
Mon Sep 24 12:00:39 EDT 2007
Claus Reinke wrote:
>> the given example is too strict, the requirement is to generate the
>> matched portion lazilly, and return the tail (unconsumed portion).
> ah yes, without optimisations, Prelude.span builds up stack,
I don't quite understand why it does so at all.
span p  = (,)
span p xs@(x:xs')
| p x = let (ys,zs) = span p xs' in (x:ys,zs)
| otherwise = (,xs)
I mean, the third line can return a tuple and the first element of the
first list immediately. Where does the stack space come from?
True enough, the second component will be a tower
snd (_, snd (_, snd (_, ...
but snd is tail recursive.
>> In principle the function should be capable of being written to run in
>> constant space which the given example dose not.
Btw, even with the space leak prevention from the Sparud paper, it will
be a linear chain of indirections. So, span doesn't run in constant
space at all!
The problem is that when lazily deconstructing the first component, the
second component has to be "deconstructed", too (reduced partially) or
it will leak space. I mean, fetching the x from
(x:ys, id zs)
should reduce the id , too. Of course, that should be up to the
programmer's choice (partial reduction may be expensive), so is there a
way to specify that in code?
More information about the Haskell-Cafe