lazy list reconstructed based on concreteness of its type?

Question

I wrote a simple (and unserious) prime number generator in Haskell, with mutually-recursive definitions for generating the primes and for determining the primeness of a number:

primes :: (Integral a) => [a]
primes = 2 : filter isPrime [3, 5..]

isPrime :: (Integral a) => a -> Bool
isPrime m = all (indiv m) (takeWhile (<= (intSqrt m)) primes)

intSqrt :: (Integral a) => a -> a
intSqrt 1 = 1
intSqrt n = div (m + (div (n - 1) m)) 2
  where m = intSqrt (n - 1)

indiv :: (Integral a) => a -> a -> Bool
indiv m n = rem m n /= 0

I noticed that it seems to reconstruct the sublist of already-generated primes with every reference to primes:

*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.70 secs, 446142856 bytes)
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.49 secs, 445803544 bytes)

But when I change the type annotations to use a concrete integral type, such as

primes :: [Integer]
isPrime :: Integer -> Bool

each prime is only generated once:

*Main> :r
[1 of 1] Compiling Main             ( Primes.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(2.15 secs, 378377848 bytes)
*Main> take 200 primes
[2,3,5,7, ..., 1223]
(0.01 secs, 1626984 bytes)

Seems curious to me. Any particular reason this is happening?

Answer 1

When you say

primes :: [Integer]

then primes is a constant, but when you say

primes :: (Integral a) => [a]

then it is a function with a hidden parameter: the Integral instance for whichever type a is. And like other functions, it will recompute its results when you call it with the same parameters (unless you've explicitly memoised it).