[Haskell-cafe] Re: simple function: stack overflow in hugs vsnonein ghc

[apfelmus]

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?

Regards,
apfelmus