Dans ce billet je souhaite vous parler rapidement des méthodes foldLeft et foldRight de l’API des listes en Scala.
foldLeft
foldLeft est une méthode de la classe scala.collection.immutable.List et voici ce que le scaladoc nous en dit:
“Applies a binary operator to a start value and all elements of this list, going left to right.”
Scaladoc nous dit que foldLeft applique une fonction prenant deux paramètres (opérateur binaire) à une valeur initiale (appelée accumulateur dans le jargon fonctionnel) et à tous les éléments de la liste en partant de la gauche. Voyons attentivement la signature de la méthode pour rendre les choses un peu plus claires!
|
1
|
def foldLeft [B] (z: B)(f: (B, A) ⇒ B): B |
Ah tiens une chose transparaît dans cette signature: foldLeft est une méthode currifiée. Si vous n’avez jamais fait de programmation fonctionnelle auparavant cette notion ne doit pas vous parler. En fait malgré les apparences la méthode foldLeft ne prend pas deux arguments! Voici comment elle fonctionne: elle prend un paramètre z de type B et renvoie une fonction qui prend à son tour un paramètre qui est une fonction de type (B, A) => B. z représente la valeur initiale de l’accumulateur et est du même type que la valeur de retour de foldLeft. A chaque étape la fonction f est appliquée à l’accumulateur et à l’élément courant de la liste. La valeur de l’accumulateur peut changer tout au long du déroulement de l’opération. Prenez une minute pour bien visualiser la chose ce n’est pas si compliqué que cela une fois qu’on a compris la notion. La méthode fold est d’une puissance incroyable! Elle vous permet de faire quasiment de faire toutes les opérations imaginables avec les listes.
Voici un usage simple de foldLeft: Calculer la somme des éléments d’une liste d’entiers.
L’accumulateur (la valeur initiale) est égal à zéro et l’opérateur binaire est une fonction qui prend deux entiers et fait leur somme:
|
1
2
3
4
|
val nums = List(1, 2, 3, 4) val sum = nums.foldLeft(0){ (acc, num) => acc + num |
En action dans le REPL:
|
1
2
3
4
5
6
7
|
scala> val nums = List(1, 2, 3, 4) nums: List[Int] = List(1, 2, 3, 4) scala> val sum = nums.foldLeft(0){(acc, num) => acc + num } sum: Int = 10 |
Le déroulé de l’opération foldLeft est le suivant :
|
1
2
3
4
5
|
((((0 + 1) + 2) + 3) + 4)((((1) + 2) + 3) + 4)(((3) + 3) + 4)((6) + 4)(10) |
En image cela donne:
foldRight
foldRight est assez similaire à foldLeft mais il parcourt la liste en partant de la droite de la liste. Ainsi c’est le dernier élément de la liste qui est d’abord traité. Voyons l’implémentation de la somme des éléments d’une liste avec foldRight:
|
1
2
3
4
5
6
|
scala> val nums = List(1, 2, 3, 4)nums: List[Int] = List(1, 2, 3, 4)scala> val sum = nums.foldRight(0) {(num, acc) => num + acc}sum: Int = 10 |
Le déroulé de l’opération foldLeft est le suivant :
|
1
2
3
4
5
|
(1 + (2 + (3 + (4 + 0))))(1 + (2 + (3 + (4))))(1 + (2 + (7)))(1 + (9))(10) |
Conclusion
Prenez le temps de digérer ce contenu, si jamais l’envie me prend dans l’avenir je reviendrais sur une comparaison plus avancée entre ces deux méthodes.
Le deuxieme deroule s’intitule :
“Le déroulé de l’opération foldLeft est le suivant :”
il faudrait plutot
“Le déroulé de l’opération foldRight est le suivant :”
Que dire ?
Merci !
merci beaucoup 😉 c’est assez claire pour qq1 qui débute sur scala
oh trop bien l’article a dix ans !!!!!!
bon anniversaire !!!!!!!!
😀 😀 😀 😀
L’article oublie une différence importante:
foldLeft est dit “tail recursive” alors que foldRight ne l’ai pas.
Ce qui fait que foldLeft est stack safe lors de l’utilisation de listes très longues car il ne produit qu’une stack pour toute la liste.
A l’inverse foldRight est susceptible de générer une stack overflow car il produit une stack pour chaque élément de la liste.