haskell - 根据类型的具体性重构惰性列表？

Question

我在 Haskell 中编写了一个简单（且不严重）的素数生成器，具有用于生成素数和确定数字的素数的相互递归定义：

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

我注意到它似乎在每次引用时都重建了已经生成的素数的子列表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)

但是当我将类型注释更改为使用具体的整数类型时，例如

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

每个素数只生成一次：

*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)

对我来说似乎很好奇。发生这种情况有什么特别的原因吗？

Answer 1

当你说

primes :: [Integer]

thenprimes是一个常数，但是当你说

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

那么它是一个带有隐藏参数的函数：Integral无论哪种类型的实例a。和其他函数一样，当你用相同的参数调用它时，它会重新计算它的结果（除非你明确地记住了它）。