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. CCD_ 5尝试访问CCD_ 6的第一元素
2. 必须对照filter谓词检查第一个元素2
3. 要检查谓词，我们必须递归地访问primes
4. 我们尝试获取primes的第一个元素，它必须在2上运行filter谓词
5. 重复步骤3

这会导致堆栈溢出。

第二个例子没有遇到这个问题，因为Stream（2）的头部没有被过滤，所以在该步骤中没有递归来检查2是否真的存在。换言之，在第二示例中，清楚地，2是Stream的head。在第一个例子中，Stream的head必须通过检查filter来计算，但为了这样做，它在无限递归循环中引用自己。