解释这段输出素数流的haskell代码

Question

解释这段输出素数流的haskell代码我很难理解这段代码：let   sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)in sieve [2 .. ]有人可以为我分解吗？我知道其中存在递归，但这就是我无法理解此示例中的递归如何工作的问题。

Answer 1

它定义了一个生成器- 一个称为“ sieve”的流转换器，

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

它使用等效于匿名函数的咖喱形式

nomultsof p x = (mod x p) /= 0

两个Sieve和Filter是数据构造与操作的内部状态和通过值参数传递语义。

---

在这里，我们可以看到，最突出的问题这段代码是不是，重复不在于它使用审判庭从工作序列筛选出数倍，而它可以直接将它们找出来，通过在增量计数p。如果我们要用后者代替前者，那么生成的代码将仍然具有极高的运行时复杂性。

不，它最明显的问题是它过早地将其Filter放在工作序列的顶部，只有在输入中看到素数平方之后才真正应该这样做。结果，与实际需要的相比，它创建了s 的二次数。它创建的s 链太长，甚至根本不需要它们中的大多数。FilterFilter

过滤器的创建被推迟到适当的时候的更正版本是

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 (nomultsof p) s

primes := Sieve primes (Nums 2)

或在Haskell中，

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

rem此处使用而不是，mod因为在某些口译员中它可以更快，并且无论如何这些数字都是正数。

通过以问题大小点的运行时间来衡量算法的局部增长阶次，如，我们得到第一个，而第二个正好在上面（以产生的素数计）。t1,t2n1,n2logBase (n2/n1) (t2/t1)O(n^2)O(n^1.4)n

---

只是为了澄清一下，可以用这种（虚构的）语言定义缺少的部分，就像

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

另见。

---

更新：奇怪的是，根据AJT Davie在1992年Haskell的书中，David Turner的1976 SASL手册中的第一个代码实例，

    primes = sieve [2..]

    sieve (p:nos) = p : sieve (remove (multsof p) nos)

实际上接受并实现了两 对实现-一对用于此问题的试验部门筛网，另一对用于通过计算直接减去每个素数的倍数（也就是真正的Eratosthenes筛子）的有序去除（两者都是当然不推迟）。在Haskell，removemultsof

    multsof p n = rem n p==0            remove m xs = filter (not . m) xs

    multsof p = [p*p, p*p+p..]          remove m xs = diff xs m

（如果他只是推迟选择实际的实现方式...）

至于推迟的代码，在带有“列表模式” 的伪代码中，

    primes = [2, ...sieve primes [3..]]

    sieve [p, ...ps] [...h, p*p, ...nos] =
                     [...h, ...sieve ps (remove (multsof p) nos)]