haskell - 这个质数函数实际上是如何工作的？

Question

取自Haskell的主页https://www.haskell.org/

primes = filterPrime [2..] 
  where filterPrime (p:xs) = 
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

看了这个函数几分钟后，我意识到我不太明白这个函数实际上在做什么，我想知道发生了什么。

但首先，这就是我认为正在发生的事情:

由于惰性求值，每次迭代中仅采用列表理解中的一个成员...如下所示:

第一次迭代

2 : filterPrime [x | x <- [3..], x `mod` p /= 0]

第二次迭代

2 : 3 : filterPrime [x | x <- [4..], x `mod` p /= 0]

第三次迭代

??? :(

Answer 1

第一个是直接从 [2..] 中形成模式匹配 p:xs - 所以它是 p = 2 并且xs 一些重击

接下来需要评估xs，因此它需要评估

[ x | x <- [3..], x `mod` 2 /= 0 ]

将以 x = 3 开头(这对于过滤器来说是可以的) - 所以你现在有了 p:xs (记住 filterPrime 的递归定义)也带有 p=3，但这次 xs 已经针对 `mod` 2/= 0 进行了过滤，现在将也会过滤 3 - 这将对每个找到的素数进行 - 每次您只会查看不是到目前为止所有找到的素数倍数的剩余数字。

你看它有点像 sieve of eratosthenes我想它也这么叫(但有some objections)