Apprendre Haskell vous fera le plus grand bien !

Pour l'instant, applyLog prend des valeurs de type (a, String), mais y a-t-il une raison à ce que le registre soit une String ? On utilise ++ pour juxtaposer les registres, ne devrait-ce donc pas marcher pour n'importe quel type de liste, pas seulement des listes de caractères ? Bien sûr que oui. On peut commencer par changer son type en :

applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])

À présent, le registre est une liste. Le type des valeurs dans la liste doit être le même dans la valeur originale que dans la valeur retournée par la fonction, autrement on ne saurait utiliser ++ pour les juxtaposer.

Est-ce que cela marcherait pour des chaînes d'octets ? Il n'y a pas de raison que ça ne marche pas. Cependant, le type qu'on a là ne marche que pour les listes. On dirait qu'il nous faut une autre fonction applyLog pour les chaînes d'octets. Mais attendez ! Les listes et les chaînes d'octets sont des monoïdes. En tant que tels, elles sont toutes deux des instances de la classe de types Monoid, ce qui signifie qu'elles implémentent la fonction mappend. Et pour les listes autant que les chaînes d'octets, mappend sert à concaténer. Regardez :

ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]
Chunk "chi" (Chunk "huahua" Empty)

Cool ! Maintenant, applyLog peut fonctionner sur n'importe quel monoïde. On doit changer son type pour refléter cela, ainsi que son implémentation pour remplacer ++ par mappend :

applyLog :: (Monoid m) => (a,m) -> (a -> (b,m)) -> (b,m)
applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)

Puisque la valeur accompagnante peut être n'importe quelle valeur monoïdale, plus besoin de penser à un tuple valeur et registre, on peut désormais penser à un tuple valeur et valeur monoïdale. Par exemple, on peut avoir un tuple contenant un nom d'objet et un prix en tant que valeur monoïdale. On utilise le newtype Sum pour s'assurer que les prix sont bien additionnés lorsqu'on opère sur les objets. Voici une fonction qui ajoute des boissons à de la nourriture de cow-boy :

import Data.Monoid

type Food = String
type Price = Sum Int

addDrink :: Food -> (Food,Price)
addDrink "beans" = ("milk", Sum 25)
addDrink "jerky" = ("whiskey", Sum 99)
addDrink _ = ("beer", Sum 30)

On utilise des chaînes de caractères pour représenter la nourriture, et un Int dans un newtype Sum pour tracer le nombre de centimes que quelque chose coûte. Juste un rappel, faire mappend sur des Sum résulte en la somme des valeurs enveloppées :

ghci> Sum 3 `mappend` Sum 9
Sum {getSum = 12}

La fonction addDrink est plutôt simple. Si l'on mange des haricots, elle retourne "milk" ainsi que Sum 25, donc 25 centimes encapsulés dans un Sum. Si l'on mange du bœuf séché, on boit du whisky, et si l'on mange quoi que ce soit d'autre, on boit une bière. Appliquer normalement une fonction à de la nourriture ne serait pas très intéressant ici, mais utiliser applyLog pour donner une nourriture qui a un prix à cette fonction est intéressant :

ghci> ("beans", Sum 10) `applyLog` addDrink
("milk",Sum {getSum = 35})
ghci> ("jerky", Sum 25) `applyLog` addDrink
("whiskey",Sum {getSum = 124})
ghci> ("dogmeat", Sum 5) `applyLog` addDrink
("beer",Sum {getSum = 35})

Du lait coûte 25 centimes, mais si on le prend avec des haricots coûtant 10 centimes, on paie finalement 35 centimes. Il est à présent clair que la valeur attachée n'a pas besoin d'être un registre, elle peut être n'importe quelle valeur monoïdale, et la façon dont deux de ces valeurs sont combinées dépend du monoïde. Quand nous faisions des registres, elles étaient juxtaposées, mais à présent, les nombres sont sommés.

Puisque la valeur qu'addDrink retourne est un tuple (Food, Price), on peut donner ce résultat à addDrink à nouveau, pour qu'elle nous dise ce qu'on devrait boire avec notre boisson et combien le tout nous coûterait. Essayons :

ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
("beer",Sum {getSum = 65})

Ajouter une boisson à de la nourriture pour chien retourne une bière et un prix additionnel de 30 centimes, donc ("beer", Sum 35). Et si l'on utilise applyLog pour donner cela à addDrink, on obtient une autre bière et le résultat est ("beer", Sum 65).

Maintenant qu'on a vu qu'une valeur couplée à un monoïde agissait comme une valeur monadique, examinons l'instance de Monad pour de tels types. Le module Control.Monad.Writer exporte le type Writer w a ainsi que son instance de Monad et quelques fonctions utiles pour manipuler des valeurs de ce type.

D'abord, examinons le type lui-même. Pour attacher un monoïde à une valeur, on doit simplement les placer ensemble dans un tuple. Le type Writer w a est juste un enrobage newtype de cela. Sa définition est très simple :

newtype Writer w a = Writer { runWriter :: (a, w) }

C'est enveloppé dans un newtype afin d'être fait instance de Monad et de séparer ce type des tuples ordinaires. Le paramètre de type a représente le type de la valeur, alors que le paramètre de type w est la valeur monoïdale attachée.

Son instance de Monad est définie de la sorte :

instance (Monoid w) => Monad (Writer w) where
    return x = Writer (x, mempty)
    (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')

Tout d'abord, examinons >>=. Son implémentation est essentiellement identique à applyLog, seulement à présent que notre tuple est enveloppé dans un newtype Writer, on doit l'en sortir en filtrant par motif. On prend la valeur x et applique la fonction f. Cela nous rend une valeur Writer w a et on utilise un filtrage par motif via une expression let dessus. On présente le y comme nouveau résultat et on utilise mappend pour combiner l'ancienne valeur monoïdale avec la nouvelle. On replace ceci et le résultat dans un constructeur Writer afin que notre résultat soit bien une valeur Writer et pas simplement un tuple non encapsulé.

Qu'en est-il de return ? Elle doit prendre une valeur et la placer dans un contexte minimal qui retourne ce résultat. Quel serait un tel contexte pour une valeur Writer ? Si l'on souhaite que notre valeur monoïdale affecte aussi faiblement que possible les autres valeurs monoïdales, il est logique d'utiliser mempty. mempty est l'élément neutre des valeurs monoïdales, comme "" ou Sum 0 ou une chaîne d'octets vide. Quand on utilise mappend avec mempty et une autre valeur monoïdale, le résultat est égal à cette autre valeur. Ainsi, si l'on utilise return pour créer une valeur Writer et qu'on utilise >>= pour donner cette valeur à une fonction, la valeur monoïdale résultante sera uniquement ce que la fonction retourne. Utilisons return sur le nombre 3 quelques fois, en lui attachant un monoïde différent à chaque fois :

ghci> runWriter (return 3 :: Writer String Int)
(3,"")
ghci> runWriter (return 3 :: Writer (Sum Int) Int)
(3,Sum {getSum = 0})
ghci> runWriter (return 3 :: Writer (Product Int) Int)
(3,Product {getProduct = 1})

Puisque Writer n'a pas d'instance de Show, on a dû utiliser runWriter pour convertir nos valeurs Writer en tuples normaux qu'on peut alors afficher. Pour les String, la valeur monoïdale est la chaîne vide. Avec Sum, c'est 0, parce que si l'on ajoute 0 à quelque chose, cette chose est inchangée. Pour Product, le neutre est 1.

L'instance Writer n'a pas d'implémentation de fail, donc si un filtrage par motif échoue dans une notation do, error est appelée.

À présent qu'on a une instance de Monad, on est libre d'utiliser la notation do pour les valeurs Writer. C'est pratique lorsqu'on a plusieurs valeurs Writer et qu'on veut faire quelque chose avec. Comme les autres monades, on peut les traiter comme des valeurs normales et les contextes sont pris en compte pour nous. Dans ce cas, les valeurs monoïdales sont attachées et mappend les unes aux autres et ceci se reflète dans le résultat final. Voici un exemple simple de l'utilisation de la notation do avec Writer pour multiplier des nombres.

import Control.Monad.Writer

logNumber :: Int -> Writer [String] Int
logNumber x = Writer (x, ["Got number: " ++ show x])

multWithLog :: Writer [String] Int
multWithLog = do
    a <- logNumber 3
    b <- logNumber 5
    return (a*b)

logNumber prend un nombre et crée une valeur Writer. Pour le monoïde, on utilise une liste de chaînes de caractères et on donne au nombre une liste singleton qui dit simplement qu'on a ce nombre. multWithLog est une valeur Writer qui multiplie 3 et 5 et s'assure que leurs registres attachés sont inclus dans le registre final. On utilise return pour présenter a*b comme résultat. Puisque return prend simplement quelque chose et le place dans un contexte minimal, on peut être sûr de ne rien avoir ajouté au registre. Voici ce qu'on voit en évaluant ceci :

ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])

