scala - Scala：为什么 List 上的右折叠会导致堆栈溢出，而左折叠不会？

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 循环 whilefoldRight使用递归。循环策略非常有效，但递归需要为列表中的每个元素在堆栈上推送一个框架（因为它遍历到末尾）。这就是为什么foldLeft工作正常但foldRight导致堆栈溢出的原因。

Answer 2

Fold是一组通用的通用函数，它们遍历递归数据结构并通常产生单个值（参考）。在序列和列表上，FoldLeft（一般意义上）是尾递归的，因此可以对其进行优化。FoldRight 不是尾递归的，因此不能进行尾调用优化。然而，它确实有可能应用于无限级数的好处。

scala 库的实现foldLeft（foldRight从@dhg 的答案盗版）反映了这种优化/缺乏。foldLeft已使用 while 循环手动优化尾调用。foldRight不可能是。

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))

我相信Odersky、Spoon、Venners 的 Programming in Scala, Second Edition中的折叠部分描述了foldLeftLists 如何是尾递归的，而它可能是foldRight无限列表。不幸的是，我现在没有它来提供页码等。如果没有，证明这一点并不难。

另请参阅Miran Lipovača 的 Learn You a Haskell for Great Good中的折叠部分

回到我们处理递归的时候，我们注意到在许多对列表进行操作的递归函数中都有一个主题。通常，我们会有一个空列表的边缘情况。我们将引入 x:xs 模式，然后我们将执行一些涉及单个元素和列表其余部分的操作。事实证明这是一种非常常见的模式，因此引入了几个非常有用的函数来封装它。这些函数称为折叠。