Une introduction aux monades : le type Maybe

Considérons le type Maybe contenant peut être une valeur:

import Prelude hiding (map,Nothing,Just,Maybe, (>>=),Functor,Applicative)
data Maybe a = Just a | Nothing

Une fonction retournant un élément du type Maybe a peut échouer, et retourner Nothing, ou renvoyer une valeur du type a encapsulée dans Just a. On pourrait donc imaginer une fonction safeHead retournant peut être la tête d’une liste:

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x

Comme souvent en Haskell, il est intéressant de raisonner en terme de fonctions. Ainsi, il est utile de voir une fonction retournant Maybe a comme un calcul pouvant échouer. Essayons d’écrire une fonction ajoutant 1 au premier élément d’une liste d’entiers, s’il existe:

addOne :: [Int] -> Maybe Int
addOne l = case safeHead l of
  Nothing -> Nothing
  Just x -> Just (x + 1)

Nous pouvons généraliser cette fonction en implémentant une fonction d’ordre supérieur qui nous permettrait d’appliquer une fonction sur le contenu d’un Maybe s’il existe:

maybeMap :: (a -> b) -> Maybe a -> Maybe b
maybeMap f Nothing = Nothing
maybeMap f (Just x) = Just (f x)

Ainsi, addOne s’écrirait:

addOne' l = maybeMap (+1) (safeHead l)

maybeMap permet d’appliquer une fonction réussissant toujours au résultat d’une fonction pouvant échouer. Considérons maintenant deux listes et supposons que l’on veuille faire la somme de leur têtes si elles sont non vide. Une première implémentation serait la suivante :

safeAdd :: [Int] -> [Int] -> Maybe Int
safeAdd lX lY = case (headX,headY) of
     (Just x,Just y) -> Just (x + y)
     otherwise       -> Nothing
  where headX = safeHead lX
        headY = safeHead lY

{- Ou en utilisant maybeMap -}
safeAdd' [] lY = Nothing
safeadd' lX lY = case safeHead lX of
  Just x    -> maybeMap (+x) (safeHead lY)
  otherwise -> Nothing

Nous sommes donc obligés d’établir un pattern matching sur les résultats des deux appels à safeHead pour récupérer les valeurs présentes dans les Just pour en faire la somme que l’on réencapsule dans un Just. Généralisons cela par la fonction maybeApply, identique à maybeMap à la diférence que son premier argument est encapsulé dans Maybe.

maybeApply :: Maybe (a -> b) -> Maybe a -> Maybe b
maybeApply Nothing _ = Nothing
maybeApply _ Nothing = Nothing
maybeApply (Just f) (Just x) = Just (f x)

{- Ou en utilisant maybeMap -}
maybeApply' Nothing _ = Nothing
maybeApply' (Just f) maybeX = maybeMap f maybeX

La réecriture de safeAdd peut donc se faire à l’aide de maybeMap et de maybeApply:

safeAdd'' :: [Int] -> [Int] -> Maybe Int
safeAdd'' lX lY  = maybeApply f (safeHead lY)
  where f :: Maybe (Int -> Int)
        f = maybeMap (+) (safeHead lX)

Super ! Nous pouvons donc combiner des fonctions pouvant échouer et des fonctions réussissant toujours. Cependant, il seraît utile de pouvoir chaîner des calculs pouvant échouer. Supposons que l’on souhaite écrire une fonction retournant le premier élément d’une liste s’il est négatif (et Nothing si ce n’est pas le cas, ou que la liste est vide).

negativeHead :: [Int] -> Maybe Int
negativeHead [] = Nothing
negativeHead (x:_)
  | x < 0     = Just x
  | otherwise = Nothing

Chaîner des calculs se fait avec l’opérateur suivant. Le membre de gauche est le résultat d’un calcul pouvant échouer, le membre de droite prenant en argument l’éventuel résultat et pouvant échouer également. Si le terme de gauche échoue, tout le calcul échoue. Dans le cas contraire, cela dépend du terme de droite.

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x

Supposons que l’on décompose negativeHead en deux fonctions. La première retourne peut être le premier élément de la liste (safeHead), le second prenant en argument une valeur et retournant peut être cette valeur, si elle est négative:

negativeVal :: Int -> Maybe Int
negativeVal x
   | x < 0     = Just x
   | otherwise = Nothing

Nous souhaitons donc chaîner negativeVal à la suite de safeHead, ce qui s’écrit de la manière suivante:

negativeHead' :: [Int] -> Maybe Int
negativeHead' l = safeHead l >>= negativeVal

Sublime non ?

Exercices

Considérons la fonction join permettant “d’aplatir” une pile de Maybe.

join :: Maybe (Maybe a) -> Maybe a
join Nothing = Nothing
join (Just x) = x

Fournir une implémentation de (>>=) en utilisant join.

Nous avons étudié, dans ce papier, comment implémenter maybeApply en utilisant maybeMap. Réaliser l’opération inverse.

Généralisation

Considérons un type f :: * -> * (ou type “conteneur”, comme Maybe). Il est intéressant de voir f comme un type de calcul. Nous pouvons, par exemple, imaginer les types de calcul suivant :

Les calculs pouvant échouer, Maybe a (défini ici).
Les calculs non déterministes (pouvant retourner plusieurs valeurs) : ce sont les fonctions retournant des listes [a].

Il en existe beaucoup d’autres, et nous en étudierons certains plus en détails dans une autre section. Dans les classes de types suivantes, il est utile de remplacer f par Maybe, et ainsi voir le parallèle avec le reste de la section.

Le type f est un foncteur, s’il est possible d’appliquer une fonction pure sur son contenu.

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

La fonction fmap généralise la fonction map à des types autres que les listes.

Un foncteur est dit applicatif si est possible d’appliquer une fonction contenue cette fois dans un foncteur. Il est également nécessaire de pouvoir construire un foncteur à partir de n’importe quelle valeur.

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

L’opérateur (<*>) généralise la fonction maybeApply à tous les foncteurs applicatifs.

Une monade permet de chaîner les calculs : il est possible de “sortir” le résultat d’un calcul pour le passer en argument à un autre.

class (Applicative f) => Monad f where
  (>>=) :: f a -> (a -> f b) -> f b

Exercice

Les fonctions retournant une liste de valeurs peuvent être vues comme un calcul retournant plusieurs réponses possibles. Écrire les instances de Functor, Applicative et Monad pour ce type de calcul.

Indice : pour implémenter l >>= f, supposer que l’on a plusieurs valeurs possibles (l :: [a]) et une fonction qui, à chacune de ces valeurs possibles, retourne une liste de résultats possibles également (f :: a -> [b]).