Parfois, on veut seulement inclure une valeur monoïdale à partir d'un endroit donné. Pour cela, la fonction tell est utile. Elle fait partie de la classe de types MonadWriter et dans le cas de Writer, elle prend une valeur monoïdale, comme ["This is going on"] et crée une valeur Writer qui présente la valeur factice () comme son résultat, mais avec notre valeur monoïdale attachée. Quand on a une valeur monoïdale qui a un () en résultat, on ne le lie pas à une variable. Voici multWithLog avec un message supplémentaire rapporté dans le registre :

multWithLog :: Writer [String] Int
multWithLog = do
    a <- logNumber 3
    b <- logNumber 5
    tell ["Gonna multiply these two"]
    return (a*b)

Il est important que return (a*b) soit la dernière ligne, parce que le résultat de la dernière ligne d'une expression do est le résultat de l'expression entière. Si l'on avait placé tell à la dernière ligne, () serait le résultat de l'expression do. On aurait perdu le résultat de la multiplication. Cependant, le registre serait le même. Place à l'action :

ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])

L'algorithme d'Euclide est un algorithme qui prend deux nombres et calcule leur plus grand commun diviseur. C'est-à-dire, le plus grand nombre qui divise à la fois ces deux nombres. Haskell contient déjà la fonction gcd, qui calcule exactement ceci, mais implémentons la nôtre avec des capacités de registre. Voici l'algorithme normal :

gcd' :: Int -> Int -> Int
gcd' a b
    | b == 0    = a
    | otherwise = gcd' b (a `mod` b)

