问foldRight效率？

EN

正如您从文档中看到的，List的foldRight和foldLeft方法都是在LinearSeqOptimized中定义的。

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使用简单的递归方法。特别是，它不是尾递归的。因此，foldRight会产生创建新堆栈帧的开销，并且如果您在一个很长的列表上尝试它(尝试，例如((1 to 10000).toList :\ 0)(_+_) )，则会导致堆栈溢出。轰隆隆！但它在没有toList的情况下工作得很好，因为Range的foldRight是通过反转左侧折叠来工作的)。

那么为什么不总是使用foldLeft呢？对于链表，右折叠可以说是一种更自然的功能，因为链表需要以相反的顺序构建。您可以对上面的方法使用foldLeft，但您需要在最后对输出进行reverse。(不要试图附加到左文件夹中的列表，因为复杂度是O(n平方)。)

至于在实践中哪个更快，foldRight和foldLeft + reverse，我运行了一个简单的测试，对于列表，foldRight的速度快了10%到40%。这一定是为什么List的foldRight是以这种方式实现的。

foldRight反转列表并应用foldLeft。