15

所以我花了几个小时试图弄清楚这段代码是如何产生素数的。

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
   ps.takeWhile{j => j * j <= i}.forall{ k => i % k > 0});

我使用了许多 printlns 等，但没有什么让它更清楚。

这就是我认为代码的作用：

/**
 * [2,3] 
 * 
 * takeWhile 2*2 <= 3 
 * takeWhile 2*2 <= 4 found match
 *      (4 % [2,3] > 1) return false.
 * takeWhile 2*2 <= 5 found match
 *      (5 % [2,3] > 1) return true 
 *          Add 5 to the list
 * takeWhile 2*2 <= 6 found match
 *      (6 % [2,3,5] > 1) return false
 * takeWhile 2*2 <= 7
 *      (7 % [2,3,5] > 1) return true
 *          Add 7 to the list
 */

但是，如果我j*j将列表更改为 2*2，我认为它的工作方式完全相同，则会导致 stackoverflow 错误。

我显然在这里遗漏了一些基本的东西，并且真的可以像我五岁时那样向我解释这一点。

任何帮助将不胜感激。

4

3 回答 3

27

我不确定寻求程序/命令式解释是在这里获得理解的最佳方式。流来自函数式编程，最好从这个角度理解它们。您给出的定义的关键方面是：

  1. 它很懒。除了流中的第一个元素之外，在您请求之前不会计算任何内容。如果你从不要求第五个素数，它就永远不会被计算出来。

  2. 它是递归的。素数列表是根据自身定义的。

  3. 它是无限的。流有一个有趣的特性（因为它们是惰性的），它们可以表示具有无限数量元素的序列。Stream.from(3)就是一个例子：它表示列表 [3, 4, 5, ...]。

让我们看看我们是否能理解为什么您的定义会计算素数序列。

定义以2 #:: .... 这只是说序列中的第一个数字是 2 - 到目前为止足够简单。

下一部分定义了其余的素数。我们可以从所有从 3 ( Stream.from(3)) 开始的计数开始，但显然我们需要过滤掉一堆这些数字（即所有的复合数字）。所以让我们考虑每个数字i。如果i不是较小素数的倍数，i则为素数。也就是说，如果对于所有小于i的素数，则为素数 。在 Scala 中，我们可以将其表示为kii % k > 0

nums.filter(i => ps.takeWhile(k => k < i).forall(k => i % k > 0))

但是，实际上并不需要检查所有较小的素数——我们实际上只需要检查平方小于或等于的素数i（这是数论中的事实*）。所以我们可以改为写

nums.filter(i => ps.takeWhile(k => k * k <= i).forall(k => i % k > 0))

所以我们得出了你的定义。

现在，如果您碰巧尝试了第一个定义（带有k < i），您会发现它不起作用。为什么不？这与这是一个递归定义这一事实有关。

假设我们试图确定序列中 2 之后的内容。定义告诉我们首先确定 3 是否属于。为此，我们考虑到第一个大于或等于 3 ( takeWhile(k => k < i)) 的素数列表。第一个素数是 2，小于 3——到目前为止还不错。但是我们还不知道第二个素数，所以我们需要计算它。好吧，所以我们需要先看看 3 是否属于... BOOM！

* 很容易看出，如果一个数n是合数，那么它的一个因数的平方必须小于或等于n。如果n是复合的，那么根据定义n == a * b，哪里1 < a <= b < n（我们可以a <= b通过适当地标记这两个因素来保证）。从a <= b它遵循那个a^2 <= a * b，所以它遵循那个a^2 <= n。

于 2013-03-24T07:11:19.517 回答
3

你的解释大多是正确的，你只犯了两个错误：

takeWhile不包括最后检查的元素：

scala> List(1,2,3).takeWhile(_<2)
res1: List[Int] = List(1)

您假设它ps总是只包含一个二和一个三，但是因为Stream它是懒惰的，所以可以向它添加新元素。事实上，每次发现一个新的素数时，它都会被添加到下一步中，ps并且在下一步takeWhile中将考虑这个新添加的元素。在这里，重要的是要记住 a 的尾部Stream仅在需要时才计算，因此在评估为 truetakeWhile之前看不到它。forall

记住这两件事，你应该想出这个：

ps = [2]
i = 3
  takeWhile
    2*2 <= 3 -> false
  forall on []
    -> true
ps = [2,3]
i = 4
  takeWhile
    2*2 <= 4 -> true
    3*3 <= 4 -> false
  forall on [2]
    4%2 > 0 -> false
