Fonctionnel
02/08/2024
Cyrille Martraire
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 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 foldRight 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.
