Scala: 为什么对列表进行右折叠会导致堆栈溢出而左折叠不会？

Question

我在一个String列表上进行了右折叠（:\），导致堆栈溢出。但是当我改用左折叠（/:）时，它就正常工作了。为什么？

- Qi Qi

---

顺便提一下，如果你必须从右侧折叠，请考虑先翻转列表，然后从左侧折叠（必要时再次翻转）--这样可以使用堆而不是栈（但对于小列表来说速度较慢）。 - Rex Kerr

@RexKerr 在 TraversableOnce 上，def foldRight[B](z: B)(op: (A, B) => B): B = reversed.foldLeft(z)((x, y) => op(y, x))。难道没有一个启发式方法来转到 /:? 吗？ - som-snytt

大多数情况下，使用正确的折叠方式并不必要，因此我可以选择安全地使用左折叠。谢谢，伙计们。 - Qi Qi

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

- dhg

---

是的，没错。字符串列表只有6000个元素，右折叠操作会导致堆栈崩溃。 - Qi Qi

Answer 2

Fold 是一组通用的常用函数，它们遍历递归数据结构并通常产生单个值(reference)。在序列和列表上，FoldLeft（在一般意义上）是尾递归的，因此可以进行优化。FoldRight不是尾递归，因此无法进行尾调用优化。但它可能有将被应用于无限序列的好处。

Scala库中foldLeft和foldRight的实现（从@dhg的答案中盗版）反映了这种优化/缺乏优化。使用while循环手动尾调用优化了foldLeft。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))

我相信在Programming in Scala, Second Edition by Odersky, Spoon, Venners中有一节关于折叠的内容，其中描述了如何在列表上使用foldLeft是尾递归的，而在无限列表上可能可以使用foldRight。不幸的是，我目前手头没有这本书，无法提供页码等信息。如果没有，证明这一点也不是很困难。

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

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

- drstevens

---

http://www.artima.com/pins1ed/working-with-lists.html#16.7 虽然也许你的意思是它在第二版中得到了改进。 - som-snytt

嗯，我没有看到我想要的那部分。我读了第二版，但是大约两年前就读完了，紧接着是《学习 Haskell》...所以有可能我把两者混淆了。 - drstevens