Implementation of foldLeft in Scala

Question

TraversableOnce implements foldLeft with mutable var result.

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

I understand that it is not practical to implement foldLeft recursively. Now I wonder if it is possible to implement foldLeft without mutable variables efficiently.

Can it be done ? Why if it cannot ?

Answer 1

Tail-recursion is your friend:

def foldLeft[A, B](xs: Seq[A], z: B)(op: (B, A) => B): B = {
  def f(xs: Seq[A], acc: B): B = xs match {
    case Seq()   => acc
    case x +: xs => f(xs, op(acc, x))
  }
  f(xs, z)
}

Btw, TraversableOnce doesn't implement head or tail, the only way to access the elements is to use foreach.