Apprendre Haskell vous fera le plus grand bien !

Dans cette section, nous allons nous intéresser aux foncteurs applicatifs, qui sont des foncteurs gonflés aux hormones, représentés en Haskell par la classe de types Applicative, située dans le module Control.Applicative.

Comme vous le savez, les fonctions en Haskell sont curryfiées par défaut, ce qui signifie qu'une fonction qui semble prendre plusieurs paramètres en prend en fait un seul et retourne une fonction qui prend le prochain paramètre, et ainsi de suite. Si une fonction a pour type a -> b -> c, on dit généralement qu'elle prend deux paramètres et retourne un c, mais en réalité, elle prend un a et retourne une fonction b -> c. C'est pourquoi on peut appeler une fonction en faisant f x y ou bien (f x) y. Ce mécanisme nous permet d'appliquer partiellement des fonctions en les appelant avec trop peu de paramètres, ce qui résulte en des fonctions que l'on peut passer à d'autres fonctions.

Jusqu'ici, lorsqu'on mappait des fonctions sur des foncteurs, on mappait généralement des fonctions qui ne prenaient qu'un paramètre. Mais que se passe-t-il lorsqu'on souhaite mapper *, qui prend deux paramètres, sur un foncteur ? Regardons quelques exemples concrets. Si l'on a Just 3 et que l'on fait fmap (*) (Just 3), qu'obtient-on ? En regardant l'implémentation de l'instance de Functor de Maybe, on sait que si c'est une valeur Just something, elle applique la fonction sur le something à l'intérieur du Just. Ainsi, faire fmap (*) (Just 3) retourne Just ((*) 3), qui peut être écrit Just (* 3) en utilisant une section. Intéressant ! On obtient une fonction enveloppée dans un Just !

ghci> :t fmap (++) (Just "hey")
fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])
ghci> :t fmap compare (Just 'a')
fmap compare (Just 'a') :: Maybe (Char -> Ordering)
ghci> :t fmap compare "A LIST OF CHARS"
fmap compare "A LIST OF CHARS" :: [Char -> Ordering]
ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]
fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]

Si l'on mappe compare, qui a pour type (Ord a) => a -> a -> Ordering sur une liste de caractères, on obtient une liste de fonctions ayant pour type Char -> Ordering, parce que la fonction compare est partiellement appliquée sur les caractères de la liste. Ce n'est pas une liste de fonctions (Ord a) => a -> Ordering, parce que le premier a appliqué était un Char et donc le deuxième a doit également être un Char.

On voit qu'en mappant des fonctions à plusieurs paramètres sur des foncteurs, on obtient des foncteurs qui contiennent des fonctions. Que peut-on faire de ceux-ci ? Pour commencer, on peut mapper sur ceux-ci des fonctions qui prennent en paramètre une fonction, parce que ce qui est dans le foncteur sera donné à la fonction mappée comme paramètre.

ghci> let a = fmap (*) [1,2,3,4]
ghci> :t a
a :: [Integer -> Integer]
ghci> fmap (\f -> f 9) a
[9,18,27,36]

Mais si l'on a une valeur fonctorielle Just (3 *) et une autre valeur fonctorielle Just 3, et qu'on souhaite sortir la fonction de Just (3 *) pour la mapper sur Just 5 ? Avec des foncteurs normaux, on est bloqué, parce qu'ils ne supportent que la mappage de fonctions normales sur des foncteurs. Même lorsqu'on a mappé \f -> f 9 sur un foncteur qui contenait une fonction, on ne mappait qu'une fonction normale sur celui-ci. Mais fmap ne nous permet pas de mapper une fonction qui est dans un foncteur sur un autre foncteur. On pourrait filtrer par motif sur le constructeur Just pour récupérer la fonction, puis la mapper sur Just 5, mais on voudrait une solution plus générale et abstraite à ce problème, qui fonctionnerait pour tous les foncteurs.

Je vous présente la classe de types Applicative. Elle réside dans le module Control.Applicative et définit deux méthodes, pure et <*>. Elle ne fournit pas d'implémentation par défaut pour celles-ci, il faut donc les définir toutes deux nous-même si l'on veut faire de quelque chose un foncteur applicatif. La classe est définie ainsi :

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

Ces trois petites lignes de définition nous disent beaucoup de choses ! Commençons par la première ligne. Elle débute la définition de la classe Applicative et introduit une contrainte de classe. Elle dit que si l'on veut faire d'un constructeur de types une instance d'Applicative, il doit d'abord être membre de Functor. C'est pourquoi, si l'on sait qu'un constructeur de type est membre d'Applicative, alors c'est aussi un Functor, et on peut donc utiliser fmap sur lui.

La première méthode qu'elle définit est appelée pure. Sa déclaration de type est pure :: a -> f a. f joue le rôle de notre instance de foncteur applicatif. Puisqu'Haskell a un très bon système de types, et puisqu'une fonction ne peut que prendre des paramètres et retourner une valeur, on peut dire beaucoup de choses avec une déclaration de type, et ceci n'est pas une exception. pure prend une valeur de n'importe quel type, et retourne un foncteur applicatif encapsulant cette valeur en son intérieur. Quand on dit en son intérieur, on se réfère à nouveau à l'analogie de la boîte, bien qu'on ait vu qu'elle ne soit pas toujours la plus à même d'expliquer ce qu'il se trame. La déclaration a -> f a est tout de même plutôt descriptive. On prend une valeur et on l'enveloppe dans un foncteur applicatif.

Une autre façon de penser à pure consiste à dire qu'elle prend une valeur et la met dans un contexte par défaut (ou pur) - un contexte minimal qui retourne cette valeur.

La fonction <*> est très intéressante. Sa déclaration de type est f (a -> b) -> f a -> f b. Cela ne vous rappelle rien ? Bien sûr, fmap :: (a -> b) -> f a -> f b. C'est un peu un fmap amélioré. Alors que fmap prend une fonction et un foncteur, et applique cette fonction à l'intérieur du foncteur, <*> prend un foncteur contenant une fonction et un autre foncteur, et d'une certaine façon extrait la fonction du premier foncteur pour la mapper sur l'autre foncteur. Quand je dis extrait, je veux en fait presque dire exécute puis extrait, peut-être même séquence. On verra pourquoi bientôt.

Regardons l'implémentation de l'instance d'Applicative de Maybe.

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

Encore une fois, de la définition de la classe, on voit que le f qui joue le rôle du foncteur applicatif doit prendre un type concret en paramètre, donc on écrit instance Applicative Maybe where plutôt que instance Applicative (Maybe a) where.

Tout d'abord, pure. On a dit précédemment qu'elle était supposée prendre quelque chose et l'encapsuler dans un foncteur applicatif. On a écrit pure = Just, parce que les constructeurs de valeurs comme Just sont des fonctions normales. On aurait pu écrire pure x = Just x.

Ensuite, on a la définition de <*>. On ne peut pas extraire de fonction d'un Nothing, parce qu'il ne contient rien. Donc si l'on essaie d'extraire une fonction d'un Nothing, le résultat est Nothing. Si vous regardez la définition de classe d'Applicative, vous verrez qu'il y a une classe de contrainte Functor, qui signifie que les deux paramètres de <*> sont des foncteurs. Si le premier paramètre n'est pas un Nothing, mais un Just contenant une fonction, on veut mapper cette fonction sur le second paramètre. Ceci prend également en compte le cas où le second paramètre est Nothing, puisque faire fmap sur un Nothing retourne Nothing.

