Scala 流计算抛出 StackOverflowError

Question

为什么这个代码片段的执行结果是 WhosebugError:

lazy val primes: Stream[Int] = 2 #:: Stream.from(3, 2) filter { pc =>
  primes.takeWhile(x => x * x <= pc) forall (p => pc % p != 0)
}
primes.take(5).last

虽然此代码片段工作正常（请参阅 filter 之前的点）：

lazy val primes: Stream[Int] = 2 #:: Stream.from(3, 2).filter { pc =>
  primes.takeWhile(x => x * x <= pc) forall (p => pc % p != 0)
}
primes.take(5).last

Answer 1

括号将使此处的执行顺序更加明显。 primes 的以下两个定义等同于它们在 OP 中的对应定义。

// fails with stack overflow
lazy val primes: Stream[Int] = (2 #:: Stream.from(3, 2)) filter { pc =>
  primes.takeWhile(x => x * x <= pc) forall (p => pc % p != 0)
}

// succeeds
lazy val primes: Stream[Int] = 2 #:: (Stream.from(3, 2).filter { pc =>
  primes.takeWhile(x => x * x <= pc) forall (p => pc % p != 0)
})

好的，第一个有什么问题？它首先通过创建流 (2 #:: Stream.from(3, 2))，然后对其进行过滤来定义。让我们尝试访问第一个元素：

primes.head

这实际上也产生了堆栈溢出。事情是这样的：

head 尝试访问 primes.
必须根据 filter 谓词检查第一个元素 2。
要检查谓词，我们必须递归访问primes。
我们尝试获取 primes 的第一个元素，它必须运行 filter 谓词 2。
重复步骤 3。

...导致堆栈溢出。

第二个例子没有遇到这个问题，因为Stream(2)的头部没有被过滤，所以在那一步没有递归检查2 是否真的存在。也就是说，在第二个例子中，很明显2就是Stream的head。在第一个示例中，Stream 的 head 必须通过检查 filter 来计算，但为了这样做，在无限递归循环中引用自身。

Scala 流计算抛出 StackOverflowError

Scala stream computation throws StackOverflowError

stack-overflow

scala

stream