Scala:列表中的不同 foldRight 实现 [英] Scala: different foldRight implementations in list

问题描述

我刚刚发现 scala(我使用的是 2.12)为 immutable list 和 mutable list 提供了完全不同的 foldRight 实现>.

I've just figured out that scala (I'm on 2.12) provides completely different implementations of foldRight for immutable list and mutable list.

不可变列表(List.scala):

Immutable list (List.scala):

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

可变列表(LinearSeqOptimized.scala):

Mutable list (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))

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

Now I'm just curious. Could you please explain me why was it implemented so differently?

推荐答案

List 中的 override 似乎覆盖了 foldRight 中的 >线性序列优化.LinearSeqOptimized

The override in List seems to override the foldRight in LinearSeqOptimized. The implementation in 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 替换.foldLeft 是堆栈安全的，因为它是由一个 while 循环实现的:

looks exactly like the canonical definition of foldRight as a catamorphism from your average theory book. However, as was noticed in SI-2818, this implementation is not stack-safe (throws unexpected StackOverflowError for long lists). Therefore, it was replaced by a stack-safe reverse.foldLeft in this commit. The foldLeft is stack-safe, because it has been implemented by a while loop:

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

That hopefully explains why it was overridden in List. It doesn't explain why it was not overridden in other classes. I guess it's simply because the mutable data structures are used less often and quite differently anyway (often as buffers and accumulators during the construction of immutable ones).

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

Hint: there is a blame button in the top right corner over every file on Github, so you can always track down what was changed when, by whom, and why.

这篇关于Scala:列表中的不同 foldRight 实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！