Donc, pour Maybe, <*> extrait la fonction de la valeur de gauche si c'est un Just et la mappe sur la valeur de droite. Si n'importe lequel des paramètres est Nothing, le résultat est Nothing.

Ok, cool, super. Testons cela.

ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 10
Just 13
ghci> pure (+3) <*> Just 9
Just 12
ghci> Just (++"hahah") <*> Nothing
Nothing
ghci> Nothing <*> Just "woot"
Nothing

On voit que faire pure (+3) ou Just (+3) est équivalent dans ce cas. Utilisez pure quand vous utilisez des valeurs Maybe dans un contexte applicatif (i.e. quand vous les utilisez avec <*>), sinon utilisez Just. Les quatre premières lignes entrées montrent comment la fonction extraite est mappée, mais dans ces exemples, elle aurait tout aussi bien pu être mappée immédiatement sur les foncteurs. La dernière ligne est intéressante parce qu'on essaie d'extraire une fonction d'un Nothing et de le mapper sur quelque chose, ce qui résulte en un Nothing évidemment.

Avec des foncteurs normaux, on peut juste mapper une fonction sur un foncteur, et on ne peut plus récupérer ce résultat hors du foncteur de manière générale, même lorsque le résultat est une fonction appliquée partiellement. Les foncteurs applicatifs, quant à eux, permettent d'opérer sur plusieurs foncteurs avec la même fonction. Regardez ce bout de code :

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

Que se passe-t-il là ? Regardons, étape par étape. <*> est associatif à gauche, ce qui signifie que pure (+) <*> Just 3 <*> Just 5 est équivalent à (pure (+) <*> Just 3) <*> Just 5. Tout d'abord, la fonction + est mise dans un foncteur, qui est dans ce cas une valeur Maybe. Donc, au départ, on a pure (+) qui est égal à Just (+). Ensuite, Just (+) <*> Just 3 a lieu. Le résultat est Just (3+). Ceci à cause de l'application partielle. Appliquer la fonction + seulement sur 3 résulte en une fonction qui prend un paramètre, et lui ajoute 3. Finalement, Just (3+) <*> Just 5 est effectuée, ce qui résulte en Just 8.

N'est-ce pas génial !? Les foncteurs applicatifs et le style applicatif d'écrire pure f <*> x <*> y <*> … nous permettent de prendre une fonction qui attend des paramètres qui ne sont pas nécessairement enveloppés dans des foncteurs, et d'utiliser cette fonction pour opérer sur des valeurs qui sont dans des contextes fonctoriels. La fonction peut prendre autant de paramètres qu'on le souhaite, parce qu'elle est partiellement appliquée étape par étape, à chaque occurrence de <*>.

Cela devient encore plus pratique et apparent si l'on considère le fait que pure f <*> x est égal à fmap f x. C'est une des lois des foncteurs applicatifs. Nous les regarderons plus en détail plus tard, pour l'instant, on peut voir intuitivement que c'est le cas. Pensez-y, ça tombe sous le sens. Comme on l'a dit plus tôt, pure place une valeur dans un contexte par défaut. Si l'on place une fonction dans un contexte par défaut, et qu'on l'extrait de ce contexte pour l'appliquer à une valeur dans un autre foncteur applicatif, on a fait la même chose que de juste mapper cette fonction sur le second foncteur applicatif. Plutôt que d'écrire pure f <*> x <*> y <*> …, on peut écrire fmap f x <*> y <*> …. C'est pourquoi Control.Applicative exporte une fonction <$> qui est simplement fmap en tant qu'opérateur infixe. Voici sa définition :

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

En utilisant <$>, le style applicatif devient brillant, parce qu'à présent, si l'on veut appliquer une fonction f sur trois foncteurs applicatifs, on peut écrire f <$> x <*> y <*> z. Si les paramètres n'étaient pas des foncteurs applicatifs, mais des valeurs normales, on aurait écrit f x y z.

Regardons cela de plus près. On a une valeur Just "johntra" et une valeur Just "volta", et on veut joindre les deux en une String dans un foncteur Maybe. On fait cela :

ghci> (++) <$> Just "johntra" <*> Just "volta"
Just "johntravolta"

Avant qu'on se penche là-dessus, comparez la ligne ci-dessus avec celle-ci :

ghci> (++) "johntra" "volta"
"johntravolta"

Génial ! Pour utiliser une fonction sur des foncteurs applicatifs, parsemez quelques <$> et <*> et la fonction opérera sur des foncteurs applicatifs et retournera un foncteur applicatif.

Quand on fait (++) <$> Just "johntra" <*> Just "volta", (++), qui a pour type (++) :: [a] -> [a] -> [a] est tout d'abord mappée sur Just "johntra", résultant en une valeur comme Just ("johntra"++) ayant pour type Maybe ([Char] -> [Char]). Remarquez comme le premier paramètre de (++) a été avalé et les a sont devenus des Char. À présent, Just ("johntra"++) <*> Just "volta" est exécuté, ce qui sort la fonction du Just et la mappe sur Just "volta", retournant Just "johntravolta". Si l'une de ces deux valeurs était un Nothing, le résultat serait Nothing.

Jusqu'ici, on a seulement regardé Maybe dans nos exemples, et vous vous dites peut-être que les foncteurs applicatifs sont juste pour les Maybe. Il y a beaucoup d'autres instances d'Applicative, alors découvrons en plus !

Les listes (ou plutôt, le constructeur de types listes, []) sont des foncteurs applicatifs. Quelle surprise ! Voici l'instance d'Applicative de [] :

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

Plus tôt, on a dit que pure prenait des valeurs, et les plaçait dans un contexte par défaut. En d'autres mots, dans un contexte minimal qui retourne cette valeur. Le contexte minimal pour les listes serait une liste vide, [], mais la liste vide représente l'absence de valeurs, donc elle ne peut pas contenir l'élément qu'on passe à pure. C'est pourquoi pure prend un élément, et le place dans une liste singleton. De manière similaire, le contexte minimal du foncteur applicatif Maybe aurait été Nothing, mais comme il représentait l'absence de valeurs, pure était implémenté avec Just.

ghci> pure "Hey" :: [String]
["Hey"]
ghci> pure "Hey" :: Maybe String
Just "Hey"

Qu'en est-il de <*> ? Si on imagine le type de <*> si elle était limitée aux listes, ce serait (<*>) :: [a -> b] -> [a] -> [b]. On l'implémente à l'aide d'une liste en compréhensionJe suis une liste en compréhension. <*> doit d'une certaine façon extraire la fonction de son paramètre de gauche, et la mapper sur son paramètre de droite. Mais ici, la liste de gauche peut contenir zéro, une ou plusieurs fonctions. La liste de droite peut elle aussi contenir plusieurs valeurs. C'est pourquoi on utilise une liste en compréhension pour piocher dans les deux listes. On applique toutes les fonctions possibles de la liste de gauche sur toutes les valeurs possibles de la liste de droite. La liste résultante contient toutes les combinaisons possibles d'application d'une fonction de la liste de gauche sur une valeur de la liste de droite.

ghci> [(*0),(+100),(^2)] <*> [1,2,3]
[0,0,0,101,102,103,1,4,9]

