4

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

Immutable list (List.scala):

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

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?

Normal
  • 1,347
  • 4
  • 17
  • 34

1 Answers1

8

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))

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
}

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).

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.

Andrey Tyukin
  • 43,673
  • 4
  • 57
  • 93