解释这个输出素数stream的haskell代码块

我无法理解这段代码：

let sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs) in sieve [2 .. ] 

有人可以为我分解吗？ 我知道有recursion，但这就是我不明白这个例子中的recursion如何工作的问题。

Answer 1

这其实很漂亮。

首先，我们定义一个函数sieve ，它包含一系列元素：

 sieve (p:xs) 

在sieve体中，我们将列表的头部（因为我们传递了无限列表[2..] ，2被定义为素数），并将其附加到sieve结果的剩余部分列表：

 p : sieve (filter (\ x -> x 'mod' p /= 0) xs) 

所以让我们来看看在其他列表中工作的代码：

 sieve (filter (\ x -> x 'mod' p /= 0) xs) 

我们正在sieve筛选列表。 让我们来分解一下filter的function：

 filter (\ x -> x 'mod' p /= 0) xs 

filter采用一个函数和一个我们应用该函数的列表，并保留满足函数给定条件的元素。 在这种情况下， filter需要一个匿名函数：

 \ x -> x 'mod' p /= 0 

这个匿名函数有一个参数x 。 它根据p检查x的模数 （列表的头部，每次调用sieve ）：

  x 'mod' p 

如果模数不等于0：

  'mod' p /= 0 

然后元素x保存在列表中。 如果它等于0，则被过滤掉。 这是有道理的：如果x是可以被p整除的，那么x就可以被1以上的整除，因此它不是素数。

Answer 2

与其他人在这里所说的相反，这个function并没有实现Eratosthenes的真正筛选 。 它确实返回了素数的初始序列，并且以类似的方式，所以可以把它想象成Eratosthenes的筛子。

当mipadi 发布他的答案时，我正在解释代码。 我可以删除它，但由于我花了一些时间，因为我们的答案不完全相同，所以我会把它留在这里。

---

首先，请注意，您发布的代码中存在一些语法错误。 正确的代码是，

 let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..] 

1. let x in y定义x并允许在y使用它的定义。 这个expression式的结果是y的结果。 所以在这种情况下，我们定义一个函数sieve并返回应用[2..] sieve 。

2. 现在让我们仔细看看这个expression式的部分：

    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) 

   1. 这定义了一个函数sieve ，它将第一个参数作为列表。
   2. (p:xs)是一个模式 ，它将p与所述列表的头部匹配， xs与尾部（除了头部之外的所有东西）匹配。
   3. 一般来说， p : xs是第一个元素是p的列表。 xs是包含其余元素的列表。 因此， sieve返回它收到的列表的第一个元素。

   4. 不要看清单的其余部分：

       sieve (filter (\x -> x `mod` p /= 0) xs) 

      1. 我们可以看到recursion调用sieve 。 因此， filterexpression式将返回一个列表。
      2. filter需要一个filter函数和一个列表。 它仅返回列表中filter函数返回true的那些元素。

      3. 在这种情况下， xs是被过滤的列表

          (\x -> x `mod` p /= 0) 

         是过滤function。

      4. filter函数接受一个参数x并返回true，如果它不是p的倍数。

3. 现在这个sieve已经定义好了，我们把它从[2 .. ] ，即从2开始的所有自然数列表传递给它。因此，

   1. 号码2将被退回。 所有其他自然数是2的倍数将被丢弃。
   2. 第二个数字是3.它将被返回。 3的所有其他倍数将被丢弃。
   3. 因此下一个数字将是5.等等

Answer 3

它定义了一个发生器 – 一个名为“筛”的stream变换器 ，

 Sieve s = while( True ): p := s.head s := s.tail yield p -- produce this s := Filter (notAMultipleOf p) s -- go next primes := Sieve (Nums 2) 

它使用一个等价的匿名函数的curryforms

 notAMultipleOf px = (mod xp) /= 0 

Sieve和Filter都是数据构造操作，内部状态和按值parameter passing语义。

---

在这里我们可以看到，这个代码最显着的问题 不是重复使用试划分来从工作序列中过滤掉倍数，而是可以直接找出它们，以p为增量进行计数 。 如果我们用后者replace前者，那么由此产生的代码将仍然具有极其糟糕的运行时复杂性。

不，最明显的问题是，它过早地将Filter放在其工作序列的顶部， 只有在input中看到素数的正方形之后才能真正做到这一点。 结果，它创build的Filter链太长 ，其中大部分根本就不需要。

修正后的版本，将filter创build推迟到适当的时刻

 Sieve ps s = while( True ): x := s.head s := s.tail yield x -- produce this p := ps.head q := p*p while( (s.head) < q ): yield (s.head) -- and these s := s.tail ps := ps.tail -- go next s := Filter (notAMultipleOf p) s primes := Sieve primes (Nums 2) 

或者在Haskell中 ，

 primes = sieve primes [2..] sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem xp /= 0] where (p:pt) = ps (h,t) = span (< p*p) xs 

rem在这里用来代替mod因为在某些解释器中它可以快得多，而且这里的数字都是正数。

通过将问题规模点n1,n2运行时间t1,t2作为logBase (n2/n1) (t2/t1) ，计算algorithm的局部增长顺序 ，我们得到第一个问题的O(n^2)一个，刚好在O(n^1.4)之上O(n^1.4)个产生的素数）。

---

只是为了澄清，缺失的部分可以用这个（虚构的）语言来定义

 Nums x = -- numbers from x while( True ): yield x x := x+1 Filter pred s = -- filter a stream by a predicate while( True ): if pred (s.head) then yield (s.head) s := s.tail 

另见 。

Answer 4

它正在实施Eratosthenes筛

基本上，从一个素数（2）开始，并从其余的整数中过滤出来，是所有倍数的两倍。 该筛选列表中的下一个数字也必须是素数，因此可以从剩余的数字中过滤所有倍数，依此类推。

Answer 5

它说：“某个列表的筛选是列表中的第一个元素（我们将称为p），并且筛选其余列表中的筛选，以便只允许通过p不能被p整除的元素”。 然后通过返回从2到无穷大的所有整数的筛子（其后是2，然后是不能被2整除的所有整数的筛子等等）来开始。

在攻击Haskell之前，我build议小Schemer 。