# Space leak question

Tue Jul 26 10:57:54 CEST 2011

```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

```