Haskell calcule seulement ce qui sert
L’évaluation paresseuse veut dire qu’une expression n’est calculée que si son résultat sert. Haskell s’en sert pour écrire des listes infinies, dont il ne calcule que la partie utilisée.
La liste de tous les entiers n’existe jamais en entier dans la mémoire. L’expression take 5 [1 ..] en demande cinq, et Haskell n’en fabrique que cinq. Avant cela, la leçon montre la récursivité : une fonction qui s’appelle elle-même.
À la fin de cette leçon
Remarque
Je peux écrire une fonction récursive et expliquer pourquoi une liste infinie reste utilisable.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Récursivité | une fonction qui s’appelle elle-même sur un cas plus petit | |
| Cas de base | le cas le plus petit, résolu sans nouvel appel | mySum [] = 0 |
| Évaluation paresseuse | ne calculer une expression que si son résultat sert | |
| Liste infinie | une liste sans fin dont on ne calcule que le début | [1 ..] |
| Générateur | une fonction Python qui rend ses valeurs une par une avec yield |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction récursive a un cas de base
Une fonction récursive s’appelle elle-même sur un cas plus petit. Elle a deux parties : un cas de base, résolu sans nouvel appel, et un cas récursif.
Pour additionner une liste : la somme de la liste vide est 0. La somme d’une liste est sa tête plus la somme de sa queue. Sans cas de base, la fonction s’appellerait sans fin.
La fonction mySum du fichier Fold.hs
-- Fold.hs : une fonction qui s’appelle elle-même.
mySum :: [Int] -> Int
mySum [] = 0
mySum (x : rest) = x + mySum rest
Ce que GHC écrit reste en anglais
Dans ce labo, docker exec haskell ghc -e calcule une expression et écrit sa valeur. Les mots que GHC écrit restent en anglais.
Le premier Run charge Fold.hs pour utiliser mySum. Les suivants n’ont besoin d’aucun fichier.
Additionner de 1 à 10 avec mySum
docker exec haskell ghc -e "mySum [1 .. 10]" Fold.hsAffiché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é : la factorielle de 3
| Appel | Se réduit à | Cas |
|---|---|---|
| fact 3 | 3 * fact 2 | Récursif |
| fact 2 | 2 * fact 1 | Récursif |
| fact 1 | 1 * fact 0 | Récursif |
| fact 0 | 1 | Cas de base |
| On remonte | 1 * 1 = 1, puis 2 * 1 = 2, puis 3 * 2 = 6 | Résultat |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La factorielle de 5, définie dans la commande
docker exec haskell ghc -e "let fact n = if n == 0 then 1 else n * fact (n - 1) in fact 5"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.
La même valeur avec product
docker exec haskell ghc -e "product [1 .. 5]"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.
La paresse retarde le calcul jusqu’au besoin
Haskell ne calcule une expression que si son résultat sert. undefined est une valeur qui fait échouer le programme si on la calcule.
Dans fst (1, undefined), on ne demande que le premier élément de la paire : undefined n’est jamais calculé. C’est ce qui permet une liste infinie : [1 ..] est la promesse des entiers, calculée au fur et à mesure.
Une valeur qu’on ne calcule jamais
docker exec haskell ghc -e "fst (1, undefined)"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.
Les cinq premiers entiers de la liste infinie
docker exec haskell ghc -e "take 5 [1 ..]"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.
Doubler une liste infinie, en prendre trois
docker exec haskell ghc -e "take 3 (map (* 2) [1 ..])"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é : take 3 (map (* 2) [1 ..])
| Demande | Ce que Haskell calcule | Éléments faits |
|---|---|---|
| Premier élément | Le 1 de [1 ..], puis 1 * 2 = 2 | 1 |
| Deuxième élément | Le 2 de [1 ..], puis 2 * 2 = 4 | 2 |
| Troisième élément | Le 3 de [1 ..], puis 3 * 2 = 6 | 3 |
| Quatrième élément | Jamais demandé : take s’arrête | Aucun de plus |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Les carrés plus petits que 40
docker exec haskell ghc -e "takeWhile (< 40) (map (^ 2) [1 ..])"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 qu’une liste infinie remplit la mémoire de l’ordinateur. Seuls les éléments demandés sont calculés. Mais demander toute la liste, avec length [1 ..] ou sum [1 ..], ne s’arrête jamais : on ne l’essaie pas.
Un générateur Python est paresseux aussi
Python a la même idée avec les générateurs. Une fonction qui contient yield rend une valeur, puis attend qu’on la redemande.
next(flux) demande la valeur suivante. Entre deux demandes, rien n’est calculé. Le flux ci-dessous n’a pas de fin, mais trois demandes ne produisent que trois valeurs.
Un flux sans fin en Python
def entiers_depuis(n):
# yield rend une valeur, puis la fonction attend la demande suivante.
while True:
yield n
n = n + 1
flux = entiers_depuis(1)
print(next(flux), next(flux), next(flux))
# Ajoutez une quatrième demande avec next(flux), puis relancez.
Pour aller plus loin
Pour trouver les dix premiers nombres de Fibonacci en Haskell, on peut écrire la liste à partir d’elle-même. Essayez dans ghci avec docker exec -it haskell ghci.
Tapez let fibs = 0 : 1 : zipWith (+) fibs (tail fibs), puis take 10 fibs. Expliquez en une phrase pourquoi cela ne boucle pas.