Foncteur, applicative et monade, en Haskell

Voir aussi : video youtube - video peertube - code source

Les foncteurs, les applicatives et les monades sont des structures permettant d’ajouter des fonctionnalités particulières à des types (par exemple, appliquer une fonction à l’intérieur du type, chainer des opérations…). Ces notions sont très puissantes et très classiques en Haskell mais peuvent paraître difficiles au premier abord car elles sont souvent peu connues dans les autres langages et font appel à des notions assez avancées comme la notion de kind (sorte d’un type).

Cet article introduit la notion de sorte, puis présente et illustre les notions de foncteur, d’applicative et de monade. Enfin, il présente comment implémenter ces fonctionnalités pour un nouveau type.

Higher-Kinded Types (HKT)

Exemple avec flat map

En Haskell, la fonction map permet d’appliquer une fonction sur chaque élément d’une liste. Par exemple, la fonction mul2 suivante applique la fonction (*2).

mul2 :: Num a => [a] -> [a]
mul2 xs = map (*2) xs

La fonction mul2 peut donc être utilisée sur toute liste de nombres (plus exactement sur toute liste de a où a est un type de classe Num).

*Main> mul2 [1,2]
[2,4]

En fait, on aimerait bien généraliser notre fonction, non seulement aux listes mais aussi à tous les types “qui contiennent des valeurs”, comme par exemple Maybe (le type qui représente une valeur optionnelle).

C’est ce que permet la classe Functor, avec la fonction fmap.

mul2F :: (Num a, Functor f) => f a -> f a
mul2F xs = fmap (*2) xs

Ainsi, notre fonction mul2F ne prend plus une liste de a pour retourner une liste de a mais elle prend un f a pour retourner un f a. Ici, f est un paramètre de type et doit être un Functor (et donc implémenter une fonction fmap). Par exemple, les listes sont des foncteurs :

*Main> mul2F [1,2]
[2,4]

Ainsi que les Maybe :

*Main> mul2F (Just 21)
Just 42

Sorte d’un type

Intuitivement, la sorte est le type d’un type. Haskell supporte les types de sorte supérieure (HKT).

Un type “classique” comme Int est un type concret, représenté par le symbole *.

*Main> :kind Int
Int :: *

Le type Maybe est un constructeur de types (pour rappel, on peut le définir par data Maybe a = Just a | Nothing).

*Main> :kind Maybe
Maybe :: * -> *

Ainsi Maybe Int est un type concret (on appelle Maybe avec le paramètre Int, comme pour une fonction mais avec des types).

*Main> :kind Maybe Int
Maybe Int :: *

De même, la liste est un constructeur de types et la liste de Int est un type concret.

*Main> :kind []
[] :: * -> *

*Main> :kind [Int]
[Int] :: *

Les sortes s’appliquent également pour les contraintes de types.

*Main> :kind Num
Num :: * -> Constraint

*Main> :kind Num Int
Num :: Constraint

Enfin, Haskell gére les sortes supérieures, c’est-à-dire qu’un constructeur peut prendre en paramètre un constructeur (de la même façon qu’une fonction peut prendre en paramètre une fonction).

Ainsi, Functor prend en paramètre un constructeur de types et retourne une contrainte de type.

*Main> :kind Functor
Functor :: (* -> *) -> Constraint

Si on rapproche cela de la section précédente, on comprend désormais, d’après leur type, que map fonctionne sur des listes et que fmap fonctionne sur n’importe quel foncteur.

*Main> :type map
map :: (a -> b) -> [a] -> [b]

*Main> :type fmap
fmap :: Functor f => (a -> b) -> f a -> f b

Notion de foncteur, d’applicative et de monade

Il s’agit ici de présenter les idées principales et leur utilisation en Haskell. On ne s’attardera donc pas sur les propriétés associées à ces notions ni sur les différences qu’elles peuvent avoir avec leur équivalent dans d’autres contextes (théorie des catégories, langage OCaml…).

Foncteur

En Haskell, un foncteur est un type “à l’intérieur duquel on peut appliquer une fonction”. Les foncteurs sont implémentés via la classe de type Functor, qui définit essentiellement la fonction fmap.

