Space leak question

[Bertram Felgenhauer]

Hi Will,
> in reformulation of a code with no space leak, the leak reappeares.
> 
> It takes near constant space to get at the n-th elt in the produced list here 
> (http://ideone.com/fiifl):
> 
>  {-# OPTIONS_GHC -O2 -fno-cse #-}
>  primes = 2 : ([3,5..] `minus`
>                 foldi (\(x:xs) -> (x:) . union xs)
>                       [[x*x, x*x+2*x..] | x<- ys])
>   where
>    ys = 3 : ([5,7..] `minus`
>                 foldi (\(x:xs) -> (x:) . union xs)
>                       [[x*x, x*x+2*x..] | x<- ys])
>    foldi f (x:xs)  = f x (foldi f (pairs f xs))
>    pairs f (x:y:t) = f x y : pairs f t
> 
> 
> Here it doesn't (http://ideone.com/m744a):
> 
>  {-# OPTIONS_GHC -O2 -fno-cse #-}
>  primes = 2 : g (fix g)
>   where
>    g = (3:) . ([5,7..] `minus`)
>             . foldi (\(x:xs) -> (x:) . union xs)
>             . map (\x-> [x*x, x*x+2*x..])

This is entirely expected. What is gobbling up the memory is the
shared [5,7..] list that some invocation of g consume while others
hang onto the head of the same list. (Note that g is a constant.)
If you change the code to make g pointful, and compile with
-fno-full-laziness, then the memory usage will go down again.

 {-# OPTIONS_GHC -O2 -fno-full-laziness #-}
 primes :: [Int]
 primes = 2 : g (fix g)
  where
   g xs = (3:) . ([5,7..] `minus`)
               . foldi (\(x:xs) -> (x:) . union xs)
               . map (\x-> [x*x, x*x+2*x..]) $ xs

With -ffull-laziness, ghc will notice that [5,7..] does not depend on
xs, and float it out to the surrounding scope, essentially turning the
code into

 {-# OPTIONS_GHC -O2 #-}
 primes :: [Int]
 primes = 2 : g (fix g)
  where
   g xs = (3:) . (odds `minus`)
               . foldi (\(x:xs) -> (x:) . union xs)
               . map (\x-> [x*x, x*x+2*x..]) $ xs
   odds = [5,7..]

and the [5,7..] list will be shared once more.

Using -fno-cse has no effect in this example, because there are no
duplicate subexpressions in the code. It is still a good idea to
try this option when one encounters odd space leaks.

Bertram