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