Scala:列表中的不同 foldRight 实现

Question

我刚刚发现 scala(我在 2.12 上)提供了完全不同的 实现。 foldRight 为 不可变列表 和 可变列表 .

不可变列表(List.scala):

override def foldRight[B](z: B)(op: (A, B) => B): B =
    reverse.foldLeft(z)((right, left) => op(left, right))

可变列表(LinearSeqOptimized.scala):

  def foldRight[B](z: B)(@deprecatedName('f) op: (A, B) => B): B =
    if (this.isEmpty) z
    else op(head, tail.foldRight(z)(op))

现在我只是好奇。
你能解释一下为什么它的实现方式如此不同吗？

Answer 1

override在 List似乎覆盖了 foldRight在 LinearSeqOptimized . LinearSeqOptimized中的实现

def foldRight[B](z: B)(@deprecatedName('f) op: (A, B) => B): B =
  if (this.isEmpty) z
  else op(head, tail.foldRight(z)(op))

看起来与 foldRight 的规范定义完全一样作为普通理论书中的变形记。然而，正如在 SI-2818 中注意到的那样，此实现不是堆栈安全的(对于长列表抛出意外 StackOverflowError)。因此，它被堆栈安全 reverse.foldLeft 所取代。在 this commit . foldLeft是堆栈安全的，因为它是由一个 while 循环实现的:

def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = op(acc, these.head)
    these = these.tail
  }
  acc
}

这有望解释为什么它在 List 中被覆盖。 .它没有解释为什么它没有在其他类中被覆盖。我想这仅仅是因为可变数据结构的使用频率较低，而且无论如何都非常不同(通常在构造不可变数据结构期间用作缓冲区和累加器)。

提示:有一个 blame Github 上每个文件右上角的按钮，因此您可以随时追踪更改的时间、人员和原因。