L'algorithme est très simple. D'abord, il vérifie si le second nombre est 0. Si c'est le cas, alors le premier est le résultat. Sinon, le résultat est le plus grand commun diviseur du second nombre et du reste de la division du premier par le second. Par exemple, si l'on veut connaître le plus grand commun diviseur de 8 et 3, on suit simplement cet algorithme. Parce que 3 est différent de 0, on doit trouver le plus grand commun diviseur de 3 et 2 (car si l'on divise 8 par 3, il reste 2). Ensuite, on cherche le plus grand commun diviseur de 3 et 2. 2 est différent de 0, on obtient donc 2 et 1. Le second nombre n'est toujours pas 0, alors on lance l'algorithme à nouveau sur 1 et 0, puisque diviser 2 par 1 nous donne un reste de 0. Finalement, puisque le second nombre est 0, alors le premier est le résultat final, c'est-à-dire 1. Voyons si le code est d'accord :

ghci> gcd' 8 3
1

C'est le cas. Très bien ! Maintenant, on veut munir notre résultat d'un contexte, et ce contexte sera une valeur monoïdale agissant comme un registre. Comme auparavant, on utilisera une liste de chaînes de caractères pour notre monoïde. Le type de notre nouvelle fonction gcd' devrait donc être :

gcd' :: Int -> Int -> Writer [String] Int

Il ne reste plus qu'à munir notre fonction de valeurs avec registres. Voici le code :

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
    | b == 0 = do
        tell ["Finished with " ++ show a]
        return a
    | otherwise = do
        tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
        gcd' b (a `mod` b)

La fonction prend deux valeurs Int normales et retourne un Writer [String] Int, c'est-à-dire, un Int avec un registre en contexte. Dans le cas où b vaut 0, plutôt que de donner simplement le a en résultat, on utilise une expression do pour le placer dans une valeur Writer en résultat. On utilise d'abord tell pour rapporter qu'on a terminé, puis return pour présenter a comme résultat de l'expression do. Au lieu de cette expression do, on aurait aussi pu écrire :

Writer (a, ["Finished with " ++ show a])

Cependant, je pense que l'expression do est plus simple à lire. Ensuite, on a le cas où b est différent de 0. Dans ce cas, on écrit qu'on utilise mod pour trouver le reste de la division de a par b. Puis, à la deuxième ligne de l'expression do on appelle récursivement gcd'. Souvenez-vous, gcd' retourne finalement une valeur Writer, il est donc parfaitement valide d'utiliser gcd' b (a `mod` b) dans une ligne d'une expression do.

Bien qu'il puisse être assez utile de tracer l'exécution de notre nouvelle gcd' à la main pour voir comment les registres sont juxtaposés, je pense qu'il sera plus enrichissant de prendre de la perspective et voir ceux-ci comme des valeurs avec un contexte, et ainsi imaginer ce que notre résultat devrait être.

Essayons notre nouvelle fonction gcd'. Son résultat est une valeur Writer [String] Int et si on l'extrait de son newtype, on obtient un tuple. La première composante de cette paire est le résultat. Voyons si c'est le cas :

ghci> fst $ runWriter (gcd' 8 3)
1

Bien ! Qu'en est-il du registre ? Puisqu'il n'est qu'une liste de chaînes de caractères, utilisons mapM_ putStrLn pour afficher ces chaînes à l'écran :

ghci> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1

Je trouve assez génial qu'on ait pu changer notre algorithme ordinaire en un algorithme reportant ce qu'il fait à la volée en changeant simplement les valeurs normales par des valeurs monadiques et en laissant l'implémentation de >>= pour Writer s'occuper des registres pour nous. On peut ajouter un mécanisme de tenue de registre à n'importe quelle fonction. On remplace simplement les valeurs normales par des valeurs Writer, et on remplace l'application de fonction usuelle par >>= (ou par des expressions do si cela augmente la lisibilité).

Quand vous utilisez la monade Writer, il faut être extrêmement prudent avec le choix du monoïde à utiliser, parce qu'utiliser des listes peut s'avérer très lent. C'est parce que les listes utilisent ++ pour mappend, et utiliser ++ pour ajouter quelque chose à la fin d'une liste peut s'avérer très lent si la liste est très longue.

Dans notre fonction gcd', la construction du registre est rapide parce que la concaténation se déroule ainsi :

a ++ (b ++ (c ++ (d ++ (e ++ f))))

Les listes sont des structures de données construites de la gauche vers la droite, et ceci est efficace parce que l'on construit d'abord entièrement la partie de gauche d'une liste, et ensuite on ajoute une liste plus longue à droite. Mais si l'on ne fait pas attention, utiliser la monade Writer peut produire une concaténation comme celle-ci :

((((a ++ b) ++ c) ++ d) ++ e) ++ f

Celle-ci est associée à gauche plutôt qu'à droite. C'est inefficace parce que chaque fois que l'on veut ajouter une partie droite à une partie gauche, elle doit construire la partie gauche en entier du début !

La fonction suivante fonctionne comme gcd', mais enregistre les choses dans le sens inverse. Elle produit d'abord le registre du reste de la procédure, puis ajoute l'étape courante à la fin du registre.

import Control.Monad.Writer

gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
    | b == 0 = do
        tell ["Finished with " ++ show a]
        return a
    | otherwise = do
        result <- gcdReverse b (a `mod` b)
        tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
        return result

Elle effectue l'appel récursif d'abord, et lie le résultat au nom result. Puis, elle ajoute l'étape courante au registre, mais celle-ci vient donc s'ajouter à la fin du registre produit par l'appel récursif. Finalement, elle présente le résultat de l'appel récursif comme résultat final. La voici en action :

ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)
Finished with 1
2 mod 1 = 0
3 mod 2 = 1
8 mod 3 = 2

C'est inefficace parce qu'elle finit par associer les utilisations de ++ à gauche plutôt qu'à droite.

Puisque les listes peuvent parfois être inefficaces quand on concatène de façon répétée, il vaut mieux utiliser une structure de données qui supporte une concaténation toujours efficace. Une liste différentielle est une telle structure de données. Une liste différentielle est similaire à une liste, mais au lieu d'être une liste normale, c'est une fonction qui prend une liste et lui prépose une autre liste. La liste différentielle équivalente à la liste [1, 2, 3] serait la fonction \xs -> [1, 2, 3] ++ xs. Une liste vide normale est [], alors qu'une liste différentielle vide est la fonction \xs -> [] ++ xs.

Le truc cool avec les listes différentielles, c'est qu'elles supportent une concaténation efficace. Quand on concatène deux listes normales avec ++, elle doit traverser la liste de la gauche jusqu'à sa fin pour coller la liste de droite à cet endroit. Mais qu'en est-il avec l'approche des listes différentielles ? Eh bien, concaténer deux listes différentielles peut être fait ainsi :

f `append` g = \xs -> f (g xs)

Souvenez-vous, f et g sont des fonctions qui prennent une liste, et leur prépose quelque chose. Par exemple, si f est la fonction ("dog"++) (qui est juste une autre façon d'écrire \xs -> "dog" ++ xs) et g est la fonction ("meat"++), alors f `append` g crée une nouvelle fonction équivalente à :

\xs -> "dog" ++ ("meat" ++ xs)

Nous avons concaténé deux listes différentielles simplement en en créant une nouvelle fonction qui applique d'abord une liste différentielle sur une liste, puis applique l'autre liste différentielle au résultat.

Créons un emballage newtype pour nos listes différentielles de façon à pouvoir les doter d'une instance de monoïde :

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

Le type que l'on enveloppe est [a] -> [a] parce qu'une liste différentielle est simplement une fonction qui prend une liste et en retourne une autre. Convertir des listes normales en listes différentielles et vice versa est très facile :

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)

fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

Pour créer une liste normale à partir d'une liste différentielle, on fait comme on faisait avant en créant une fonction qui prépose une autre liste. Puisqu'une liste différentielle est une fonction qui prépose une autre liste à la liste qu'elle représente, pour obtenir cette liste, il suffit de l'appliquer à une liste vide !

Voici l'instance de Monoid :

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

Remarquez comme pour ces listes, mempty est juste la fonction id et mappend est simplement la composition de fonctions. Voyons si cela marche :

ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])
[1,2,3,4,1,2,3]

Tip top ! On peut maintenant améliorer l'efficacité de gcdReverse en lui faisant utiliser des listes différentielles plutôt que des listes normales :

import Control.Monad.Writer

gcd' :: Int -> Int -> Writer (DiffList String) Int
gcd' a b
    | b == 0 = do
        tell (toDiffList ["Finished with " ++ show a])
        return a
    | otherwise = do
        result <- gcd' b (a `mod` b)
        tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])
        return result

On a simplement dû changer le type du monoïde de [String] en DiffList String, et changer nos listes normales en listes différentielles avec toDiffList quand on utilisait tell. Voyons si le registre est assemblé correctement :

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34
Finished with 2
8 mod 2 = 0
34 mod 8 = 2
110 mod 34 = 8

On fait gcdReverse 110 34, puis on utilise runWriter pour sortir le résultat du newtype, et on applique snd pour n'obtenir que le registre, puis on applique fromDiffList pour le convertir en une liste normale, et enfin on l'affiche entrée par entrée à l'écran.

Pour vous faire une idée de l'ordre de grandeur de l'amélioration des performances en utilisant les listes différentielles, considérez cette fonction qui décompte à partir d'un nombre jusqu'à zéro, et produit son registre dans le sens inverse, comme gcdReverse, de manière à ce que le registre compte les nombres dans l'ordre croissant :

finalCountDown :: Int -> Writer (DiffList String) ()
finalCountDown 0 = do
    tell (toDiffList ["0"])
finalCountDown x = do
    finalCountDown (x-1)
    tell (toDiffList [show x])

Si on lui donne 0, elle l'écrit simplement dans le registre. Pour tout autre nombre, elle commence d'abord par décompter depuis son prédécesseur, jusqu'à 0 et enfin, ajoute ce nombre au registre. Ainsi, si l'on applique finalCountDown à 100, la chaîne de caractères "100" sera la dernière du registre.

Si vous chargez cette fonction dans GHCi et que vous l'appliquez à un nombre gros, comme 500000, vous verrez qu'elle compte rapidement depuis 0 vers l'avant :

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000
0
1
2
...

Cependant, si on la change pour utiliser des listes normales plutôt que des listes différentielles, de cette manière :

finalCountDown :: Int -> Writer [String] ()
finalCountDown 0 = do
    tell ["0"]
finalCountDown x = do
    finalCountDown (x-1)
    tell [show x]

Et qu'on demande à GHCi de compter :

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

On voit que le décompte est très lent.

Bien sûr, ce n'est pas la façon rigoureuse et scientifique de tester la vitesse de nos programmes, mais on peut déjà voir que dans ce cas, utiliser des listes différentielles commence à fournir des résultats immédiatement alors que pour des listes normales, cela prend une éternité.

Oh, au fait, la chanson Final Countdown d'Europe est maintenant coincée dans votre tête. De rien !

Disons qu'on souhaite modéliser la manipulation d'une pile. Vous avez une pile de choses l'une sur l'autre, et vous pouvez soit ajouter quelque chose au sommet de la pile, soit enlever quelque chose du sommet de la pile. Quand on place quelque chose sur la pile, on dit qu'on l'empile, et quand on enlève quelque chose on dit qu'on le dépile. Si vous voulez quelque chose qui est tout en bas de la pile, il faut d'abord dépiler tout ce qui est au-dessus.

