haskell - 具有递归和列表理解的素数生成器

我是Haskell编程的新手，无法理解以下列表理解的扩展方式。

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

有人可以纠正我sieve扩展的工作原理:

由于我们在sieve中进行模式匹配，因此p将与2中的x和[3..]关联。

接下来，在列表中，了解x<-3，但是在没有短路的情况下，如何仅用3调用筛子。

我不明白的另一件事是递归在这里如何工作。

我认为很明显，如果可以一次扩展上述步骤的前几个数字，直到5。

最佳答案

让我们做一些方程式推理。

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

[2..]是[2, 3, 4, 5, ...]的语法糖，因此

primes = sieve [2, 3, 4, 5, 6, ...]

内联sieve一次:

primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]

首先，x获得值3，该值通过mod 2过滤器

primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])

再次内联sieve(我将x重命名为y以避免混淆)

primes = 2 : 3 : sieve [y | y <- [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0],
                            y `mod` 3 /= 0]

现在x = 4使mod 2过滤器失败，但x = 5通过了它。所以

primes = 2 : 3 : sieve [y | y <- 5 : [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0],
                            y `mod` 3 /= 0]

这个y = 5也通过了mod 3过滤器，所以我们现在有了

primes = 2 : 3 : sieve (5 : [y | y <- [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0],
                                 y `mod` 3 /= 0])

再扩展一次sieve(用z代替y)可以使我们

primes = 2 : 3 : 5 : sieve [z | z <- [y | y <- [x | x <- [6, 7, 8, ...],
                                                    x `mod` 2 /= 0],
                                          y `mod` 3 /= 0],
                                z `mod` 5 /= 0]

并且扩展以相同的方式继续进行。