La liste de gauche contient trois fonctions, et la liste de droite contient trois valeurs, donc la liste résultante contient neuf éléments. Chaque fonction de la liste de gauche est appliquée à chaque valeur de la liste de droite. Si l'on a une liste de fonctions qui prennent deux paramètres, on peut les appliquer entre deux listes.

ghci> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

Puisque <*> est associative à gauche, [(+), (*)] <*> [1, 2] est exécuté en premier, résultant en une liste équivalente à [(1+), (2+), (1*), (2*)], parce que chaque fonction à gauche est appliquée sur chaque valeur de droite. Puis, [(1+),(2+),(1*),(2*)] <*> [3,4] est exécuté, produisant le résultat final.

Utiliser le style applicatif avec les listes est fun ! Regardez :

ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]

À nouveau, remarquez qu'on a utilisé une fonction normale qui prend deux chaînes de caractères entre deux foncteurs applicatifs à l'aide des opérateurs applicatifs appropriés.

Vous pouvez imaginer les listes comme des calculs non déterministes. Une valeur comme 100 ou "what" peut être vue comme un calcul déterministe qui ne renvoie qu'un seul résultat, alors qu'une liste [1, 2, 3] peut être vue comme un calcul qui ne peut pas se décider sur le résultat qu'il doit avoir, et nous présente donc tous les résultats possibles. Donc, quand vous faites quelque chose comme (+) <$> [1, 2, 3] <*> [4, 5, 6], vous pouvez imaginer ça comme la somme de deux calculs non déterministes avec +, qui produit ainsi un nouveau calcul non déterministe encore moins certain de son résultat.

Le style applicatif sur les listes est souvent un bon remplaçant des listes en compréhension. Dans le deuxième chapitre, on souhaitait connaître tous les produits possibles de [2, 5, 10] et [8, 10, 11], donc on a fait :

ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]
[16,20,22,40,50,55,80,100,110]

On pioche simplement dans deux listes et on applique la fonction à toutes les combinaisons d'éléments. Cela peut être fait dans le style applicatif :

ghci> (*) <$> [2,5,10] <*> [8,10,11]
[16,20,22,40,50,55,80,100,110]

Cela me paraît plus clair, parce qu'il est plus simple de voir qu'on appelle seulement * entre deux calculs non déterministes. Si l'on voulait tous les produits possibles de deux listes supérieurs à 50, on ferait :

ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]
[55,80,100,110]

Il est facile de voir comment pure f <*> xs est égal à fmap f xs sur les listes. pure f est juste [f], et [f] <*> xs appliquera chaque fonction de la liste de gauche à chaque valeur de la liste de droite, mais puisqu'il n'y a qu'une fonction à gauche, c'est comme mapper.

Une autre instance d'Applicative qu'on a déjà rencontrée est IO. Voici comment son instance est implémentée :

instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)

Puisque pure ne fait que mettre des valeurs dans un contexte minimal qui puisse toujours renvoyer ce résultat, il est sensé que pure soit juste return, parce que c'est exactement ce que fait return : elle crée une action I/O qui ne fait rien, mais retourne la valeur passée en résultat, sans rien écrire sur le terminal ni écrire dans un fichier.

Si <*> était spécialisée pour IO, elle aurait pour type (<*>) :: IO (a -> b) -> IO a -> IO b. Elle prendrait une action I/O qui retourne une fonction en résultat, et une autre action I/O, et retournerait une action I/O à partir de ces deux, qui, lorsqu'elle serait exécutée, effectuerait d'abord la première action pour obtenir la fonction, puis effectuerait la seconde pour obtenir une valeur, et retournerait le résultat de la fonction appliquée à la valeur. On utilise la syntaxe do pour l'implémenter ici. Souvenez-vous, la syntaxe do prend plusieurs actions I/O et les colle les unes aux autres, ce qui est exactement ce que l'on veut ici.

Avec Maybe et [], on pouvait imaginer que <*> extrayait simplement une fonction de son paramètre de gauche et l'appliquait d'une certaine façon sur son paramètre de droite. Avec IO, l'extraction est toujours de la partie, mais on a également une notion d'ordonnancement, parce qu'on prend deux actions I/O et qu'on les ordonne, en les collant l'une à l'autre. On doit extraire la fonction de la première action I/O, mais pour pouvoir l'extraire, il faut exécuter l'action.

Considérez ceci :

myAction :: IO String
myAction = do
    a <- getLine
    b <- getLine
    return $ a ++ b

C'est une action I/O qui demande à l'utilisateur d'entrer deux lignes, et retourne en résultat ces deux lignes concaténées. Ceci est obtenu en collant deux actions I/O getLine ensemble avec un return, afin que le résultat soit a ++ b. Une autre façon d'écrire cela en style applicatif serait :

myAction :: IO String
myAction = (++) <$> getLine <*> getLine

Ce qu'on faisait précédemment, c'était créer une action I/O qui appliquait une fonction entre les résultats de deux actions I/O, et ici c'est pareil. Souvenez-vous, getLine est une action I/O qui a pour type getLine :: IO String. Quand on utilise <*> entre deux foncteurs applicatifs, le résultat est un foncteur applicatif, donc tout va bien.

Le type de l'expression (++) <$> getLine <*> getLine est IO String, ce qui signifie que cette expression est une action I/O comme une autre, qui contient également une valeur résultante, comme toutes les actions I/O. C'est pourquoi on peut faire :

main = do
    a <- (++) <$> getLine <*> getLine
    putStrLn $ "The two lines concatenated turn out to be: " ++ a

Si jamais vous vous retrouvez en train de lier des actions I/O à des noms, puis à faire return sur l'application d'une fonction à ces noms, considérez utiliser le style applicatif, qui sera probablement plus concis et simple.

Une autre instance d'Applicative est (->) r, autrement dit les fonctions. Elles sont rarement utilisées en style applicatif, à moins que vous ne fassiez du golf avec votre code, mais elles sont tout de même d'intéressants foncteurs applicatifs, regardons donc comment leur instance est implémentée.

instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

Lorsqu'on encapsule une valeur dans un foncteur applicatif avec pure, le résultat retourné doit être cette valeur. Il nous faut un contexte minimal retournant cette valeur. C'est pourquoi, dans l'instance des fonctions, pure prend une valeur, et crée une fonction qui ignore le paramètre qu'elle reçoit pour retourner plutôt cette valeur-là. Le type de pure si elle était spécialisée pour l'instance (->) r serait pure :: a -> (r -> a).

ghci> (pure 3) "blah"
3

Grâce à la curryfication, l'application des fonctions est associative à gauche, on peut donc omettre les parenthèses.

ghci> pure 3 "blah"
3

L'implémentation pour cette instance de <*> est un peu énigmatique, il vaut donc mieux regarder comment l'on utilise les fonctions en foncteurs applicatifs en style applicatif.

ghci> :t (+) <$> (+3) <*> (*100)
(+) <$> (+3) <*> (*100) :: (Num a) => a -> a
ghci> (+) <$> (+3) <*> (*100) $ 5
508

Appeler <*> avec deux foncteurs applicatifs retourne un foncteur applicatif, donc utilisé sur deux fonctions elle renvoie une fonction. Que se passe-t-il donc ici ? Quand on fait (+) <$> (+3) <*> (*100), on crée une fonction qui utilise + sur les résultats de (+3) et de (*100), et retourne cela. Pour montrer un exemple réel, quand on fait (+) <$> (+3) <*> (*100) $ 5, (+3) et (*100) sont appliquées sur 5, retournant 8 et 500. Puis + est appelée sur 8 et 500, retournant 508.

ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5
[8.0,10.0,2.5]