ps = [2,3]
i = 5
  takeWhile
    2*2 <= 5 -> true
    3*3 <= 5 -> false
  forall on [2]
    5%2 > 0 -> true
ps = [2,3,5]
i = 6
...

虽然这些步骤描述了代码的行为，但它并不完全正确，因为不仅向其中添加元素Stream是惰性的，而且对它的每个操作都是惰性的。这意味着，当您调用xs.takeWhile(f)所有值时，直到f为 false 的点才会立即计算 - 它们是在forall想要查看它们时计算的（因为它是这里唯一需要查看所有元素的函数，然后才能确定为 true , 为 false 它可以提前中止）。这里是在任何地方都考虑惰性时的计算顺序（仅查看 9 的示例）：

ps = [2,3,5,7]
i = 9
  takeWhile on 2
    2*2 <= 9 -> true
  forall on 2
    9%2 > 0 -> true
  takeWhile on 3
    3*3 <= 9 -> true
  forall on 3
    9%3 > 0 -> false
ps = [2,3,5,7]
i = 10
...

因为forall当它评估为假时被中止，takeWhile不计算剩余的可能元素。

于 2013-03-24T02:32:27.237 回答
1

该代码更容易（至少对我来说）阅读一些变量，暗示性地重命名，如

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
   ps.takeWhile{p => p * p <= i}.forall{ p => i % p > 0});

这很自然地从左到右读取，因为

素数是2i ，并且从3开始的那些数字，即平方不超过 的所有素数 ，不均分（即没有一些非零余数）。pii

以真正的递归方式，为了将这个定义理解为定义不断增加的素数流，我们假设它是这样的，并且从这个假设中我们看到没有出现矛盾，即定义的真实性成立。

之后唯一的潜在问题ps 是在定义流时访问流的时间。作为第一步，想象我们只是从某个地方神奇地提供了另一个素数流。然后，在看到定义的真实性之后，检查访问的时机是否正确，即我们从不尝试访问ps未定义的区域；这会使定义停滞不前，毫无成效。

我记得在某个地方（不记得在哪里）读过类似下面的东西——一个学生和一个巫师之间的对话，

  • 学生：哪些数是质数？
  • 巫师：嗯，你知道第一个质数是多少吗？
  • s：是的，它是2。
  • w：好的（很快在一张纸上写下2 ）。那么下一个呢？
  • s：嗯，下一个候选人是3。我们需要检查它是否被任何平方不超过它的素数除，但我还不知道素数是什么！
  • w：别担心，我给你。这是我知道的魔法；毕竟我是个巫师。
  • s：好的，那么第一个质数是多少？
  • w：（瞥了一眼纸）2。
  • s：太好了，所以它的平方已经大于3了……嘿，你作弊了！......

这是您的代码的伪代码1翻译，部分从右到左读取，为清楚起见再次重命名了一些变量（p用于“prime”）：

ps = 2 : filter (\i-> all (\p->rem i p > 0) (takeWhile (\p->p^2 <= i) ps)) [3..]

这也是

ps = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p->p^2 <= i) ps]]

使用list comprehensions在视觉上更明显。and检查布尔值列表中的所有条目是否为True（读|作“for”、<-“drawn from”、,“such that”和(\p-> ...)“ lambda of p”）。

所以你看，ps 是一个 2 的惰性列表，然后是i从一个流中抽取的数字[3,4,5,...]，使得对于所有p从ps这样抽取的数字p^2 <= i，确实i % p > 0。这实际上是一个最优的 试划分算法。:)

当然，这里有一个微妙之处：列表ps是开放式的。我们使用它是因为它正在“充实”（当然，因为它是懒惰的）。当ps 取自 时ps，可能会出现超出其末尾的情况，在这种情况下，我们将进行非终止计算（“黑洞”）。就这样发生了:)（并且需要 ⁄ 可以在数学上证明）上述定义是不可能的。所以 2 被无条件地放入ps，所以它有一些东西开始。

但如果我们尝试“简化”，

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p->p < i) bad]]

它在只产生一个数字 2 后停止工作：当考虑 3 作为候选时，takeWhile (\p->p < 3) bad要求bad2 之后的下一个数字，但那里还没有更多的数字。它“超越自己”。

这是“固定”的

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- [2..(i-1)] ]]

但这是一种慢得多的试验划分算法，与最优算法相去甚远。

--

1（实际上是Haskell，那样对我来说更容易:)）

于 2013-03-24T10:00:26.467 回答