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 _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users