[Haskell-beginners] Memory leak after going from type Integer to Int

[Andreas Lemke]

Hi everyone,

I wrote a simple program that returns the n-th prime number when given n as
its command-line argument:

  import System.Environment

  isPrime n | n < 2  = False
            | n == 2 = True
            | otherwise = not $ any (`divides` n) dividerList
            where a `divides` b = b `mod` a == 0
                  dividerList = 2:[3, 5 .. floor $ sqrt $ fromIntegral n]

  primes = filter isPrime [1 ..]

  main = do
    [arg] <- getArgs
    print $ primes !! (read arg)

I compiled it with "ghc -O2". As expected, it runs in constant space, i. e.
space complexity O(1). Then, I added the declaration: "primes :: [Int]",
expecting a performance improvement. Runtime was indeed reduced by about
50%. However, it no longer runs in constant space. Memory usage rises
significantly for arguments > 1e5.

I tried all sorts of strictness annotations, which did not help. Turning on
profiling with "ghc -O2 -prof -auto-all" made the problem disappear, so I
could not analyze the memory leak using the profiler.  Only if I remove the
cases "n < 2" and "n == 2" from the definition of isPrime, does the program
run in constant space with type Int. If I replace the guards by an if
statement or pattern matching, the problem remains.

I have no idea how to continue from here. Can anyone explain why going from
type Integer to Int causes a different space complexity? How would I have to
change the program to get it to run in constant space with type Int?

I used ghc 7.4.1.

Regards,

Andreas