*Main> :info Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
  	-- Defined in ‘GHC.Base’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
...

On notera que la fonction fmap existe également sous forme d’opérateur (<$>) et que de nombreux types Haskell instancient Functor (par exemple, [], Maybe…).

Par exemple, on peut appliquer la fonction (*3) sur les éléments d’une liste ou d’un Maybe :

*Main> (*3) <$> [1,2]
[3,6]

Main> (*3) <$> Just 2 
Just 6

Applicative

Une applicative (ou foncteur applicatif) est un foncteur mais où la fonction à appliquer est également “à l’intérieur du type”. Concrètement, une applicative permet de “fmapper” des fonctions à plusieurs paramètres.

En Haskell, les applicatives sont implémentées via la classe Applicative.

*Main> :info Applicative
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  GHC.Base.liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}
  	-- Defined in ‘GHC.Base’
instance Applicative [] -- Defined in ‘GHC.Base’
instance Applicative Maybe -- Defined in ‘GHC.Base’
...

On notera qu’une applicative est obligatoirement un foncteur (ceci est vérifié à la compilation). En simplifiant, une applicative a une fonction pure, qui “met dans l’applicative”, et un opérateur <*> (appelé “ap”), qui “continue et combine les évaluations”.

Une applicative permet d’appliquer des fonctions à plusieurs paramètres. Par exemple, si on veut appliquer (*) sur des listes, c’est-à-dire appliquer une fonction à 2 paramètres de type liste :

*Main> (*) <$> [1,2] <*> [3]
[3,6]

*Main> (*) <$> [1,2] <*> [3,4]
[3,4,6,8]

On remarquera qu’on obtient bien une liste résultat, contenant toutes les combinaisons sur les paramètres.

De même pour des Maybe :

*Main> (*) <$> Just 2 <*> Just 21
Just 42

*Main> (*) <$> Nothing <*> Just 21
Nothing

Monade

Enfin, une monade est un type qui permet d’enchainer des actions. Haskell propose la classe Monad suivante.

*Main> :info Monad
class Applicative m => Monad (m :: * -> *) where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a
  {-# MINIMAL (>>=) #-}
  	-- Defined in ‘GHC.Base’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
...

Ainsi, une monade est obligatoirement une applicative, et donc également un foncteur. Elle définit principalement l’opérateur >>= (appelé “bind”) qui prend une monade et une action, et retourne la monade résultat.

La fonction return correspond exactement à la fonction pure. L’opérateur >> (appelé “then”) peut être vu comme >>=, c’est-à-dire un enchainement d’actions, mais où on ignore le “résultat” de la première monade.

Ainsi, on peut appliquer la fonction (*3) à la liste [1,2] avec l’opérateur >>= (mais en retournant une monade) :

*Main> [1,2] >>= \x -> return (x*3)
[3,6]

*Main> [1,2] >>= return . (*3)
[3,6]

L’intérêt est qu’on peut facilement chainer les actions. Par exemple, si on veut multiplier par 3 puis ajouter 4 :

*Main> [1,2] >>= return . (*3) >>= return . (+4)
[7,10]

Jusqu’ici, on a utilisé la monade liste mais on peut utliser beaucoup d’autres types monades, par exemple Maybe :

*Main> Just 1 >>= return . (*3) >>= return . (+4)
Just 7

L’opérateur >>= peut devenir un peu compliqué à utiliser, notamment pour des opérations à plusieurs paramètres.

*Main> [1,2] >>= \x -> [2,3] >>= \y -> return (x*y)
[2,3,4,6]

*Main> Just 2 >>= \x -> Just 21 >>= \y -> return (x*y)
Just 42

Pour éviter cela, Haskell propose une syntaxe alternative, la “notation do” :

*Main> :{
*Main| do
*Main|   x <- [1,2]
*Main|   y <- [3,4]
*Main|   return (x*y)
*Main| :}
[3,4,6,8]

*Main> do { x <- Just 2 ; y <- Just 21 ; return (x*y) }
Just 42

La notion de monade est essentielle en Haskell, notamment parce qu’elle permet d’implémenter des entrées-sorties (avec IO) mais également des états mutables (State), des références mutables (IORef), des parseurs (ReadP), etc.

Définir un type foncteur, applicative ou monade

Cette dernière section illustre comment instancier les classes précédentes pour un nouveau type (ici une implémentation de liste) et ainsi rendre ce type utilisable avec n’importe quelle fonction Haskell définie sur des foncteurs, applicatives ou monades.

Attention, l’implémentation du type et de ses instances doit respecter certaines propriétés (associativité, élément neutre, etc), mais ceci n’est pas détaillé ici.

Type List

On définit le type List suivant, de façon très classique :

data List a
    = Nil
    | Cons a (List a)
    deriving (Show)

List est donc d’un constructeur de types, de sorte * -> *.

Foncteur

Pour pouvoir utiliser notre type List comme un foncteur, il suffit d’instancier la classe Functor et de définir la fonction fmap.

instance Functor List where
    -- fmap :: (a -> b) -> List a -> List b
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)
    fmap f Nil = Nil

