Dear GHC team, I have observed a space leak in a simple program compiled with -O option. The problem is to compute the "Fibonacci rabbit sequence": [1,0,1,1,0,1,0,1,1,0,1,1,0,...] see e.g., this Haskell Cafe discussion: http://www.haskell.org/pipermail/haskell-cafe/2007-November/034236.html I like this problem because I studied the spectrum of the Schrodinger operator defined by this sequence a while ago. Anyway, here are two slightly different programs that compute the rabbit sequence: -- Version 1: O(n) time, O(n) space rs :: [Int] rs = 1: tail [x | r <- rs, x <- f r] where f 0 = [1] f 1 = [1,0] main :: IO () main = print $ take 100 rs -- Version 2: O(n) time, O(log n) space rs :: () -> [Int] rs () = 1: tail [x | r <- rs(), x <- f r] where f 0 = [1] f 1 = [1,0] -- test of memory usage main :: IO () main = print $ rs() !! (10^8) When the second program is compiled with -O flag (using GHC-6.10.4 or the latest version, 6.13.20091125), it eats up a lot of memory. After some web searching and experimentation, I found that the space leak can be fixed by compiling with -fno-full-laziness and inserting {-# NOINLINE rs #-} However, I still have a few of questions: 1) Why would inlining introduce a space leak? This looks like a compiler bug to me. 2) Is there a set of "safe" or, if this is a better word, "conservative" optimizations that never increase the running time or space usage more than by a constant factor? This leads to another question: relative to what? I understand that prescribing the exact evaluation order and other details would be impractical, but is it possible to define *some* aspects of the program behavior that would allow the programmer to guarantee the correct asymptotic efficiency? Thank you, Alexei Kitaev