N'ayez pas peur des monades

Pour mieux comprendre le concept de monade, on a besoin de deux concepts intermédiaires : les foncteurs et les applicatifs.

1. Fonct-ions vers Fonct-eurs

Une généralisation des fonctions

Dans tout un tas de langages de programmation, on a besoin d’effectuer des calculs sur les éléments d’une liste par exemple. Par exemple, si on veut ajouter 1 à tous les entiers d’une liste, on peut définir la fonction :

inc :: [Int] -> [Int]
inc []     = []
inc (x:xs) = (x + 1) : inc xs

Si on voulait doubler tous les éléments d’une liste, on pourrait définir une fonction comme :

double :: [Int] -> [Int]
double []     = []
double (x:xs) = 2 * x : double xs

Comme, on peut le voir, les deux fonctions font des choses très différentes, mais sont finalement extrêmement semblables. On veut pouvoir généraliser le fait d’appliquer une fonction quelconque à chaque élément de la liste. Ceci nous donne la fonction map ¹, qui prend une fonction de type (a -> b) et l’applique à chaque élément d’une liste d’éléments de type a et renvoie la liste des éléments transformés en type b.

Ce qui nous intéresse, c’est de généraliser encore le fait d’appliquer une fonction à chaque élément d’une structure de données, et pas que les listes.

En Haskell, les structures de données qui permettent ceci sont des foncteurs. Une classe est un foncteur si elle implémente une fonction spéciale : fmap (functor map).

La classe Functor est définie comme ceci :

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Pour les listes, il est assez évident de voir que la fonction fmap est simplement la fonction map. Mais d’autres conteneurs peuvent aussi être des foncteurs. Maybe par exemple, l’est facilement :

instance Functor Maybe where
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

Ceci implique que le résultat reste une erreur s’il y avait une erreur, mais que si on avait une valeur, alors on reste dans le conteneur en ayant changé la valeur par application de la fonction.

On peut bien sûr faire en sorte que nos propres types soient des foncteurs. Si on reprend un autre exemple ² :

data Tree a = Leaf | Node a (Tree a) (Tree a)

Alors, on peut en faire un foncteur en définissant la bonne fonction

instance Functor Tree where
    fmap _ Leaf         = Leaf
    fmap f (Node v l r) = Node (f v) (fmap f l) (fmap f r)

Dans ce cas, on applique la fonction à la valeur de chaque nœud et on répercute ça récursivement dans les sous-arbres.

Une des conséquences de cette abstraction, c’est qu’on peut maintenant écrire des fonctions qui sont génériques pour tous les foncteurs, et donc éviter de la redondance de code. Si on reprend l’exemple de notre fonction inc, elle devient alors :

inc :: Functor f => f Int -> f Int
inc = fmap (+1)

et fonctionne sur tous les foncteurs que l’on a vus !

ghci> inc [1, 2, 5]
[2, 3, 6]
ghci> inc (Just 9)
Just 10
ghci> inc (Node 4 (Node 2 Leaf Leaf) Leaf)
Node 5 (Node 3 Leaf Leaf) Leaf

Les deux règles fondamentales

Bien sûr, ce n’est pas rigolo si on peut faire n’importe quoi avec fmap. Il y a des règles à respecter :

1. d’abord, fmap id = id, Quel que soit le foncteur ;
2. fmap (g . h) = fmap g . fmap h, c’est-à-dire qu’appliquer une composition de fonctions à travers fmap revient à appliquer la première puis la deuxième.

Ces deux règles font qu’il n’y a qu’une seule implémentation de fmap possible pour chaque type de foncteur.

2. D’un argument à plusieurs

On a réussi avec les foncteurs à généraliser le concept d’application d’une fonction à tous les éléments à l’intérieur d’un conteneur.

On va aller encore un peu plus loin : on va chercher à généraliser les fonctions que l’on veut appliquer aux fonctions qui prennent non plus un seul argument, mais plusieurs.

Bien sûr, une solution naïve serait d’avoir des types des foncteurs pour chaque nombre d’arguments. On aurait alors fmap1 = fmap, mais on pourrait définir fmap2 :: (a -> b -> c) -> f a -> f b -> f c et ainsi de suite. Mais ce n’est vraiment pas pratique et on se rend bien compte que ça nous ferait écrire du code redondant.

On va en fait se resservir de la notion de curryfication ³. Une fonction qui prend deux arguments est en réalité une fonction qui prend un argument et renvoie une fonction qui prend un argument qui elle renvoie une valeur.

On a donc besoin de deux nouveaux opérateurs. Un opérateur, que l’on va appeler pure, va transformer une valeur en l’intégrant au conteneur. Le deuxième opérateur, <*>, est une généralisation de l’application de fonction où tous les arguments sont contenus dans des conteneurs.

Comme pour les applications de fonctions standard, l’opérateur <*> est associatif à gauche, c’est-à-dire que :

g <*> x <*> y <*> z = ((g <*> x) <*> y) <*> z

Étendre les foncteurs

On peut donc étendre nos foncteurs par le type applicatif qui implémente ces deux opérateurs. On a ainsi :

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

> L’exemple de Maybe

Le type Maybe, qui est un foncteur, peut être étendu en applicatif avec les définitions suivantes :

