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