Scala 流计算抛出 StackOverflowError

Question

为什么此代码片段执行会导致 StackOverflowError:

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

这实际上也会产生堆栈溢出。这是发生了什么:

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

...导致堆栈溢出。

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