Wadler space leak

[Simon Marlow]

On 28/10/2010 14:21, Bertram Felgenhauer wrote:
> Hi,
>
>>    let (first,rest) = break (const False) input
>>    in
>>    print (length (first ++ rest))
>>
>> When I compile this program using -O2 and use a large text file as
>> input the code runs in constant space. If I understand correctly,
>> the program runs in constant space because ghc uses an optimization
>> similar to the one proposed by Wadler/Sparud.
>
> Right. The optimization works by producing special thunks for tuple
> selectors which the garbage collector can recognize and evaluate
> during GC.
>
> However the implementation in GHC is quite brittle. See
>
>      http://hackage.haskell.org/trac/ghc/ticket/2607
>
> I suspect your program is another instance of this behaviour.
>
>> If I define the following function which is based on break
>>
>>    splitBy :: (a ->  Bool) ->  [a] ->  [[a]]
>>    splitBy _ []  = []
>>    splitBy p xs  =
>>      l : case ys of
>>               []   ->  []
>>               _:zs ->  splitBy' p zs
>>      where
>>        (l,ys) = break p xs
>
> I haven't looked in detail; what follows is a guess of what
> ghc may be doing. It could be verified by looking at the
> generated core.
>
> The where-binding desugars to something like
>
>      let q = break p xs
>          ys = case q of (_, ys) ->  ys
>          l = case q of (l, _) ->  l
>      in  ...
>
> ys can be inlined into splitBy, producing
>
>      l : case (case q of (l, ys) ->  ys) of
>               []   ->  []
>               _:zs ->  splitBy' p zs
>
>      l : case q of (l, ys) ->  case ys of
>               []   ->  []
>               _:zs ->  splitBy' p zs
>
> and now the tuple selector is no longer recognizable.

Yes, that's exactly what happens.

Cheers,
	Simon