De même ici. On crée une fonction qui appelle la fonction \x y z -> [x, y, z] sur les résultats de (+3), (*2) et (/2). Le 5 est donné à chacune de ces trois fonctions, puis \x y z -> [x, y, z] est appelée avec ces trois résultats.

Vous pouvez imaginer les fonctions comme des boîtes qui contiennent leur résultat à venir, donc faire k <$> f <*> g crée une fonction qui appellera k sur les résultats à venir de f et g. Quand on fait (+) <$> Just 3 <*> Just 5, on utilise + sur des valeurs qui peuvent être là ou non, ce qui retourne donc une valeur qui peut être là ou non. Quand on fait (+) <$> (+10) <*> (+5), on utilise + sur une valeur future de (+10) et (+5), et le résultat sera aussi une valeur future qui ne sera produite que lorsqu'on appellera la fonction avec un paramètre.

On utilise peu les fonctions comme des foncteurs applicatifs, mais c'est tout de même intéressant. Ce n'est pas très important pour vous de comprendre comment l'instance de (->) r d'Applicative fonctionne, donc ne désespérez pas si vous ne le saisissez pas dès maintenant. Essayez de jouer avec le style applicatif pour améliorer votre intuition des fonctions en tant que foncteurs applicatifs.

Une instance d'Applicative que l'on n'a jamais rencontrée auparavant est ZipList, et elle réside dans Control.Applicative.

Il s'avère qu'il y a plusieurs façons pour une liste d'être un foncteur applicatif. L'une est celle qu'on a déjà vue, qui dit qu'appeler <*> sur une liste et une liste de valeurs retourne une liste de toutes les combinaisons possibles d'application d'une fonction de la liste de gauche sur une valeur de la liste de droite. Si l'on fait [(+3),(*2)] <*> [1,2], (+3) est appliquée à la fois sur 1 et sur 2, et (*2) est également appliquée avec 1 et 2, ce qui nous donne une liste à quatre éléments, [4, 5, 2, 4].

Cependant, [(+3),(*2)] <*> [1,2] pourrait aussi fonctionner de manière à ce que la première fonction de la liste de gauche soit appliquée avec la première valeur de la liste de droite, la deuxième fonction avec la deuxième valeur, et ainsi de suite. Cela retournerait une liste à deux valeurs, [4, 4]. Vous pouvez l'imaginer comme [1 + 3, 2 * 2].

Puisqu'un type ne peut pas avoir deux instances de la même classe de types, le type ZipList a est introduit, et il a pour seul constructeur ZipList qui ne prend qu'un seul champ, de type liste. Voici son instance :

instance Applicative ZipList where
        pure x = ZipList (repeat x)
        ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

<*> fait juste ce qu'on a dit. Elle applique la première fonction avec la première valeur, la deuxième fonction avec la deuxième valeur, etc. Cela est réalisé avec zipWith (\f x -> f x) fs xs. La liste résultante sera aussi longue que la plus courte des deux listes, parce que c'est ce que fait zipWith.

pure est également intéressante ici. Elle prend une valeur, et la met dans une liste qui contient cette valeur un nombre infini de fois. pure "haha" retourne ZipList (["haha", "haha", "haha", …. C'est peut-être un peu déroutant, puisqu'on a dit que pure devait mettre une valeur dans un contexte minimal qui retournait cette valeur. Et vous vous dites sûrement qu'une liste infinie est difficilement minimale. Mais cela a du sens pour les listes zippées, parce qu'elle doit produire cette valeur à chaque position. Cela permet aussi de satisfaire la loi disant que pure f <*> xs doit être égal à fmap f xs. Si pure 3 ne retournait que ZipList [3], pure (*2) <*> ZipList [1, 5, 10] retournerait ZipList [2], parce que la liste retournée par zipWith est aussi longue que la plus courte des deux. Alors que si l'on zippe une liste finie à une liste infinie, la longueur de la liste résultante sera celle de la liste finie.

Que font donc les listes zippées dans le style applicatif ? Voyons cela. Oh, le type ZipList a n'a pas d'instance de Show, il faut donc utiliser getZipList pour récupérer une liste normale à partir d'une liste zippée.

ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]
[101,102,103]
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]
[101,102,103]
ghci> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2]
[5,3,3,4]
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"
[('d','c','r'),('o','a','a'),('g','t','t')]

En plus de zipWith, la bibliothèque standard a des fonctions comme zipWith3, zipWith4, jusqu'à 7. zipWith prend une fonction à deux paramètres et zippe deux listes avec cette fonction. zipWith3 prend une fonction à trois paramètres et zippe trois listes à l'aide de celle-ci, et ainsi de suite. En utilisant des listes zippées avec un style applicatif, on n'a pas besoin d'avoir une fonction zip différente pour chaque nombre de listes à zipper. On utilise simplement le style applicatif pour zipper ensemble un nombre arbitraire de listes avec une fonction, c'est plutôt cool.

Control.Applicative définit une fonction nommée liftA2, qui a pour type liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c. Elle est définie ainsi :

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

Rien de spécial, elle applique juste une fonction entre deux foncteurs applicatifs, encapsulant le style applicatif auquel on s'était habitué. On observe cette fonction pour la raison qu'elle démontre clairement en quoi les foncteurs applicatifs sont plus puissants que les foncteurs ordinaires. Avec des foncteurs ordinaires, on peut seulement mapper des fonctions sur un foncteur. Avec des foncteurs applicatifs, on peut appliquer une fonction entre plusieurs foncteurs. Il est aussi intéressant d'imaginer le type de cette fonction comme (a -> b -> c) -> (f a -> f b -> f c). Quand on regarde de cette façon, on voit que liftA2 prend une fonction binaire normale, et la promeut en une fonction binaire sur deux foncteurs.

Voici un concept intéressant : on peut prendre deux foncteurs applicatifs, et les combiner en un foncteur applicatif qui contient en lui les résultats de ces deux foncteurs applicatifs, sous forme d'une liste. Par exemple, on a Just 3 et Just 4. Imaginons que ce deuxième a une liste singleton en lui, puisque c'est très simple à réaliser :

ghci> fmap (\x -> [x]) (Just 4)
Just [4]

Ok, donc disons qu'on a Just 3 et Just [4]. Comment obtenir Just [3, 4] ? Facile.

ghci> liftA2 (:) (Just 3) (Just [4])
Just [3,4]
ghci> (:) <$> Just 3 <*> Just [4]
Just [3,4]

Souvenez-vous, : est la fonction qui prend un élément, une liste, et retourne une nouvelle liste qui a cet élément en tête. À présent qu'on a Just [3, 4], pourrait-on combiner ceci avec Just 2 pour produire Just [2, 3, 4] ? Bien sûr. Il semble qu'on puisse combiner n'importe quel nombre de foncteurs applicatifs en un foncteur applicatif qui contient une liste de tous les résultats. Essayons d'implémenter une fonction qui prend une liste de foncteurs applicatifs et retourne un foncteur applicatif qui contienne une liste en résultat. On l'appellera sequenceA.

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