Nous utiliserons une liste pour notre pile et la tête de la liste sera le sommet de la pile. Pour nous aider dans notre tâche, nous créerons deux fonctions : pop et push. pop prend une pile, dépile un élément, et retourne l'élément en résultat ainsi que la nouvelle pile sans cet élément. push prend un élément et une pile et empile l'élément sur la pile. Elle retourne () en résultat, ainsi qu'une nouvelle pile. Voici :

type Stack = [Int]

pop :: Stack -> (Int,Stack)
pop (x:xs) = (x,xs)

push :: Int -> Stack -> ((),Stack)
push a xs = ((),a:xs)

On utilise () comme résultat lorsque l'on empile parce qu'empiler un élément sur la pile n'a pas de résultat intéressant, son travail est simplement de changer la pile. Remarquez que si l'on applique que le premier paramètre de push, on obtient un calcul à états. pop est déjà un calcul à états de par son type.

Écrivons un petit bout de code qui simule une pile en utilisant ces fonctions. On va prendre une pile, empiler 3 et dépiler deux éléments, juste pour voir. Voici :

stackManip :: Stack -> (Int, Stack)
stackManip stack = let
    ((),newStack1) = push 3 stack
    (a ,newStack2) = pop newStack1
    in pop newStack2

On prend une pile stack et on fait push 3 stack, ce qui retourne un tuple. La première composante de cette paire est () et la seconde est la nouvelle pile, qu'on appelle newStack1. Ensuite, on dépile un nombre de newStack1, ce qui retourne un nombre a (qui est 3) et une nouvelle pile qu'on appelle newStack2. Puis, on dépile un nombre de newStack2 et obtient un nombre b et une nouvelle pile newStack3. Le tuple de ce nombre et cette pile est retourné. Essayons :

ghci> stackManip [5,8,2,1]
(5,[8,2,1])

Cool, le résultat est 5 et la nouvelle pile est [8, 2, 1]. Remarquez comme stackManip est elle-même un calcul à états. On a pris plusieurs calculs à états et on les a collés ensemble. Hmm, ça sonne familier.

Le code ci-dessus de stackManip est un peu fastidieux puisqu'on donne manuellement l'état à chaque calcul à états, puis on récupère un nouvel état qu'on donne à nouveau au prochain calcul. Ce serait mieux si, au lieu de donner les piles manuellement à chaque fonction, on pouvait écrire :

stackManip = do
    push 3
    a <- pop
    pop

Eh bien, avec la monade d'états c'est exactement ce qu'on écrira. Avec elle, on peut prendre des calculs à états comme ceux-ci et les utiliser sans se préoccuper de la gestion de l'état manuellement.

Le module Control.Monad.State fournit un newtype qui enveloppe des calculs à états. Voici sa définition :

newtype State s a = State { runState :: s -> (a,s) }

Un State s a est un calcul à états qui manipule un état de type s et retourne un résultat de type a.

Maintenant qu'on a vu ce que sont des calculs à états et comment ils pouvaient être vus comme des valeurs avec des contextes, regardons leur instance de Monad :

instance Monad (State s) where
    return x = State $ \s -> (x,s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State g) = f a
                                    in  g newState

Regardons d'abord return. Le but de return est de prendre une valeur et d'en faire un calcul à états retournant toujours cette valeur. C'est pourquoi on crée une lambda \s -> (x, s). On présente toujours x en résultat du calcul à états et l'état est inchangé, parce que return place la valeur dans un contexte minimal. Donc return crée un calcul à états qui retourne une certaine valeur sans changer l'état.

Qu'en est-il de >>= ? Eh bien, le résultat obtenu en donnant une fonction à un calcul à états par >>= doit être un calcul à états, n'est-ce pas ? On commence donc à écrire le newtype State et une lambda. Cette lambda doit être notre nouveau calcul à états. Mais que doit-elle faire ? Eh bien, on doit extraire le résultat du premier calcul à états d'une manière ou d'une autre. Puisqu'on se trouve dans un calcul à états, on peut donner au calcul à états h notre état actuel s, ce qui retourne une paire d'un résultat et d'un nouvel état : (a, newState). À chaque fois qu'on a implémenté >>=, après avoir extrait le résultat de la valeur monadique, on appliquait la fonction f dessus pour obtenir une nouvelle valeur monadique. Dans Writer, après avoir fait cela et obtenu la nouvelle valeur monadique, on devait ne pas oublier de tenir compte du contexte en faisant mappend entre l'ancienne valeur monoïdale et la nouvelle. Ici, on fait f a et on obtient un nouveau calcul à états g. Maintenant qu'on a un calcul à états et un état (qui s'appelle newState) on applique simplement le calcul à états g à l'état newState. Le résultat est un tuple contenant le résultat final et l'état final !

Ainsi, avec >>=, on colle ensemble deux calculs à états, seulement le second est caché dans une fonction qui prend le résultat du premier. Puisque pop et push sont déjà des calculs à états, il est facile de les envelopper dans un State. Regardez :

import Control.Monad.State

pop :: State Stack Int
pop = State $ \(x:xs) -> (x,xs)

push :: Int -> State Stack ()
push a = State $ \xs -> ((),a:xs)

pop est déjà un calcul à états et push prend un Int et retourne un calcul à états. Maintenant, on peut réécrire l'exemple précédent où l'on empilait 3 sur la pile avant de dépiler deux nombres ainsi :

import Control.Monad.State

stackManip :: State Stack Int
stackManip = do
    push 3
    a <- pop
    pop

Voyez-vous comme on a collé ensemble un empilement et deux dépilements en un calcul à états ? Quand on sort ce calcul de son newtype, on obtient une fonction à laquelle on peut fournir un état initial :

ghci> runState stackManip [5,8,2,1]
(5,[8,2,1])

On n'avait pas eu besoin de lier le premier pop à a vu qu'on n'utilise pas ce a. On aurait pu écrire :

stackManip :: State Stack Int
stackManip = do
    push 3
    pop
    pop

Plutôt cool. Mais et si l'on voulait faire ceci : dépiler un nombre de la pile, puis si ce nombre est 5, l'empiler à nouveau et sinon, empiler 3 et 8 plutôt ? Voici le code :

stackStuff :: State Stack ()
stackStuff = do
    a <- pop
    if a == 5
        then push 5
        else do
            push 3
            push 8

C'est plutôt simple. Lançons-la sur une pile vide.

ghci> runState stackStuff [9,0,2,1,0]
((),[8,3,0,2,1,0])

Souvenez-vous, les expressions do résultent en des valeurs monadiques, et avec la monade State, une expression do est donc une fonction à états. Puisque stackManip et stackStuff sont des calculs à états ordinaires, on peut les coller ensemble pour faire des calculs plus compliqués.

moreStack :: State Stack ()
moreStack = do
    a <- stackManip
    if a == 100
        then stackStuff
        else return ()

Si le résultat de stackManip sur la pile actuelle est 100, on fait stackStuff, sinon on ne fait rien. return () conserve l'état comme il est et ne fait rien.

Le module Control.Monad.State fournit une classe de types appelée MonadState qui contient deux fonctions assez utiles, j'ai nommé get et put. Pour State, la fonction get est implémentée ainsi :

get = State $ \s -> (s,s)

Elle prend simplement l'état courant et le présente en résultat. La fonction put prend un état et crée une fonction à états qui remplace l'état courant par celui-ci :

put newState = State $ \s -> ((),newState)

Avec ces deux fonctions, on peut voir la pile courante ou la remplacer par une toute nouvelle pile. Comme ça :

stackyStack :: State Stack ()
stackyStack = do
    stackNow <- get
    if stackNow == [1,2,3]
        then put [8,3,1]
        else put [9,2,1]

Il est intéressant d'examiner le type qu'aurait >>= si elle était restreinte aux valeurs State :

(>>=) :: State s a -> (a -> State s b) -> State s b

Remarquez que le type de l'état s reste le même, mais le type du résultat peut changer de a en b. Cela signifie que l'on peut coller ensemble des calculs à états dont les résultats sont de différents types, mais le type des états doit être le même. Pourquoi cela ? Eh bien, par exemple, pour Maybe, >>= a ce type :

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b

Il est logique que la monade elle-même, Maybe, ne change pas. Ça n'aurait aucun sens d'utiliser >>= entre deux monades différentes. Eh bien, pour la monade d'états, la monade est en fait State s, donc si ce s était différent, on utiliserait >>= entre deux monades différentes.

Au début de la section, on a vu que générer des nombres aléatoires pouvait parfois sembler bizarre puisque chaque fonction aléatoire prenait un générateur et retourne un nombre aléatoire ainsi qu'un nouveau générateur, qui devait ensuite être utilisé à la place du précédent pour générer de nouveaux nombres aléatoires. La monade d'états rend cela bien plus facile.

La fonction random de System.Random a pour type :

random :: (RandomGen g, Random a) => g -> (a, g)

Signifiant qu'elle prend un générateur aléatoire et produit un nombre aléatoire et un nouveau générateur. On peut voir que c'est un calcul à états, on peut donc l'envelopper dans le constructeur de newtype State et l'utiliser comme une valeur monadique afin que la gestion de l'état soit faite pour nous :

import System.Random
import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a
randomSt = State random

À présent, si l'on souhaite lancer trois pièces (True pour pile, False pour face), on peut faire :

import System.Random
import Control.Monad.State

threeCoins :: State StdGen (Bool,Bool,Bool)
threeCoins = do
    a <- randomSt
    b <- randomSt
    c <- randomSt
    return (a,b,c)

threeCoins est un calcul à états et après avoir pris un générateur aléatoire initial, il le passe au premier randomSt, qui produit un nombre et un nouveau générateur, qui est passé au prochain et ainsi de suite. On utilise return (a, b, c) pour présenter (a, b, c) comme le résultat sans changer le générateur le plus récent. Essayons :

ghci> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)

