Make lines stricter to fix a space leak

[Ian Lynagh]

On Fri, Sep 24, 2010 at 09:21:19PM +0200, Daniel Fischer wrote:
> Proposal: A stricter implementation of lines.
> 
> Reason: The current implementation causes a space leak (cf. 
> http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps), at least in GHC.
> 
> The proposed implementation fixes the leak at the small cost of being 
> stricter if the first _|_ in the String is the first character of a line.

I think this changes the definition from one that currently has a space
leak with GHC, to one which necessarily must have a space leak (as all
of l must be held in memory while we look for a newline).

IIRC GHC's GC does have an optimisation which I believe would apply
here, where it reduces essentially (snd (x, y)) in the heap to y, but
that that optimisation isn't always good enough (it has a threshold for
how deep it is willing to reduce, and a small loop like this will
generates pairs and selectors faster than the GC is willing to reduce
them).

I thought we had a ticket about that, but I can't find it now.

If that was fixed then we could have constant space usage.


Thanks
Ian