Blog Arolla

Listes Scala: méthodes foldLeft et foldRight

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.

1 comment for “Listes Scala: méthodes foldLeft et foldRight

  1. Eric Le Goff
    29 avril 2015 at 16 h 14 min

    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 :”

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *