Implémentation de foldLeft dans Scala

Question

TraversableOnce implémente foldLeft avec mutable var result.

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

Je comprends qu'il ne soit pas pratique de mettre en œuvre foldLeft récursive. Maintenant, je me demande s'il est possible de mettre en œuvre foldLeft sans variables mutables efficacement.

Cela peut-il être fait? Pourquoi si ça ne peut pas?

Answer 1

Queue-récursion est votre ami:

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 n'implémente pas head ou tail, la seule façon d'accéder aux éléments est d'utiliser foreach.

Answer 2

def foldLeft[B](z: B)(op: (B, A) => B): B = { 
    val thislist = this.toList 
    @tailrec 
    def myFold(result: B, list: List[A]): B = list match { 
    case Nil => result 
    case head :: tail => myFold(op(result,head), tail) 
    } 
    myFold(z, thislist) 
}