Ah, de la récursivité ! Tout d'abord, regardons le type. Elle transforme une liste de foncteurs applicatifs en un foncteur applicatif avec une liste. Ainsi, on peut voir apparaître notre cas de base. Si on veut transformer une liste vide en un foncteur applicatif retournant une liste, eh bien il suffit de mettre la liste vide dans un contexte minimal applicatif. Vient ensuite la récursion. Si on a une liste avec une tête et une queue (souvenez-vous, x est un foncteur applicatif, xs une liste de ceux-ci), on appelle sequenceA sur la queue pour obtenir un foncteur applicatif qui contient une liste. On n'a plus qu'à préposer la valeur contenue dans le foncteur x à cette liste, et voilà !

Ainsi, si l'on fait sequenceA [Just 1, Just 2], c'est comme (:) <$> Just 1 <*> sequenceA [Just 2]. C'est égal à (:) <$> Just 1 <*> ((:) <$> Just 2 <*> sequenceA []). Ah ! On sait que sequenceA [] est simplement Just [], donc cette expression se réduit en (:) <$> Just 1 <*> ((:) <$> Just 2 <*> Just []), puis en (:) <$> Just 1 <*> Just [2] et finalement en Just [1,2] !

Un autre moyen d'implémenter sequenceA est à l'aide d'un pli. Souvenez-vous, presque toute fonction parcourant une liste d'éléments en accumulant un résultat peut être implémentée comme un pli.

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA = foldr (liftA2 (:)) (pure [])

On approche la liste par la droite avec un accumulateur initial égal à pure []. On fait listA2 (:) entre l'accumulateur et le dernier élément de la liste, ce qui retourne un foncteur applicatif qui contient une liste singleton. Puis l'on fait liftA2 (:) sur le nouveau dernier élément et l'accumulateur, et ainsi de suite, jusqu'à ce qu'il ne reste plus que l'accumulateur, contenant la liste des résultats des foncteurs applicatifs.

Testons notre fonction sur quelques foncteurs applicatifs.

ghci> sequenceA [Just 3, Just 2, Just 1]
Just [3,2,1]
ghci> sequenceA [Just 3, Nothing, Just 1]
Nothing
ghci> sequenceA [(+3),(+2),(+1)] 3
[6,5,4]
ghci> sequenceA [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]
[]

Ah ! Plutôt cool. Quand on l'utilise sur des valeurs Maybe, sequenceA crée une valeur Maybe avec tous les résultats dans une liste. Si l'une des valeurs est Nothing, alors le résultat est Nothing. C'est utile lorsque vous avez une liste de valeurs Maybe, et que vous ne vous intéressez à ses résultats que s'ils sont tous différents de Nothing.

Quand on l'utilise avec des fonctions, sequenceA prend une liste de fonctions et retourne une fonction qui retourne une liste. Dans notre exemple, on a créé une fonction qui prend un nombre en paramètre et appliquait chaque fonction d'une liste sur ce nombre, retournant la liste des résultats. sequenceA [(+3), (+2), (+1)] 3 appellera (+3) avec 3, (+2) avec 3 et (+1) avec 3, et retourne tous ces résultats sous forme de liste.

Faire (+) <$> (+3) <*> (*2) créera une fonction qui prend un paramètre, le donne à la fois à (+3) et à (*2), et appelle + avec ces deux résultats. Dans la même veine, il est normal que sequenceA [(+3), (*2)] crée une fonction qui prend un paramètre, et le donne à toutes les fonctions de la liste. Plutôt que d'appeler + sur le résultat de ces fonctions, une combinaison de : et de pure [] est utilisée pour rassembler ces résultats en une liste, qui est le résultat de cette fonction.

Utiliser sequenceA est cool quand on a une liste de fonctions et qu'on veut leur donner la même entrée et voir une liste des résultats. Par exemple, si l'on a un nombre et qu'on se demande s'il satisfait tous les prédicats d'une liste. Un moyen de faire serait le suivant :

ghci> map (\f -> f 7) [(>4),(<10),odd]
[True,True,True]
ghci> and $ map (\f -> f 7) [(>4),(<10),odd]
True

Souvenez-vous, and prend une liste de booléens et ne retourne True que s'ils sont tous True. Un autre moyen de faire ceci, avec sequenceA :

ghci> sequenceA [(>4),(<10),odd] 7
[True,True,True]
ghci> and $ sequenceA [(>4),(<10),odd] 7
True

sequenceA [(>4),(<10),odd] crée une fonction qui prendra un nombre et le donnera à tous les prédicats de la liste [(>4),(<10),odd], et retournera une liste de booléens. Elle transforme une liste ayant pour type (Num a) => [a -> Bool] en une fonction ayant pour type (Num a) => a -> [Bool]. Plutôt joli, hein ?

Parce que les listes sont homogènes, toutes les fonctions de la liste doivent avoir le même type, évidemment. Vous ne pouvez pas avoir une liste comme [ord, (+3)], parce qu'ord prend un caractère et retourne un nombre, alors que (+3) prend un nombre et retourne un nombre.

Quand on l'utilise avec [], sequenceA prend une liste de listes et retourne une liste de listes. Hmm, intéressant. Elle crée en fait des listes contenant toutes les combinaisons possibles des éléments. Par exemple, voici ceci réalisé avec sequenceA puis avec une liste en compréhension :

ghci> sequenceA [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> [[x,y] | x <- [1,2,3], y <- [4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> sequenceA [[1,2],[3,4]]
[[1,3],[1,4],[2,3],[2,4]]
ghci> [[x,y] | x <- [1,2], y <- [3,4]]
[[1,3],[1,4],[2,3],[2,4]]
ghci> sequenceA [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
ghci> [[x,y,z] | x <- [1,2], y <- [3,4], z <- [5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]

C'est peut-être un peu dur à saisir, mais en jouant un peu avec, vous verrez comment ça marche. Mettons qu'on fasse sequenceA [[1,2],[3,4]]. Pour voir ce qu'il se passe, utilisons la définition sequenceA (x:xs) = (:) <$> x <*> sequenceA xs de sequenceA et son cas de base sequenceA [] = pure []. Vous n'êtes pas obligé de suivre cette évaluation, mais cela peut vous aider si vous avez du mal à imaginer comment sequenceA fonctionne sur des listes de listes, car ça peut être un peu gratiné.

• On commence avec sequenceA [[1,2],[3,4]]
• Ceci est évalué en (:) <$> [1,2] <*> sequenceA [[3,4]]
• En développant le sequenceA, on obtient (:) <$> [1,2] <*> ((:) <$> [3,4] <*> sequenceA [])
• On a atteint le cas de base, cela donne donc (:) <$> [1,2] <*> ((:) <$> [3,4] <*> [[]])
• On évalue maintenant la partie (:) <$> [3,4] <*> [[]], qui va utiliser : sur toutes les valeurs possibles de la liste de gauche (3 et 4 sont possibles) et avec chaque valeur possible de la liste de droite (seule [] est possible), ce qui donne [3:[], 4:[]], autrement dit [[3],[4]]. On a donc (:) <$> [1,2] <*> [[3],[4]]
• Maintenant, : est utilisée sur toutes les valeurs possibles de la liste de gauche (1 et 2) avec chaque valeur possible de la liste de droite ([3] et [4]), ce qui donne [1:[3], 1:[4], 2:[3], 2:[4]], qui est juste [[1,3],[1,4],[2,3],[2,4]

Faire (+) <$> [1,2] <*> [4,5,6] retourne un calcul non déterministe x + y où x prend toute valeur de [1, 2] et y prend toute valeur de [4, 5, 6]. On représente ceci comme une liste contenant tous les résultats possibles. De façon similaire, quand on fait sequence [[1,2],[3,4],[5,6],[7,8]], le résultat est un calcul non déterministe [x, y, z, w], où x prend toute valeur de [1, 2], y prend toute valeur de [3, 4] et ainsi de suite. Pour représenter le résultat de ce calcul non déterministe, on utilise une liste, dans laquelle chaque élément est une des listes possibles. C'est pourquoi le résultat est une liste de listes.

Quand on l'utilise avec des actions I/O, sequenceA est équivalent à sequence ! Elle prend une liste d'actions I/O et retourne une action I/O qui exécutera chacune de ces actions et aura pour résultat une liste des résultats de ces actions I/O. Ceci parce que, pour changer une valeur [IO a] en une valeur IO [a], c'est-à-dire créer une action I/O qui retourne une liste de tous les résultats, il faut ordonnancer les actions I/O afin qu'elles soient effectuées l'une après l'autre lorsque l'évaluation sera forcée. On ne peut en effet pas obtenir le résultat d'une action I/O sans l'exécuter.

ghci> sequenceA [getLine, getLine, getLine]
heyh
ho
woo
["heyh","ho","woo"]

Comme les foncteurs ordinaires, les foncteurs applicatifs viennent avec quelques lois. La plus importante est celle qu'on a déjà mentionnée, qui dit que pure f <*> x = fmap f x. En exercice, vous pouvez prouver cette loi pour quelques-uns des foncteurs applicatifs vus dans ce chapitre. Les autres lois des foncteurs applicatifs sont :

• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <*> pure y = pure ($ y) <*> u

On ne va pas les regarder en détail pour l'instant, parce que cela prendrait trop de pages et serait probablement ennuyeux, mais si vous vous sentez d'attaque, regardez-les et voyez si elles tiennent pour certaines instances.

En conclusion, les foncteurs applicatifs ne sont pas seulement intéressants, mais également utiles, parce qu'ils nous permettent de combiner différents calculs, comme les entrées-sorties, les calculs non déterministes, les calculs pouvant échouer, etc. en utilisant le style applicatif. Simplement en utilisant <$> et <*>, on peut utiliser des fonctions ordinaires pour opérer uniformément sur n'importe quel nombre de foncteurs applicatifs, et profiter de la sémantique de chacun d'entre eux.

Jusqu'ici, nous avons appris comment créer nos propres types de données algébriques en utilisant le mot-clé data. On a aussi appris comment donner des synonymes à des types avec le mot-clé type. Dans cette section, on va regarder comment créer de nouveaux types à partir de types existants, et pourquoi on voudrait pouvoir faire cela.

Dans la section précédente, on a vu qu'il y a plusieurs manières de définir un foncteur applicatif pour le type des listes. L'une d'elles fait prendre à <*> chaque fonction d'une liste passée en paramètre de gauche et la lui fait appliquer à chaque valeur d'une liste passée en paramètre de droite, retournant toutes les combinaisons possibles d'application de fonctions de la liste de gauche sur des valeurs de la liste de droite.

ghci> [(+1),(*100),(*5)] <*> [1,2,3]
[2,3,4,100,200,300,5,10,15]

La deuxième manière consiste à prendre la première fonction de la liste à gauche de <*>, et de l'appliquer à la première valeur de la liste de droite, puis prendre la deuxième fonction à gauche et l'appliquer à la deuxième valeur à droite, et ainsi de suite. Finalement, c'est comme zipper les deux listes ensemble. Mais les listes sont déjà des instances d'Applicative, alors comment les faire aussi instances d'Applicative de l'autre manière ? Si vous vous souvenez, on a dit que le type ZipList a était introduit pour cette raison, avec un seul constructeur de valeurs, ZipList, contenant un seul champ. On place la liste qu'on enveloppe dans ce champ. Ainsi, ZipList est fait instance d'Applicative, de manière à ce que si l'on souhaite utiliser des listes comme foncteurs applicatifs de la manière zip, on ait juste à envelopper la liste dans le constructeur ZipList, puis, une fois les calculs terminés, là sortir avec getZipList :

ghci> getZipList $ ZipList [(+1),(*100),(*5)] <*> ZipList [1,2,3]
[2,200,15]

Donc, que fait le nouveau mot-clé newtype ? Eh bien, réfléchissez à la façon dont vous écririez la déclaration data du type ZipList a. Une façon de l'écrire serait :

data ZipList a = ZipList [a]

Un type qui n'a qu'un constructeur de valeurs, et ce constructeur de valeurs n'a qu'un champ, qui est une liste de choses. On aurait aussi pu vouloir utiliser la syntaxe des enregistrements pour obtenir automatiquement une fonction qui extrait une liste d'une ZipList :

data ZipList a = ZipList { getZipList :: [a] }

Cela a l'air correct, et fonctionnerait en fait plutôt bien. Puisqu'on avait deux manières de faire d'un type existant une instance d'une classe de types, on a utilisé le mot-clé data pour juste envelopper ce type dans un autre type, et fait de ce second type une instance de la seconde manière.

Le mot-clé newtype en Haskell est fait exactement pour ces cas où l'on veut juste prendre un type et l'encapsuler dans quelque chose pour le présenter comme un nouveau type. Dans la bibliothèque, ZipList a est définie comme :

newtype ZipList a = ZipList { getZipList :: [a] }

Plutôt que d'utiliser le mot-clé data, on utilise le mot-clé newtype. Pourquoi cela ? Eh bien, premièrement, newtype est plus rapide. Quand vous utilisez le mot-clé data pour envelopper un type, il y aura un coût à l'exécution pour faire l'encapsulage et le décapsulage. Alors qu'avec le mot-cle newtype, Haskell sait que vous utilisez cela juste pour encapsuler un type existant dans un nouveau type (d'où le nom du mot-clé), parce que vous voulez la même chose en interne, mais avec un nom (type) différent. Avec cela en tête, Haskell peut se débarrasser de l'emballage et du déballage une fois qu'il a tenu compte du type de chaque valeur pour savoir quelle instance utiliser.

Pourquoi ne pas utiliser newtype tout le temps plutôt que data dans ce cas ? Eh bien, quand vous créez un nouveau type à partir d'un type existant en utilisant le mot-clé newtype, vous ne pouvez avoir qu'un seul constructeur de valeurs, et ce constructeur de valeurs ne peut avoir qu'un seul champ. Alors qu'avec data, vous pouvez créer des types de données qui ont plusieurs constructeurs de valeurs, chacun pouvant avoir zéro ou plusieurs champs :

data Profession = Fighter | Archer | Accountant

data Race = Human | Elf | Orc | Goblin

data PlayerCharacter = PlayerCharacter Race Profession

Quand on utilise newtype, on est restreint à un seul constructeur avec un seul champ.

On peut également utiliser le mot-clé deriving avec newtype, comme on le fait avec data. On peut dériver les instances d'Eq, Ord, Enum, Bounded, Show et Read. Si l'on souhaite dériver une instance d'une classe de types, le type qu'on enveloppe doit lui-même être membre de cette classe. C'est logique, parce que newtype ne fait qu'envelopper ce type. On peut donc afficher et tester l'égalité de valeurs de notre nouveau type en faisant :

newtype CharList = CharList { getCharList :: [Char] } deriving (Eq, Show)

Essayons :

ghci> CharList "this will be shown!"
CharList {getCharList = "this will be shown!"}
ghci> CharList "benny" == CharList "benny"
True
ghci> CharList "benny" == CharList "oisters"
False

Pour ce newtype, le constructeur de valeurs a pour type :

CharList :: [Char] -> CharList

Il prend une valeur [Char], comme "my sharona", et retourne une valeur CharList. Dans les exemples ci-dessus où l'on utilisait le constructeur de valeurs CharList, on voit que c'est le cas. Réciproquement, la fonction getCharList, qui a été générée lorsqu'on a utilisé la syntaxe des enregistrements dans notre newtype, a pour type :

getCharList :: CharList -> [Char]

Elle prend une valeur CharList et la convertit en [Char]. Vous pouvez imaginer ceci comme emballer et déballer, mais vous pouvez aussi l'imaginer comme une conversion d'un type vers l'autre.

XI-B-1. Utiliser newtype pour créer des instances de classes de types▲

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

instance Functor Maybe where

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

newtype Pair b a = Pair { getPair :: (a,b) }

instance Functor (Pair c) where
    fmap f (Pair (x,y)) = Pair (f x, y)

fmap :: (a -> b) -> Pair c a -> Pair c b

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

ghci> getPair $ fmap (*100) (Pair (2,3))
(200,3)
ghci> getPair $ fmap reverse (Pair ("london calling", 3))
("gnillac nodnol",3)

XI-B-2. De la paresse de newtype▲

ghci> undefined
*** Exception: Prelude.undefined

ghci> head [3,4,5,undefined,2,undefined]
3

data CoolBool = CoolBool { getCoolBool :: Bool }

helloMe :: CoolBool -> String
helloMe (CoolBool _) = "hello"

ghci> helloMe undefined
"*** Exception: Prelude.undefined

newtype CoolBool = CoolBool { getCoolBool :: Bool }

ghci> helloMe undefined
"hello"

XI-B-3. type vs. newtype vs. data▲

type IntList = [Int]

ghci> ([1,2,3] :: IntList) ++ ([1,2,3] :: [Int])
[1,2,3,1,2,3]

newtype CharList = CharList { getCharList :: [Char] }

Les classes de types en Haskell sont utilisées pour présenter une interface pour des types qui partagent un comportement. On a commencé avec des classes de types simples comme Eq, pour les types dont on peut tester l'égalité, et Ord pour ceux qu'on peut mettre en ordre, puis on est passé à des classes plus intéressantes, comme Functor et Applicative.

Lorsqu'on crée un type, on réfléchit aux comportements qu'il supporte, i.e. pour quoi peut-il se faire passer, et à partir de cela, on décide de quelles classes de types on en fera une instance. Si cela a un sens de tester l'égalité de nos valeurs, alors on crée une instance d'Eq. Si l'on voit que notre type est un foncteur, alors on crée une instance de Functor, et ainsi de suite.

Maintenant, considérez cela : * est une fonction qui prend deux nombres et les multiplie entre eux. Si l'on multiplie un nombre par 1, le résultat est toujours égal à ce nombre. Peu importe qu'on fasse 1 * x ou x * 1, le résultat est toujours x. De façon similaire, ++ est aussi une fonction qui prend deux choses et en retourne une troisième. Au lieu de les multiplier, elle les concatène. Et tout comme *, elle a aussi une valeur qui ne change pas l'autre quand on la combine avec ++. Cette valeur est la liste vide : [].

ghci> 4 * 1
4
ghci> 1 * 9
9
ghci> [1,2,3] ++ []
[1,2,3]
ghci> [] ++ [0.5, 2.5]
[0.5,2.5]

On dirait que * et 1 partagent une propriété commune avec ++ et [] :

• La fonction prend deux paramètres.
• Les paramètres et la valeur retournée ont le même type.
• Il existe une valeur de ce type qui ne change pas l'autre valeur lorsqu'elle est appliquée à la fonction binaire.

Autre chose que ces deux opérations ont en commun et qui n'est pas si évidente : lorsqu'on a trois valeurs ou plus et qu'on utilise la fonction binaire pour les réduire à une seule valeur, l'ordre dans lequel on applique la fonction n'importe pas. Peu importe qu'on fasse (3 * 4) * 5 ou 3 * (4 * 5). De toute manière, le résultat est 60. De même pour ++ :

ghci> (3 * 2) * (8 * 5)
240
ghci> 3 * (2 * (8 * 5))
240
ghci> "la" ++ ("di" ++ "da")
"ladida"
ghci> ("la" ++ "di") ++ "da"
"ladida"

On appelle cette propriété l'associativité. * est associative, de même que ++, mais par exemple - ne l'est pas. Les expressions (5 - 3) - 4 et 5 - (3 - 4) n'ont pas le même résultat.

En remarquant ces propriétés et en les écrivant, on vient de tomber sur les monoïdes ! On a un monoïde lorsqu'on dispose d'une fonction binaire associative et d'un élément neutre pour cette fonction. Quand quelque chose est un élément neutre pour une fonction, cela signifie que lorsqu'on appelle la fonction avec cette chose et une autre valeur, le résultat est toujours égal à l'autre valeur. 1 est l'élément neutre vis-à-vis de *, et [] est le neutre de ++. Il y a beaucoup d'autres monoïdes à trouver dans le monde d'Haskell, c'est pourquoi la classe de types Monoid existe. Elle est pour ces types qui peuvent agir comme des monoïdes. Voyons comment la classe de types est définie :

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

La classe de types Monoid est définie dans Data.Monoid. Prenons un peu de temps pour la découvrir.

Tout d'abord, on voit que seuls des types concrets peuvent être faits instance de Monoid, parce que le m de la définition de classe ne prend pas de paramètres. C'est différent de Functor et Applicative qui nécessitent que leurs instances soient des constructeurs de types prenant un paramètre.

La première fonction est mempty. Ce n'est pas vraiment une fonction puisqu'elle ne prend pas de paramètres, c'est plutôt une constante polymorphique, un peu comme minBound de Bounded. mempty représente l'élément neutre de ce monoïde.

Ensuite, on a mappend, qui, comme vous l'avez probablement deviné, est la fonction binaire. Elle prend deux valeurs du même type et retourne une valeur de ce type. Il est bon de mentionner que la décision d'appeler mappend de la sorte est un peu malheureuse, parce que ce nom semble impliquer qu'on essaie de juxtaposer deux choses (NDT : en anglais, « append » signifie « juxtaposer »). Bien que ++ prenne deux listes et les juxtapose, * ne juxtapose pas vraiment, elle multiplie seulement deux nombres. Quand nous rencontrerons d'autres instances de Monoid, on verra que la plupart d'entre elles ne juxtaposent pas non plus leurs valeurs, évitez donc de penser en termes de juxtaposition, et pensez plutôt que mappend est une fonction binaire qui prend deux valeurs monoïdales et en retourne une troisième.

La dernière fonction de la définition de la classe de types est mconcat. Elle prend une liste de valeurs monoïdales et les réduit à une unique valeur en faisant mappend entre les éléments de la liste. Elle a une implémentation par défaut, qui prend mempty comme valeur initiale et plie la liste depuis la droite avec mappend. Puisque l'implémentation par défaut convient pour la plupart des instances, on ne se souciera pas trop de mconcat pour l'instant. Quand on crée une instance de Monoid, il suffit d'implémenter mempty et mappend. La raison de la présence de mconcat ici est que, pour certaines instances, il peut y avoir une manière plus efficace de l'implémenter, mais pour la plupart des instances, l'implémentation par défaut convient.

Avant de voir des instances spécifiques de Monoid, regardons brièvement les lois des monoïdes. On a mentionné qu'il devait exister une valeur neutre vis-à-vis de la fonction binaire, et que la fonction binaire devait être associative. Il est possible de créer des instances de Monoid ne suivant pas ces règles, mais ces instances ne servent à personne parce que, quand on utilise la classe de types Monoid, on se repose sur le fait que ses instances agissent comme des monoïdes. Sinon, à quoi cela servirait-il ? C'est pourquoi, en créant des instances, on doit s'assurer qu'elles obéissent à ces lois :

• mempty `mappend` x = x
• x `mappend` mempty = x
• (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

Les deux premières déclarent que mempty doit être le neutre de mappend, la troisième dit que mappend doit être associative, i.e. l'ordre dans lequel on applique mappend pour réduire plusieurs valeurs monoïdales en une n'importe pas. Haskell ne fait pas respecter ces lois, c'est donc à nous en tant que programmeur de faire attention à ce que nos instances y obéissent.

XI-C-1. Les listes sont des monoïdes▲

instance Monoid [a] where
    mempty = []
    mappend = (++)

ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> ("one" `mappend` "two") `mappend` "tree"
"onetwotree"
ghci> "one" `mappend` ("two" `mappend` "tree")
"onetwotree"
ghci> "one" `mappend` "two" `mappend` "tree"
"onetwotree"
ghci> "pang" `mappend` mempty
"pang"
ghci> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
ghci> mempty :: [a]
[]

ghci> "one" `mappend` "two"
"onetwo"
ghci> "two" `mappend` "one"
"twoone"

XI-C-2. Product et Sum▲

ghci> 0 + 4
4
ghci> 5 + 0
5
ghci> (1 + 3) + 5
9
ghci> 1 + (3 + 5)
9

newtype Product a =  Product { getProduct :: a }
    deriving (Eq, Ord, Read, Show, Bounded)

instance Num a => Monoid (Product a) where
    mempty = Product 1
    Product x `mappend` Product y = Product (x * y)

ghci> getProduct $ Product 3 `mappend` Product 9
27
ghci> getProduct $ Product 3 `mappend` mempty
3
ghci> getProduct $ Product 3 `mappend` Product 4 `mappend` Product 2
24
ghci> getProduct . mconcat . map Product $ [3,4,2]
24

ghci> getSum $ Sum 2 `mappend` Sum 9
11
ghci> getSum $ mempty `mappend` Sum 3
3
ghci> getSum . mconcat . map Sum $ [1,2,3]
6

XI-C-3. Any et All▲

newtype Any = Any { getAny :: Bool }
    deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid Any where
        mempty = Any False
        Any x `mappend` Any y = Any (x || y)

ghci> getAny $ Any True `mappend` Any False
True
ghci> getAny $ mempty `mappend` Any True
True
ghci> getAny . mconcat . map Any $ [False, False, False, True]
True
ghci> getAny $ mempty `mappend` mempty
False

newtype All = All { getAll :: Bool }
        deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid All where
        mempty = All True
        All x `mappend` All y = All (x && y)

ghci> getAll $ mempty `mappend` All True
True
ghci> getAll $ mempty `mappend` All False
False
ghci> getAll . mconcat . map All $ [True, True, True]
True
ghci> getAll . mconcat . map All $ [True, True, False]
False

XI-C-4. Le monoïde Ordering▲

ghci> 1 `compare` 2
LT
ghci> 2 `compare` 2
EQ
ghci> 3 `compare` 2
GT

instance Monoid Ordering where
    mempty = EQ
    LT `mappend` _ = LT
    EQ `mappend` y = y
    GT `mappend` _ = GT

ghci> LT `mappend` GT
LT
ghci> GT `mappend` LT
GT
ghci> mempty `mappend` LT
LT
ghci> mempty `mappend` GT
GT

lengthCompare :: String -> String -> Ordering
lengthCompare x y = let a = length x `compare` length y
                        b = x `compare` y
                    in  if a == EQ then b else a

import Data.Monoid

lengthCompare :: String -> String -> Ordering
lengthCompare x y = (length x `compare` length y) `mappend`
                    (x `compare` y)

ghci> lengthCompare "zen" "ants"
LT
ghci> lengthCompare "zen" "ant"
GT

import Data.Monoid

lengthCompare :: String -> String -> Ordering
lengthCompare x y = (length x `compare` length y) `mappend`
                    (vowels x `compare` vowels y) `mappend`
                    (x `compare` y)
    where vowels = length . filter (`elem` "aeiou")

ghci> lengthCompare "zen" "anna"
LT
ghci> lengthCompare "zen" "ana"
LT
ghci> lengthCompare "zen" "ann"
GT

XI-C-5. Maybe le monoïde▲

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

ghci> Nothing `mappend` Just "andy"
Just "andy"
ghci> Just LT `mappend` Nothing
Just LT
ghci> Just (Sum 3) `mappend` Just (Sum 4)
Just (Sum {getSum = 7})

newtype First a = First { getFirst :: Maybe a }
    deriving (Eq, Ord, Read, Show)

instance Monoid (First a) where
    mempty = First Nothing
    First (Just x) `mappend` _ = First (Just x)
    First Nothing `mappend` x = x

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')
Just 'a'
ghci> getFirst $ First Nothing `mappend` First (Just 'b')
Just 'b'
ghci> getFirst $ First (Just 'a') `mappend` First Nothing
Just 'a'

ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]
Just 9

ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]
Just 10
ghci> getLast $ Last (Just "one") `mappend` Last (Just "two")
Just "two"

XI-C-6. Utiliser des monoïdes pour plier des structures de données▲

import qualified Foldable as F

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t F.foldr
F.foldr :: (F.Foldable t) => (a -> b -> b) -> b -> t a -> b

ghci> foldr (*) 1 [1,2,3]
6
ghci> F.foldr (*) 1 [1,2,3]
6

ghci> F.foldl (+) 2 (Just 9)
11
ghci> F.foldr (||) False (Just True)
True

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

instance F.Foldable Tree where
    foldMap f Empty = mempty
    foldMap f (Node x l r) = F.foldMap f l `mappend`
                             f x           `mappend`
                             F.foldMap f r

testTree = Node 5
            (Node 3
                (Node 1 Empty Empty)
                (Node 6 Empty Empty)
            )
            (Node 9
                (Node 8 Empty Empty)
                (Node 10 Empty Empty)
            )

ghci> F.foldl (+) 0 testTree
42
ghci> F.foldl (*) 1 testTree
64800

ghci> getAny $ F.foldMap (\x -> Any $ x == 3) testTree  
True

ghci> getAny $ F.foldMap (\x -> Any $ x > 15) testTree  
False

ghci> F.foldMap (\x -> [x]) testTree  
[1,3,6,5,8,9,10]