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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