Alors que nous débutions notre périple vers le sommet du Mont Monade, on a d'abord vu des foncteurs, qui étaient pour les choses sur lesquelles on pouvait mapper. Puis, on a appris qu'il existait des foncteurs améliorés appelés foncteurs applicatifs, qui nous permettaient d'appliquer des fonctions normales sur plusieurs valeurs applicatives ainsi que de prendre une valeur normale et de la placer dans un contexte par défaut. Finalement, on a introduit les monades comme des foncteurs applicatifs améliorés, qui ajoutaient la possibilité de donner ces valeurs avec des contextes à des fonctions normales.

Ainsi, chaque monade est un foncteur applicatif, et chaque foncteur applicatif est un foncteur. La classe de types Applicative a une contrainte de classe telle que notre type doit être une instance de Functor avant de pouvoir devenir une instance d'Applicative. Mais bien que Monad devrait avoir la même contrainte de classe pour Applicative, puisque chaque monade est un foncteur applicatif, elle ne l'a pas, parce que la classe de types Monad a été introduite en Haskell longtemps avant Applicative.

Mais bien que chaque monade soit un foncteur, on n'a pas besoin que son type soit une instance de Functor grâce à la fonction liftM. liftM prend une fonction et une valeur monadique et mappe la fonction sur la valeur. C'est donc comme fmap ! Voici le type de liftM :

liftM :: (Monad m) => (a -> b) -> m a -> m b

Et le type de fmap :

fmap :: (Functor f) => (a -> b) -> f a -> f b

