使用递归和列表推导式生成素数

Question

我是Haskell编程的新手，对下面的列表推导式扩展有困难。

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

请问有人能帮我纠正一下如何使用筛法扩展的方法吗：

• 当我们在 sieve 中进行模式匹配时，p 将与 2 和来自 [3..] 的 x 相关联。
• 接下来，在列表推导中，x<-3，但是当没有短路时，我们如何仅使用 3 调用筛法。

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

如果可以一步一步地扩展前几个数字，比如到 5，那么我认为会更清楚。

- Rohit Sharma

---

可能是帮助解释这段输出质数流的Haskell代码的重复问题。 - Mihai Maruseac

不，这不是重复的，请再次阅读我的问题。 - Rohit Sharma

如果您将所有内容内联到一个函数中，并将列表理解式中的保护条件翻译为“filter”，那么它就会起作用。 - Mihai Maruseac

Answer 1

让我们进行一些等式推理。

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]

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

- Mihai Maruseac

Answer 2

以下是关于 sieve 的操作描述：

计算 sieve (x:xs):

1. 输出第一个元素 x。
2. 从尾部的 xs 中，让 ys 成为一个列表，其中所有 x 的倍数都已被删除。
3. 为了生成下一个元素，在步骤2中定义的 ys 上递归调用 sieve。

以下是前几个术语的计算方法：

sieve [2..]
  = sieve (2:[3..])              -- x = 2, xs = [3..]
  = 2 : sieve ys
      where ys = [3..] with all of the multiples of 2 removed
               = [3,5,7,9,...]
  = 2 : sieve [3,5,7,9,...]

然后：

sieve [3,5,7,9,...]              -- x = 3, xs = [5,7,9,11,...]
  = 3 : sieve ys
      where ys = [5,7,9,11,13,15,17,...] with all of the multiples of 3 removed
               = [5,7,  11,13,   17,...]
  = 3 : sieve [5,7,11,13,17,...]

然后：

sieve [5,7,11,13,17,...]         -- x = 5, xs = [7,11,13,17..]
  = 5 : sieve ys
      where ys = [7, 11,13, 17,19,...]  with all of the multiples of 5 removed
               = [7, 11,13, 17,19,...]  (the first one will be 25, then 35,...)
  = 5 : sieve [7,11,13,17,19,...]

etc.

- ErikR

Answer 3

使用辅助函数

transform (p:xs) = [x | x <- xs, mod x p /= 0]
                 = filter (\x-> mod x p /= 0) xs  -- remove all multiples of p
                 = xs >>= noMult p                -- feed xs through a tester
-- where
noMult p x = [x | rem x p > 0]      -- keep x if not multiple of p

我们可以将sieve函数重写为：

       .=================================================+
       |                                                 |
       |  sieve input =                                  |
       |                  .===========================+  |
       |                  |                           |  |
 <~~~~~~~~~~ head input : | sieve (transform input )  |  |
       |                  |                           |  |
       |                  \___________________________|  |
       |                                                 |
       \_________________________________________________|

在命令式伪代码中，我们可以这样写：

sieve input =
    while (True) :
        yield (head input)           -- wait until it's yanked, and then
        input := transform input     -- advance and loop

这种重复应用的模式被称为迭代：

iterate f x = loop x
  where
    loop x = x : loop (f x)   -- [x, a:=f x, b:=f a, c:=f b, ...]

所以

sieve xs = map head ( iterate transform xs )

自然地，每个步骤中转换序列的头元素都将是质数，因为我们已经在之前的步骤中删除了所有前面质数的倍数。

Haskell是惰性的，所以变换不会在每个步骤上完全完成，远非如此——只有需要完成尽可能多的工作。这意味着只产生第一个元素，并“发出通知”在需要时进一步执行转换：

<--  2 ---<    [2..]
<--  3 ---<    [3..] >>= noMult 2 
<--  5 ---<   ([4..] >>= noMult 2) >>= noMult 3 
<--  7 ---<  (([6..] >>= noMult 2) >>= noMult 3) >>= noMult 5
<-- 11 ---< ((([8..] >>= noMult 2) >>= noMult 3) >>= noMult 5) >>= noMult 7
            ...............

---

顺便提一下，这应该给我们一个思路：3不需要由2进行测试；4..8不需要由3进行测试，更不用说5或7了；9..24不应该由5进行测试。我们想要的是：

<-- 2
<-- 3         --<  2(4),    [3..]
<-- 5,7       --<  3(9),    [4..]  >>= noMult 2 
<-- 11,...,23 --<  5(25),  ([9..]  >>= noMult 2) >>= noMult 3 
<-- 29,...,47 --<  7(49), (([25..] >>= noMult 2) >>= noMult 3) >>= noMult 5
                   ......................

即，我们希望每个>>= noMult p过滤器的创建被推迟，直到输入达到p*p。

- Will Ness