scala - foldRight效率？

我听说foldLeft在大多数操作中效率更高，但是Scala School(来自Twitter)提供了以下示例。有人可以对其效率进行分析吗，我们应该使用foldLeft实现相同的操作吗？

val numbers = List(1,2,3,4,5,...10)
def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = {
    numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) =>
    fn(x) :: xs
  }
}

scala> ourMap(numbers, timesTwo(_))
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

最佳答案

从文档中可以看到，List定义了LinearSeqOptimized的foldRight和foldLeft方法。因此，请查看源代码:

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)(_+_)。Boom!但是在没有toList的情况下，它仍然可以正常工作，因为Range的foldRight可以通过向左翻转)。

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

至于实践中更快的foldRight或foldLeft + reverse，我进行了一个简单的测试，列表的foldRight更快了10％到40％。这必须是为什么List的foldRight如此实现的原因。