map, filter et fold remplacent les boucles
En programmation fonctionnelle, les fonctions map, filter et fold remplacent presque toutes les boucles. Chacune fait une seule chose : transformer chaque élément, garder certains éléments, ou réduire une liste à une valeur.
Une caisse de magasin passe d’une liste de prix à un total. Avec une boucle, il faut un compteur, un test et une addition. Avec ces trois fonctions, chaque étape a son nom.
À la fin de cette leçon
Remarque
Je peux remplacer une boucle par map, filter ou fold.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Fonction d’ordre supérieur | une fonction qui prend une autre fonction en argument | |
| map | applique une fonction à chaque élément d’une liste | map (* 2) [1, 2] |
| filter | garde les éléments qui passent un test | filter even [1, 2] |
| fold | réduit une liste à une seule valeur | foldr (+) 0 [1, 2] |
| Accumulateur | la valeur qu’un fold fait grandir à chaque élément |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
map applique une fonction à chaque élément
map f liste rend une nouvelle liste : f appliquée à chaque élément, dans le même ordre. La liste d’origine ne change pas.
Le morceau (* 2) est une fonction : le signe * auquel il manque son premier nombre. (* 2) 5 vaut 10. La boucle Python ci-dessous fait exactement ce que fait map (* 2) prix.
La boucle que map remplace
prix = [5, 25, 12, 40]
doubles = []
for p in prix:
doubles.append(p * 2)
print(doubles)
# C’est ce que fait map (* 2) prix en Haskell.
# Remplacez p * 2 par p + 1, puis relancez.
GHC écrit des listes comme on les tape
Dans ce labo, docker exec haskell ghc -e calcule une expression et écrit sa valeur. Les listes s’affichent entre crochets, sans espace après les virgules.
Tout ce que GHC écrit est en anglais ou en chiffres. Les Runs ci-dessous n’ont besoin d’aucun fichier.
Doubler chaque nombre
docker exec haskell ghc -e "map (* 2) [1, 2, 3]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Tripler chaque nombre
docker exec haskell ghc -e "map (* 3) [4, 5, 6]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
filter garde les éléments qui passent un test
filter test liste garde les éléments pour lesquels le test rend True. L’ordre est conservé. Le résultat peut être plus court, ou vide.
Un test est une fonction qui rend vrai ou faux. even dit si un nombre est pair. (> 20) dit si un nombre dépasse 20.
Exemple travaillé : filter (> 20) [5, 25, 12, 40]
| Élément | Test (> 20) | Gardé ? |
|---|---|---|
| 5 | False | Non |
| 25 | True | Oui |
| 12 | False | Non |
| 40 | True | Oui |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Garder les prix au-dessus de 20
docker exec haskell ghc -e "filter (> 20) [5, 25, 12, 40]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Garder les nombres pairs
docker exec haskell ghc -e "filter even [1 .. 10]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
fold réduit une liste à une valeur
foldr f départ liste combine les éléments un par un avec la fonction f, en partant de la valeur de départ. foldr (+) 0 [1, 2, 3] rend 6.
La valeur qui grandit est l’accumulateur. foldl part de la gauche de la liste et foldr de la droite. Pour +, le sens ne change rien. Pour -, il change le résultat.
Exemple travaillé : foldl et foldr avec -
| Fonction | Calcul, étape par étape | Résultat |
|---|---|---|
| foldl (-) 10 [1, 2, 3] | 10 - 1 = 9, puis 9 - 2 = 7, puis 7 - 3 | 4 |
| foldr (-) 10 [1, 2, 3] | 3 - 10 = -7, puis 2 - (-7) = 9, puis 1 - 9 | -8 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La somme de 1 à 10
docker exec haskell ghc -e "foldr (+) 0 [1 .. 10]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Soustraire de la gauche
docker exec haskell ghc -e "foldl (-) 10 [1, 2, 3]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Soustraire de la droite
docker exec haskell ghc -e "foldr (-) 10 [1, 2, 3]"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Exemple travaillé : les trois ensemble
| Étape | Expression | Résultat |
|---|---|---|
| 1 | filter odd [1 .. 10] | [1,3,5,7,9] |
| 2 | map (* 2) de la liste précédente | [2,6,10,14,18] |
| 3 | sum de la liste précédente | 50 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Filtrer, transformer, additionner
docker exec haskell ghc -e "sum (map (* 2) (filter odd [1 .. 10]))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens pensent que foldl et foldr donnent toujours le même résultat. C’est vrai pour + et *, qui se moquent de l’ordre. Pour - ou pour construire un texte, le sens compte : vérifiez avec un petit exemple.
Pour aller plus loin
Écrivez en Python une fonction longueur(liste) qui compte les éléments avec votre mon_fold, sans len. Indice : la fonction donnée au fold ignore l’élément et ajoute un au total.
Écrivez ensuite la même idée en Haskell avec foldr, puis vérifiez avec ghc -e sur une liste de cinq éléments.