Si un type est à la fois instance de Functor et de Monad et obéit à leurs lois respectives, alors ces deux fonctions doivent être identiques (c'est le cas pour toutes les monades qu'on a vues jusqu'ici). Un peu comme pure et return font la même chose, seulement que la première a une contrainte de classe Applicative alors que l'autre a une contrainte Monad. Testons liftM :

ghci> liftM (*3) (Just 8)
Just 24
ghci> fmap (*3) (Just 8)
Just 24
ghci> runWriter $ liftM not $ Writer (True, "chickpeas")
(False,"chickpeas")
ghci> runWriter $ fmap not $ Writer (True, "chickpeas")
(False,"chickpeas")
ghci> runState (liftM (+100) pop) [1,2,3,4]
(101,[2,3,4])
ghci> runState (fmap (+100) pop) [1,2,3,4]
(101,[2,3,4])

On sait déjà comment fmap fonctionne avec les valeurs Maybe. Et liftM est identique. Pour les valeurs Writer, la fonction est mappée sur la première composante du tuple, qui est le résultat. Faire fmap ou liftM sur un calcul à états résulte en un autre calcul à états, mais son résultat final sera modifié par la fonction passée en argument. Si l'on n'avait pas mappé (+100) sur pop, elle aurait retourné (1,[2,3,4]).

Voici comment liftM est implémentée :

liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = m >>= (\x -> return (f x))

Ou, en notation do :

liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = do
    x <- m
    return (f x)

On donne la valeur monadique m à la fonction, et on applique f à son résultat avant de le retourner dans un contexte par défaut. Grâce aux lois des monades, on a la garantie que le contexte est inchangé, seule la valeur résultante est altérée. On voit que liftM est implémentée sans faire référence à la classe de types Functor. Cela signifie qu'on a pu implémenter fmap (ou liftM, peu importe son nom) en utilisant simplement ce que les monades nous offraient. Ainsi, on peut conclure que les monades sont plus fortes que les foncteurs normaux.

La classe de types Applicative nous permet d'appliquer des fonctions entre des valeurs dans des contextes comme si elles étaient des valeurs normales. Comme cela :

ghci> (+) <$> Just 3 <*> Just 5
Just 8
ghci> (+) <$> Just 3 <*> Nothing
Nothing

Utiliser ce style applicatif rend les choses plutôt faciles. <$> est juste fmap et <*> est une fonction de la classe de types Applicative qui a pour type :

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

C'est donc un peu comme fmap, seulement la fonction elle-même est dans un contexte. Il faut d'une certaine façon l'extraire de ce contexte et la mapper sur la valeur f a, puis restaurer le contexte. Grâce à la curryfication par défaut en Haskell, on peut utiliser la combinaison de <$> et <*> pour appliquer des fonctions qui prennent plusieurs paramètres entre plusieurs valeurs applicatives.

Il s'avère que tout comme fmap, <*> peut aussi être implémentée uniquement avec ce que la classe de types Monad nous donne. La fonction ap est simplement <*>, mais avec une contrainte de classe Monad plutôt qu'Applicative. Voici sa définition :

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
    f <- mf
    x <- m
    return (f x)

mf est une valeur monadique dont le résultat est une fonction. Puisque la fonction est dans un contexte comme la valeur, on récupère la fonction de son contexte et on l'appelle f, puis on récupère la valeur qu'on appelle x et finalement on applique la fonction avec la valeur et on présente le résultat. Voici un exemple rapide :

ghci> Just (+3) <*> Just 4
Just 7
ghci> Just (+3) `ap` Just 4
Just 7
ghci> [(+1),(+2),(+3)] <*> [10,11]
[11,12,12,13,13,14]
ghci> [(+1),(+2),(+3)] `ap` [10,11]
[11,12,12,13,13,14]

On voit à présent que les monades sont plus fortes que les foncteurs applicatifs, puisqu'on peut utiliser les fonctions de Monad pour implémenter celles d'Applicative. En fait, très souvent, lorsqu'un type s'avère être une monade, les gens écrivent d'abord l'instance de Monad, puis créent une instance d'Applicative en disant que pure est return et <*> est ap. De façon similaire, si vous avez une instance de Monad, vous pouvez faire une instance de Functor en disant que fmap est liftM.

La fonction liftA2 est pratique pour appliquer une fonction entre deux valeurs applicatives. Elle est simplement définie comme :

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y

La fonction liftM2 fait la même chose, mais avec une contrainte Monad. Il existe également liftM3, liftM4 et liftM5.

Nous avons vu que les monades étaient plus puissantes que les foncteurs applicatifs et les foncteurs et que bien que toutes les monades soient des foncteurs applicatifs et des foncteurs, elles n'ont pas nécessairement d'instances de Functor et Applicative, et on a donc vu les fonctions équivalentes à celles qu'on utilisait sur nos foncteurs et nos foncteurs applicatifs.

Voici de quoi faire travailler vos neurones : si le résultat d'une valeur monadique est une autre valeur monadique, autrement dit si une valeur monadique est imbriquée dans une autre, peut-on les aplatir en une valeur monadique simple ? Par exemple, si l'on a Just (Just 9), peut-on en faire un Just 9 ? Il s'avère que toute valeur monadique imbriquée peut être aplatie et ceci est une propriété unique des monades. Pour cela, la fonction join existe. Son type est :

join :: (Monad m) => m (m a) -> m a

Ainsi, elle prend une valeur monadique dans une valeur monadique et retourne simplement une valeur monadique, donc en quelque sorte elle l'aplatit. La voici en action sur diverses valeurs Maybe :

ghci> join (Just (Just 9))
Just 9
ghci> join (Just Nothing)
Nothing
ghci> join Nothing
Nothing

La première ligne contient un calcul réussi en résultat d'un calcul réussi, donc ils sont joints en un gros calcul réussi. La deuxième ligne contient un Nothing comme résultat dans un Just. À chaque fois qu'on a eu affaire à des valeurs Maybe auparavant et qu'on voulait en combiner plusieurs, que ce soit avec <*> ou >>=, elles devaient toutes être Just pour que le résultat soit Just. S'il y avait un seul échec parmi elles, le résultat était un échec. Il en va de même ici. À la troisième ligne, on essaie d'aplatir ce qui est déjà un échec, le résultat reste un échec.

Aplatir les listes est intuitif :

ghci> join [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]

Comme vous le voyez, join est juste concat. Pour aplatir une valeur Writer donc le résultat est une valeur Writer, on doit mappend les valeurs monoïdales.

ghci> runWriter $ join (Writer (Writer (1,"aaa"),"bbb"))
(1,"bbbaaa")

La valeur monoïdale extérieure "bbb" vient d'abord, puis "aaa" est juxtaposée. Intuitivement, pour examiner la valeur d'un Writer, il faut que sa valeur monoïdale soit mise au registre d'abord, et seulement ensuite peut-on examiner ce qu'elle contient.

Aplatir des valeurs Either est similaire au cas des valeurs Maybe :

ghci> join (Right (Right 9)) :: Either String Int
Right 9
ghci> join (Right (Left "error")) :: Either String Int
Left "error"
ghci> join (Left "error") :: Either String Int
Left "error"

Si on applique join à un calcul à états dont le résultat est un calcul à états, le résultat est un calcul à états qui lance d'abord le calcul extérieur et ensuite le calcul intérieur. Regardez :

ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0]
((),[10,1,2,0,0,0])

La lambda ici prend un état et place 2 et 1 dans la pile et présente push 10 comme son résultat. Quand cette chose est aplatie avec join et évaluée, elle empile d'abord 2 et 1 puis push 10 est exécuté, empilant un 10 en sommet de pile.

L'implémentation de join est comme suit :

join :: (Monad m) => m (m a) -> m a
join mm = do
    m <- mm
    m

Puisque le résultat de mm est une valeur monadique, on obtient ce résultat et on le place ensuite sur sa propre ligne, comme une valeur monadique. L'astuce ici est que lorsqu'on fait m <- mm, le contexte de la monade en question est pris en compte. C'est pourquoi, par exemple, des valeurs Maybe résultent en des Just seulement si les valeurs intérieures et extérieures sont toutes deux des valeurs Just. Voici à quoi cela ressemblait si mm était fixé à l'avance à la valeur Just (Just 8) :

joinedMaybes :: Maybe Int
joinedMaybes = do
    m <- Just (Just 8)
    m

Peut-être que la chose la plus intéressante à propos de join est que, pour chaque monade, donner une valeur monadique à une fonction avec >>= est équivalent à mapper cette fonction sur la valeur puis utiliser join pour aplatir la valeur monadique imbriquée résultante ! En d'autres termes, m >>= f est toujours égal à join (fmap f m) ! C'est logique quand on y réfléchit. Avec >>=, on donne une valeur monadique à une fonction qui attend une valeur normale et retourne une valeur monadique. Si l'on mappe cette fonction sur la valeur monadique, on a une valeur monadique à l'intérieur d'une valeur monadique. Par exemple, si l'on a Just 9 et la fonction \x -> Just (x + 1). En mappant la fonction sur Just 9, on obtient Just (Just 10)).

Le fait que m >>= f est toujours égal à join (fmap f) est très utile quand on crée nos propres instances de Monad pour certains types parce qu'il est souvent plus facile de voir comment on aplatirait une valeur monadique imbriquée plutôt que de trouver comment implémenter >>=.

La fonction filter est le pain quotidien de la programmation en Haskell (map étant le beurre sur la tartine). Elle prend un prédicat et une liste à filtrer et retourne une nouvelle liste dans laquelle tous les éléments satisfaisant le précidat ont été gardés. Son type est :

filter :: (a -> Bool) -> [a] -> [a]

Le prédicat prend un élément de la liste et retourne une valeur Bool. Et si la valeur Bool retournée était une valeur monadique ? Ouah ! C'est-à-dire, et si elle venait avec son contexte ? Est-ce que cela marcherait ? Par exemple, si chaque valeur True ou False que le prédicat produisait était accompagnée d'une valeur monoïdale, comme ["Accepted the number 5"] ou ["3 is too small"] ? On dirait que ça pourrait marcher. Si c'était le cas, on s'attendrait à ce que la liste résultante vienne également avec un registre combinant tous les registres obtenus en route. Donc, si le Bool retourné par le prédicat vient avec un contexte, on s'attendrait à ce que la liste résultante ait également un contexte attaché, autrement, le contexte de chaque Bool serait perdu.