instance Applicative Maybe where
    pure :: a -> Maybe a
    pure = Just

    (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
    Nothing  <*> _  = Nothing
    (Just g) <*> mx = fmap g mx

Reprenons ce que font ces opérateurs. Pour encapsuler une valeur dans Maybe (c’est-à-dire pure), il suffit d’utiliser Just.

Ensuite, appliquer une fonction de type Maybe (a -> b) ne fait rien si la fonction est Nothing. Si elle existe, il suffit de la mapper dans son argument avec fmap. On a donc une fonction qui peut échouer qui est appliquée à un argument qui peut échouer et produit un résultat qui peut être un échec.

Un exemple ?

ghci> pure (+) <*> Just 1 <*> Just 5
-- comme on est associatif à gauche, on a en fait
ghci> (pure (+) <*> Just 1) <*> Just 5
-- L'application de <*> donne une fonction qui prend un argument
-- et lui ajoute 1
ghci> pure (+1) <*> Just 5
Just 6

Les deux quatre règles fondamentales

Encore une fois, on doit respecter quelques règles quand on instancie un foncteur pour en faire un applicatif.

1. pure id <*> x = x : quel que soit x, lui appliquer id doit le laisser identique, pure préserve l’identité ;
2. pure (g x) = pure g <*> pure x : pure préserve l’application de fonction ;
3. x <*> pure y = pure (\g -> g y) <*> x : si on applique une fonction avec effet à un argument pur, alors l’ordre d’évaluation n’a pas d’importance ;
4. x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z : l’opérateur <*> est associatif (modulo les types).

Il est important de noter que chacune des instances applicatives respectent également la règle suivante :

fmap g x = pure g <*> x

Notation infixe

Haskell offre la possibilité d’utiliser fmap sous la forme de l’opérateur infixe <$>.

La dernière règle que l’on a donnée permet d’écrire les choses de manière plus compacte. Si on a une fonction g qui prend \(n\) arguments de type a et qu’on a \(n\) paramètres encapsulés dans des foncteurs, on peut écrire :

g <$> x1 <*> x2 <*> ... <*> xn

3. Et maintenant… les monades

Tout ce qu’on a fait jusqu’à présent, c’est généraliser des concepts qu’on connaissait déjà pour éviter d’écrire du code verbeux et/ou répétitif.

Les monades sont encore une généralisation qui permet d’éviter ces problèmes.

Un exemple avec des expressions

Graham Hutton présente un exemple simple pour se rendre compte de la nécessité de l’introduction de ce nouveau concept. Reprenons l’exemple des expressions arithmétiques, simplifié pour n’avoir que des valeurs entières ou des divisions d’expressions.

data Exp = Val Int | Div Exp Exp

On peut alors évaluer les expressions facilement :

eval :: Exp -> Int
eval (Val n)     = n
eval (Div e1 e2) = eval e1 `div` eval e2

Mais ceci ne tient pas compte du fait qu’on pourrait diviser par 0. Le premier réflexe serait alors d’implémenter une division sûre :

divSafe :: Int -> Int -> Maybe Int
divSafe _ 0 = Nothing
divSafe x y = Just (x `div` y)

Mais ceci implique un re-travail de notre évaluateur, qui va devenir d’un coup beaucoup plus verbeux :

eval :: Exp -> Maybe Int
eval (Val n)     = Just n
eval (Div e1 e2) = case eval e1 of
                        Nothing -> Nothing
                        Just x  -> case eval e2 of
                            Nothing -> Nothing
                            Just y  -> divSafe x y

Maintenant, on se souvient que Maybe est un foncteur applicatif, et on pourrait essayer de reformuler l’évaluation en en tirant profit, avec quelque chose comme :

eval :: Exp -> Maybe Int
eval (Val n)     = Just n
eval (Div e1 e2) = pure divSafe <*> eval e1 <*> eval e2

Mais dans ce cas, le type de divSafe n’est pas le bon, on a Int -> Int -> Maybe Int alors qu’il nous faudrait Int -> Int -> Int. Et si on enlève le Maybe, alors on perd notre faculté à gérer les cas avec erreur…

On peut donc en conclure qu’un foncteur applicatif n’est pas suffisant ici pour simplifier l’écriture. Mais si on y regarde de plus près, on voit que l’on effectue deux fois la même chose, à savoir regarder l’issue d’une évaluation, renvoyer Nothing si ça a échoué et le résultat sinon.

On peut en extraire un nouvel opérateur qui fait cette opération :

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
mx >>= f = case mx of
            Nothing -> Nothing
            Just x  -> f x

Avec ce nouvel opérateur, on propage toujours l’erreur si elle est rencontrée et on applique la fonction s’il n’y en a pas.

On peut alors réécrire notre évaluateur beaucoup plus concisément :

eval :: Exp -> Maybe Int
eval (Val n)     = Just n
eval (Div e1 e2) = eval e1 >>= \x -> eval e2 >>= \y -> divSafe x y

Haskell permet aussi d’utiliser une notation plus claire pour l’utilisation de cet opérateur – la do-notation.

eval :: Exp -> Maybe Int
eval (Val n)     = Just n
eval (Div e1 e2) = do
                    x <- eval e1
                    y <- eval e2
                    divSafe x y

Définition de monade

Les foncteurs applicatifs qui sont des monades implémentent les deux fonctions suivantes :

class Applicative m => Monad m where
    return :: a -> m a
    return = pure

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

Les trois règles des monades

Comme d’habitude, il y a des règles à respecter :

1. return x >>= f = f x
2. mx >>= return = mx
3. (mx >>= f) >>= g = mx >>= (\x -> (f x >>= g)) : l’opérateur est associatif.

Vous pouvez trouver quelques exercices simples sur les monades ici