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