List implementation of foldLeft in Scala

Question

Scala foldLeft implementation is:

def foldLeft[B](z: B)(op: (B, A) => B): B = {
   var result = z
   this foreach (x => result = op(result, x))
   result
}

Why scala develovers don't use something like tail recursion or something else like this(It's just example) :

def foldLeft[T](start: T, myList: List[T])(f:(T, T) => T): T = {
  def foldRec(accum: T, list: List[T]): T = {
    list match {
      case Nil => accum
      case head :: tail => foldRec(f(accum, head), tail)
    }
  }
  foldRec(start, myList)
}

Can it be? Why if it cannot/can?

I'm not sure all these "why is this Scala library written this way?" questions are very useful, even when the library in question is the standard library. They'd probably be a better fit on one of the Scala mailing lists, or the scala/scala Gitter chat room. — Travis Brown, Jul 12 '15 at 21:59

score 3 · Answer 1 · answered Jul 12 '15 at 21:45

"Why not replace this simple three-line piece of code with this less simple seven-line piece of code that does the same thing?"

Um. That's why.

(If you are asking about performance, then one would need benchmarks of both solutions and an indication that the non-closure version was significantly faster.)

score 0 · Accepted Answer · edited May 23 '17 at 12:21

According to this answer, Scala does support tail-recursion optimization, but it looks like it wasn't there from the beginning, and it might still not work in every case, so that specific implementation might be a leftover.

That said, Scala is multi-paradigm and I don't think it strives for purity in terms of its functional programming, so I wouldn't be surprised if they went for the most practical or convenient approach.

score 0 · Answer 3 · answered Jul 13 '15 at 07:45

Beside the imperative solution is simpler, it is also way more general. As you may have noticed, foldLeft is implemented in TraversableOnce and depends only on the foreach method. Thus, by extending Traversable and implementing foreach, which is probably the simplest method to implement on any collection, you get all these wonderful methods.

The declarative implementation on the other hand is reflexive on the structure of the List and very specific as it depends on Nil and ::.

List implementation of foldLeft in Scala

3 Answers3