-1

我发现很难理解 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
4

2 回答 2

7

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.

于 2018-12-06T04:30:22.663 回答
4

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

正如您的代码所示，它打印出前 100000 个素数，那么如何primes工作？

首先，生成第一个素数很简单，就是列表的第一个元素：

2 : filter ((==1) ...

也就是说2，对于下一个，我们需要将primeFactors函数应用为

primeFactors 3 = factor 3 primes

现在可能会让刚接触 Haskell 的人感到困惑，如何评估primes上面的表达式？答案是，它只是一个包含 as 元素的列表[2,...]，由于惰性评估，现在我们不需要评估primes函数生成的列表的所有素数。我们只需要评估下一个，看看会发生什么。所以，我们得到2，上面的表达式变成：

 primeFactors 3 = factor 3 [2,..]

和

factor 3 (2:ps) | 2 * 2 > 3 = [3]

所以，primeFactors 3重新运行[3]

所以

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

我们现在成功地生成了 2 个素数，但是我们需要 100000，接下来呢？显然，我们适用5于以下表达式：

2: filter ((==1) . length . primeFactors) 5

重复上述过程：

primeFactors 5 = factor 5 [2,3,..]

这次我们在列表中有 2 个元素：

factor 5 [2,3..]

和

factor 5 [2,3..] | otherwise = factor 5 [3,...]

和

factor 5 [3,...] | 3 * 3 > 5 = [5]

并一次又一次地重复直到生成 100000 个素数，再一次，由于惰性计算，我们不需要 100001 个素数，所以计算停止并打印出结果。

于 2018-12-06T05:01:41.023 回答