Scala:为什么列表上的右折叠会导致堆栈溢出，而左折叠不会？

Question

我在字符串列表上运行了右折叠 (:\)，这导致了堆栈溢出。但是当我将其更改为使用左折叠 (/:) 时，它运行良好。为什么？

Answer 1

由于源代码是开放的，你实际上可以在LinearSeqOptimized.scala中看到实现。 :

override /*TraversableLike*/
def foldLeft[B](z: B)(f: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = f(acc, these.head)
    these = these.tail
  }
  acc
}

override /*IterableLike*/
def foldRight[B](z: B)(f: (A, B) => B): B =
  if (this.isEmpty) z
  else f(head, tail.foldRight(z)(f))

您会注意到 foldLeft使用 while 循环 while foldRight使用递归。循环策略非常有效，但递归需要为列表中的每个元素在堆栈上推送一个帧(因为它遍历到最后)。这就是为什么foldLeft工作正常，但 foldRight导致堆栈溢出。