我用 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)
我觉得很好奇。发生这种情况有什么特别的原因吗?
最佳答案
当你说
primes :: [Integer]
然后 primes
是一个常数,但是当你说
primes :: (Integral a) => [a]
然后它是一个带有隐藏参数的函数:Integral
实例,无论是 a
是什么类型。与其他函数一样,当您使用相同的参数调用它时,它会重新计算其结果(除非您已明确记住它)。
关于haskell - 根据类型的具体性重建惰性列表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14903425/