La fonction filterM de Control.Monad fait exactement ce que l'on souhaite ! Son type est :

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

Le prédicat retourne une valeur monadique dont le résultat est un Bool, mais puisque c'est une valeur monadique, son contexte peut-être n'importe quoi, un possible échec, du non-déterminisme, et encore plus ! Pour s'assurer que le contexte est reflété dans le résultat final, celui-ci est aussi une valeur monadique.

Prenons une liste et gardons seulement les valeurs inférieures à 4. Pour commencer, on va utiliser la fonction filter ordinaire :

ghci> filter (\x -> x < 4) [9,1,5,2,10,3]
[1,2,3]

C'était plutôt simple. Maintenant, créons un prédicat qui, en plus de retourner True ou False, fournisse également un registre de ce qu'il a fait. Bien sûr, on va utiliser la monade Writer à cet effet :

keepSmall :: Int -> Writer [String] Bool
keepSmall x
    | x < 4 = do
        tell ["Keeping " ++ show x]
        return True
    | otherwise = do
        tell [show x ++ " is too large, throwing it away"]
        return False

Plutôt que de seulement retourner un Bool, cette fonction retourne un Writer [String] Bool. C'est un prédicat monadique. Ça sonne classe, non ? Si le nombre est plus petit que 4, on indique qu'on le garde et on return True.

À présent, passons-la à filterM avec une liste. Puisque le prédicat retourne une valeur Writer, la liste résultante sera également une valeur Writer.

ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
[1,2,3]

En examinant le résultat de la valeur Writer résultante, on voit que tout se déroule bien. Maintenant, affichons le registre pour voir ce qu'il s'est passé :

ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
9 is too large, throwing it away
Keeping 1
5 is too large, throwing it away
Keeping 2
10 is too large, throwing it away
Keeping 3

Génial. Donc simplement en fournissant un prédicat monadique à filterM, nous avons pu filtrer une liste en tirant profit du contexte monadique utilisé.

Une astuce Haskell très cool est d'utiliser filterM pour obtenir l'ensemble des parties d'une liste (en imaginant la liste comme un ensemble pour le moment). L'ensemble des parties d'un ensemble est l'ensemble des sous-ensembles de cet ensemble. Si l'on a un ensemble comme [1, 2, 3], l'ensemble de ses parties contient les ensembles suivants :

[1,2,3]
[1,2]
[1,3]
[1]
[2,3]
[2]
[3]
[]

En d'autres termes, obtenir l'ensemble des parties d'un ensemble consiste à trouver toutes les combinaisons possibles de garder ou jeter les éléments de cet ensemble. [2, 3] est comme l'ensemble original, mais on a exclu le nombre 1.

Pour créer une fonction renvoyant l'ensemble des parties d'une liste, on va s'appuyer sur le non-déterminisme. On prend une liste [1, 2, 3] et on regarde son premier élément, qui est 1, et on se demande : devrait-on le garder ou le jeter ? Eh bien, on aimerait faire les deux en réalité. On va donc filtrer une liste à l'aide d'un prédicat qui gardera et jettera chaque élément de façon non déterministe. Voici notre fonction des sous-parties d'un ensemble :

powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs

Quoi, c'est tout ? Yup. On choisit de jeter et de garder chaque élément, peu importe lequel c'est. Nous avons un prédicat non déterministe, donc la liste résultante sera aussi une valeur non déterministe, et donc une liste de listes. Essayons :

ghci> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Il faut un peu y réfléchir pour comprendre ce qui se passe, mais si vous considérez simplement les listes comme des valeurs non déterministes qui ne savent pas ce qu'elles valent et choisissent donc de tout valoir à la fois, c'est un peu plus simple.

L'équivalent monadique de foldl est foldM. Si vous vous souvenez de vos plis de la section sur les plis, vous savez que foldl prend une fonction binaire, un accumulateur initial et une liste à plier, et plie la liste en partant de la gauche avec la fonction binaire pour n'en faire plus qu'une valeur. foldM fait la même chose, mais prend une fonction qui produit une valeur monadique pour plier la liste. Sans surprise, la valeur résultante est également monadique. Le type de foldl est :

foldl :: (a -> b -> a) -> a -> [b] -> a

Alors que foldM a pour type :

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

La valeur que la fonction binaire retourne est monadique, et donc le résultat du pli entier est aussi monadique. Sommons une liste de nombres à l'aide d'un pli :

ghci> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14

L'accumulateur initial est 0, puis 2 est ajouté à l'accumulateur, résultant en une valeur de 2. 8 est ensuite ajouté, résultant en un accumulateur valant 10 et ainsi de suite jusqu'à atteindre la fin, l'accumulateur final étant le résultat.

Et si l'on voulait sommer une liste de nombres avec la condition supplémentaire que si l'un des nombres de la liste est plus grand que 9, tout échoue ? Il semble logique d'utiliser une fonction binaire qui vérifie si le nombre à ajouter est plus grand que 9, échoue le cas échéant, et continue son petit bonhomme de chemin si ce n'est pas le cas. À cause de cette possibilité d'échec additionnelle, faisons retourner à notre fonction un Maybe accumulateur plutôt qu'un accumulateur normal. Voici la fonction binaire :

binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
    | x > 9     = Nothing
    | otherwise = Just (acc + x)

Puisque notre fonction binaire est maintenant une fonction monadique, on ne peut plus utiliser le foldl normal, mais on doit utiliser foldM. Voici :

ghci> foldM binSmalls 0 [2,8,3,1]
Just 14
ghci> foldM binSmalls 0 [2,11,3,1]
Nothing

Excellent ! Puisqu'un des nombres de la liste est plus grand que 9, le tout résulte en Nothing. Plier avec une fonction binaire qui retourne une valeur Writer est aussi cool parce que vous pouvez enregistrer ce que vous voulez pendant que le pli suit son chemin.

Quand nous résolvions le problème de l'implémentation d'une calculatrice NPICalculatrice de notation polonaise inverse, nous avions remarqué qu'elle fonctionnait bien tant que l'entrée était bien formée. Mais s'il se passait quelque chose de travers, notre programme entier plantait. À présent que l'on sait prendre un code existant et le rendre monadique, reprenons notre calculatrice NPI et ajoutons-lui une gestion d'erreur en profitant de la monade Maybe.

Nous avions implémenté notre calculatrice NPI en prenant une chaîne de caractères comme "1 3 + 2 *", en la découpant en mots pour obtenir quelque chose comme ["1","3","+","2","*"], puis en pliant cette liste en commençant avec une pile vide et en utilisant une fonction binaire de pli qui empile les nombres ou manipule ceux au sommet de la pile pour les ajouter ou les diviser, etc.

Ceci était le corps de notre fonction principale :

import Data.List

solveRPN :: String -> Double
solveRPN = head . foldl foldingFunction [] . words

On transformait l'expression en une liste de chaînes de caractères, qu'on pliait avec notre fonction de pli, et il ne nous restait plus qu'un élément dans la pile, qu'on retournait comme réponse. La fonction de pli était :

foldingFunction :: [Double] -> String -> [Double]
foldingFunction (x:y:ys) "*" = (x * y):ys
foldingFunction (x:y:ys) "+" = (x + y):ys
foldingFunction (x:y:ys) "-" = (y - x):ys
foldingFunction xs numberString = read numberString:xs

