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