22

我很难理解这段代码：

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

有人可以为我分解吗？我知道其中有递归，但这就是我无法理解此示例中的递归如何工作的问题。

4

5 回答 5

24

与其他人在这里所说的相反，这个函数没有实现 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. 此表达式的结果是 的结果y。所以在这种情况下，我们定义一个函数sieve并返回应用[2..]到的结果sieve。

  2. 现在让我们仔细看看let这个表达式的一部分：

    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
    1. 这定义了一个sieve将列表作为其第一个参数的函数。
    2. (p:xs)是与所述列表的头部和尾部（除了头部之外的所有内容）匹配的模式。pxs
    3. 通常，p : xs是一个列表，其第一个元素是p。xs是一个包含剩余元素的列表。因此，sieve返回它接收到的列表的第一个元素。

    4. 不看列表的其余部分：

      sieve (filter (\x -> x `mod` p /= 0) xs)
      1. 我们可以看到它sieve被递归调用。因此，filter表达式将返回一个列表。
      2. filter接受一个过滤器函数和一个列表。它仅返回列表中过滤器函数为其返回 true 的那些元素。

      3. 在这种情况下xs，列表被过滤并且

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

        是过滤功能。

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

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

    1. 将返回数字 2。所有其他为 2 的倍数的自然数将被丢弃。
    2. 因此，第二个数字是 3。它将被返回。所有其他 3 的倍数将被丢弃。
    3. 因此下一个数字将是 5。等等。
于 2009-11-19T15:50:19.137 回答
17

它实际上非常优雅。

首先，我们定义一个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 (\ x -> x 'mod' p /= 0) xs

filter接受一个函数和一个我们应用该函数的列表，并保留满足函数给出的标准的元素。在这种情况下，filter采用匿名函数：

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

这个匿名函数有一个参数，x. 它检查反对的模数（列表的头部，每次被调用）：xpsieve

 x 'mod' p

如果模数不等于 0：

 x 'mod' p /= 0

然后该元素x保留在列表中。如果它等于 0，则将其过滤掉。这是有道理的：如果能被,x整除，则不能被 1 和自身整除，因此它不是素数。px

于 2009-11-19T15:49:13.710 回答
10

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

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

primes := Sieve (Nums 2)

它使用匿名函数的柯里化形式，相当于

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

两者Sieve和Filter都是具有内部状态和按值参数传递语义的数据构造操作。

在这里我们可以看到，这段代码最明显的问题不是，重复一遍，它使用试除法从工作序列中过滤掉倍数，而它可以通过以 为增量直接找出它们。如果我们将前者替换为后者，则生成的代码仍将具有极其糟糕的运行时复杂性。p

不，它最明显的问题是它过早Filter地将 a放在其工作序列的顶部，而只有在输入中看到素数的平方之后它才真正应该这样做。结果，与真正需要的相比，它创建了一个二次数的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+1

Filter 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)

实际上承认两 对实现remove并multsof一起进行 - 一对用于本问题中的试验除法筛，另一对用于通过计数直接生成的每个素数的倍数的有序去除，也就是埃拉托色尼的真正筛（两者都是当然，不可推迟）。在哈斯克尔，

    multsof p n = (rem n p)==0              multsof p = [p*p, p*p+p..]

    remove m xs = filter (not.m) xs         remove m xs = minus xs m

（要是他推迟在这里选择实际的实现就好了……）

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

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

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

在现代 Haskell 中可以ViewPatterns写成

{-# LANGUAGE ViewPatterns #-}

primes = 2 : sieve primes [3..]

sieve (p:ps) (span (< p*p) -> (h, _p2 : nos)) 
                             = h ++ sieve ps (remove (multsof p) nos)
于 2012-01-15T17:51:54.497 回答
2

它正在实施埃拉托色尼筛法

基本上，从素数 (2) 开始，然后从其余整数中过滤掉所有 2 的倍数。该过滤列表中的下一个数字也必须是素数，因此从剩余的中过滤掉它的所有倍数，依此类推。

于 2009-11-19T15:42:14.533 回答
2

它说“某个列表的筛子是列表的第一个元素（我们称之为 p）和列表其余部分的筛子，经过过滤，只有不能被 p 整除的元素才允许通过”。然后，它通过将所有整数的筛从 2 返回到无穷大（即 2 后跟所有不能被 2 整除的整数的筛等）来开始。

在你攻击 Haskell 之前，我推荐The Little Schemer 。

于 2009-11-19T15:47:43.087 回答