L'accumulateur du pli était une pile, qu'on représentait comme une liste de valeurs Double. Tandis que la fonction de pli traversait l'expression en NPI, si l'élément en cours était un opérateur, elle prenait deux éléments en haut de la pile, appliquait l'opérateur sur ceux-ci et replaçait le résultat sur la pile. Si l'élément en cours était une chaîne représentant un nombre, elle convertissait cette chaîne en un vrai nombre et retournait une nouvelle pile comme l'ancienne, mais avec ce nombre empilé.

Rendons d'abord notre fonction de pli capable d'échouer gracieusement. Son type va changer de ce qu'il était en :

foldingFunction :: [Double] -> String -> Maybe [Double]

Ainsi, soit elle retournera Just une nouvelle pile, soit elle échouera avec la valeur Nothing.

La fonction reads est comme read, seulement elle retourne une liste avec un unique élément en cas de lecture réussie. Si elle échoue à lire quelque chose, alors elle retourne une liste vide. À part retourner la valeur qu'elle a lue, elle retourne également le morceau de chaîne de caractères qu'elle n'a pas consommé. On va dire qu'il faut qu'elle consomme l'entrée en entier pour que cela marche, et on va créer une fonction readMaybe pour notre convenance. La voici :

readMaybe :: (Read a) => String -> Maybe a
readMaybe st = case reads st of [(x,"")] -> Just x
                                _ -> Nothing

Testons :

ghci> readMaybe "1" :: Maybe Int
Just 1
ghci> readMaybe "GO TO HELL" :: Maybe Int
Nothing

OK, ça a l'air de marcher. Donc, transformons notre fonction de pli en une fonction monadique pouvant échouer :

foldingFunction :: [Double] -> String -> Maybe [Double]
foldingFunction (x:y:ys) "*" = return ((x * y):ys)
foldingFunction (x:y:ys) "+" = return ((x + y):ys)
foldingFunction (x:y:ys) "-" = return ((y - x):ys)
foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)

Les trois premiers cas sont comme les anciens, sauf que la nouvelle pile est enveloppée dans un Just (on a utilisé return pour cela, mais on aurait tout aussi bien pu écrire Just). Dans le dernier cas, on fait readMaybe numberString et on mappe ensuite (:xs) dessus. Donc, si la pile xs est [1.0, 2.0] et si readMaybe numberString résulte en Just 3.0, le résultat est Just [3.0, 1.0, 2.0]. Si readMaybe numberString résulte en Nothing, alors le résultat est Nothing. Essayons la fonction de pli seule :

ghci> foldingFunction [3,2] "*"
Just [6.0]
ghci> foldingFunction [3,2] "-"
Just [-1.0]
ghci> foldingFunction [] "*"
Nothing
ghci> foldingFunction [] "1"
Just [1.0]
ghci> foldingFunction [] "1 wawawawa"
Nothing

Ça a l'air de marcher ! Il est l'heure d'introduire notre nouvelle fonction solveRPN améliorée. Mesdames, mesdemoiselles et messieurs !

import Data.List

solveRPN :: String -> Maybe Double
solveRPN st = do
    [result] <- foldM foldingFunction [] (words st)
    return result

Tout comme avant, on prend une chaîne de caractères et on en fait une liste de mots. Puis, on fait un pli, démarrant avec une pile vide, seulement au lieu d'un foldl normal, on fait un foldM. Le résultat de ce foldM doit être une valeur Maybe contenant une liste (notre pile finale) et cette liste ne doit contenir qu'une valeur. On utilise une expression do pour obtenir cette valeur et on l'appelle result. Si foldM retourne Nothing, le tout vaudra Nothing, parce que c'est comme cela que Maybe fonctionne. Remarquez aussi qu'on filtre par motif dans l'expression do, donc si la liste a plus d'une valeur, ou bien aucune, le filtrage par motif échoue et Nothing est produit. À la dernière ligne, on fait simplement return result pour présenter le résultat du calcul NPI comme le résultat de la valeur Maybe.

Mettons-la à l'essai :

ghci> solveRPN "1 2 * 4 +"
Just 6.0
ghci> solveRPN "1 2 * 4 + 5 *"
Just 30.0
ghci> solveRPN "1 2 * 4"
Nothing
ghci> solveRPN "1 8 wharglbllargh"
Nothing

Le premier échec est dû au fait que la pile finale n'a pas un seul élément, donc le filtrage par motif échoue dans l'expression do. Le deuxième échec a lieu parce que readMaybe retourne Nothing.

Lorsque nous étudiions les lois des monades, nous avions dit que la fonction <=< était comme la composition, mais qu'au lieu de travailler sur des fonctions ordinaires comme a -> b, elle travaillait sur des fonctions comme a -> m b. Par exemple :

ghci> let f = (+1) . (*100)
ghci> f 4
401
ghci> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))
ghci> Just 4 >>= g
Just 401

Dans cet exemple, on a d'abord composé deux fonctions ordinaires, appliqué la fonction résultante à 4, et ensuite on a composé deux fonctions monadiques, et donné Just 4 à la fonction résultante à l'aide de >>=.

Si l'on a tout un tas de fonctions dans une liste, on peut les composer en une unique énorme fonction en utilisant id comme accumulateur initial et . comme fonction binaire. Voici un exemple :

ghci> let f = foldr (.) id [(+1),(*100),(+1)]
ghci> f 1
201

La fonction f prend un nombre et lui ajoute 1, multiplie le résultat par 100 et ajoute 1 à ça. On peut composer des fonctions monadiques de la même façon, seulement au lieu de la composition normale on utilise <=< et au lieu d'id on utilise return. On n'a même pas à remplacer foldr par foldM puisque la fonction <=< s'occupe de gérer la composition de manière monadique.

Quand on s'habituait à la monade des listes dans le chapitre précédentLa monade des listes, on l'utilisait pour trouver si un cavalier pouvait aller d'une position d'un échiquier à une autre en exactement trois mouvements. On avait une fonction nommée moveKnight qui prenait la position du cavalier sur l'échiquier et retournait tous les déplacements possibles au prochain tour. Puis, pour générer toutes les positions possibles après trois mouvements, on a créé la fonction suivante :

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

Et pour vérifier s'il pouvait aller de start à end en trois mouvements, on faisait :

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

En utilisant la composition de fonctions monadiques, on peut créer une fonction comme in3, seulement qu'au lieu de générer toutes les positions possibles du cavalier après trois mouvements, on peut le faire pour un nombre de mouvements arbitraire. Si vous regardez in3, vous voyez qu'on utilise moveKnight trois fois, et à chaque fois, on utilise >>= pour lui donner toutes les positions précédentes. Rendons cela plus général à présent. Voici comment procéder :

import Data.List

inMany :: Int -> KnightPos -> [KnightPos]
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

D'abord, on utilise replicate pour créer une liste contenant x copies de la fonction moveKnight. Puis, on compose monadiquement toutes ces fonctions en une seule, ce qui nous donne une fonction qui prend une position de départ, et déplace le cavalier x fois de façon non déterministe. Il suffit alors de placer la position initiale dans une liste singleton avec return et de la donner à notre fonction.

On peut maintenant changer la fonction canReachIn3 pour être également plus générale :

canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start