Haskell如何评估这个素数函数？

Question

我发现很难理解Haskell如何评估这个primes函数.是的primes功能得到评估一遍又一遍,或primes在primeFactors功能将指向回到第一primes？

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps)
        | p * p > n        = [n]
        | n `mod` p == 0   = p : factor (n `div` p) (p:ps)
        | otherwise        = factor n ps

main :: IO ()
main = print $ length . take 100000 $ primes

Answer 1

primes只是一个清单.它的第一个元素是2,其余元素取自由函数(部分)过滤的奇数整数列表primeFactors.

primeFactors但是,使用primes.这不是通告吗？

不完全的.因为Haskell是惰性的,primeFactors所以不需要同时使用所有值primes,只需要小于或等于其参数的平方根(p:ps匹配primes,但我们只需要psif p*p <= n),并且这些素数都是由之前的电话primeFactors.

举个例子,跟踪前几个调用primeFactors.为简洁起见,让我们b = (==1) . length . primeFactors.

primeFactors 3 == factor 3 primes
               -- only unpack as much of primes as we need for the next step
               == factor 3 (2:filter b [3,5..])
               -- because 2*2 > 3, that's only one level
               == [3]

因此,b [3]既然如此,我们知道3是下一个元素primes.那是,primes = 2:3:filter b [5,7..]

primeFactors 5 == factor 5 primes
               == factor 5 (2:3:filter b [3,5..])
               -- 2*2 > 5 is false, as is 5 `mod` 2 == 0, so
               == factor 5 (3:filter b [3,5..])
               -- 3*3 > 5, so
               == [5]

而且b [5]是真实的,所以5是下一个元素primes.

primeFactors 7 == factor 7 primes
               == factor 7 (2:3:5:filter b [3,5..])
               == factor 7 (3:5:filter b [3,5..])
               -- 3*3 > 7
               == [7]

而且b [7]是真实的,所以7是下一个元素primes.(似乎所有东西都被添加到了primes,不是吗？还有一个电话primeFactors会显示不是这样)

primeFactors 9 == factor 9 primes
               == factor 9 (2:3:5:7:filter b [3,5..])
               -- 2*2 > 9 and 9 `mod` 2 == 0 are false
               == factor 9 (3:5:7:filter b [3,5..])
               -- 3*3 > 9 is false, but 9 `mod` 3 == 0 is true, so
               == 3 : factor (9 `div` 3) (3:5:7:filter b [3,5..])
               == 3 : factor 3 (3:5:7:filter b [3,5..])
               -- 3*3 > 3 is false, but 3 `mod` 3 == 0, so
               == 3 : [3] == [3,3]

但既然b [3,3]是假的,9是不是的元素primes.所以现在我们有了

 primes = 2:3:5:7:filter b [3,5..])

追踪这个过程是一个漫长而乏味的过程,但你应该感觉primes始终保持"领先" primeFactors; primes这些primeFactors需求的要素总是由早先的呼吁决定primeFactors.