Ici, la fonction fmap consiste à déconstruire/reconstruire récursivement la liste tout en appliquant la fonction f sur ses éléments. On peut alors maintenant “fmapper” sur notre type List.

*Main> (*3) <$> Cons 1 (Cons 2 Nil)
Cons 3 (Cons 6 Nil)

Applicative

De même, on instancie Applicative :

instance Applicative List where
    -- pure :: a -> List a
    pure x = Cons x Nil

    -- (<*>) :: List (a -> b) -> List a -> List b
    (Cons f fs) <*> xs =
        let ys = fs <*> xs
        in concatList (f <$> xs) ys
    Nil <*> _ = Nil

concatList :: List a -> List a -> List a
concatList (Cons x xs) ys = Cons x (concatList xs ys)
concatList Nil ys = ys

Pour la fonction pure, rien de compliqué : il suffit de construire une liste avec le paramètre donné.

Pour l’opérateur <*>, l’implémentation est plus compliquée : il faut déconstruire/reconstruire récursivement la liste de fonctions en fmappant ces fonctions sur la liste de valeurs et en concaténant les résultats en une seule liste.

*Main> (*) <$> Cons 1 (Cons 2 Nil) <*> Cons 3 (Cons 4 Nil)
Cons 3 (Cons 4 (Cons 6 (Cons 8 Nil)))

Monade

Enfin, pour la classe Monad, l’implémentation de l’opérateur >>= suit le même principe que pour <*> : déconstruire/reconstruire récursivement en appliquant la fonction et en concaténant le résultat.

instance Monad List where
    -- (>>=) :: List a -> (a -> List b) -> List b
    (Cons x xs) >>= f =
        concatList (f x) (xs >>= f)
    Nil >>= _ = Nil

On peut alors utiliser les opérateurs des monades et la notation do, sur notre type List.

*Main> Cons 1 (Cons 2 Nil) >>= return . (*3) >>= return . (+4)
Cons 7 (Cons 10 Nil)

*Main> do { x <- Cons 1 (Cons 2 Nil) ; y <- Cons 3 (Cons 4 Nil) ; return (x*y) }
Cons 3 (Cons 4 (Cons 6 (Cons 8 Nil)))

Ainsi que n’importe quelle fonction définie sur des monades, par exemple sequence :

*Main> :type sequence
sequence :: Monad m => [m a] -> m [a]

*Main> sequence [Cons 1 (Cons 2 Nil), Cons 3 (Cons 4 Nil)]
Cons [1,3] (Cons [1,4] (Cons [2,3] (Cons [2,4] Nil)))

*Main> sequence [[1,2], [3,4]]
[[1,3],[1,4],[2,3],[2,4]]

Conclusion

Haskell supporte la notion de sorte, c’est-à-dire le type d’un type, et même les types de sorte supérieure. Ceci permet d’implémenter des structures comme les foncteurs, les applicatives et les monades. En pratique, ces structures sont très utiles et très utilisées en Haskell, ce qui sera détaillé dans de prochains articles.