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

...Which导致堆栈溢出。

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