La combinaison de la pureté, des fonctions d’ordre supérieur, des types de données algébriques paramétrés, et des classes de types que propose Haskell nous permet d’implémenter du polymorphisme à un niveau bien plus élevé que dans la plupart des autres langages. On n’a pas besoin de penser aux types comme appartenant à une hiérarchie de types. À la place, on pense à ce que les types peuvent faire, et on les connecte aux classes de types appropriées. Un Int peut se faire passer pour beaucoup de choses. Il peut se faire passer pour quelque chose dont on peut tester l’égalité, pour quelque chose qu’on peut ordonner, pour quelque chose qu’on peut énumérer, etc.

Les classes de types sont ouvertes, ce qui veut dire qu’on peut définir nos propres types de données, réfléchir à ce qu’ils peuvent faire, et les connecter aux classes de types qui définissent ses comportements. Grâce à cela, et au système de types d’Haskell qui nous permet de savoir beaucoup de choses sur une fonction rien qu’en regardant sa déclaration de type, on peut définir des classes de types qui définissent des comportements très généraux et abstraits. On a vu des classes de types définissant des opérateurs pour tester l’égalité ou comparer des choses. Ce sont des comportements assez abstraits et élégants, mais on ne les considère pas comme cela parce qu’on fait souvent la même chose dans nos vies réelles. On a récemment découvert les foncteurs, qui sont simplement des choses sur lesquelles on peut mapper. C’est un exemple de propriété utile mais plutôt abstraite que peuvent décrire les classes de types. Dans ce chapitre, on va regarder les foncteurs d’un peu plus près, ainsi que des versions plus fortes et utiles de foncteurs, appelés foncteurs applicatifs. On va aussi s’intéresser aux monoïdes, qui sont un peu comme des chaussettes.

Foncteurs revisités

On a déjà parlé des foncteurs dans leur propre petite section. Si vous ne l’avez pas encore lue, vous devriez probablement le faire à présent, ou plus tard, quand vous aurez plus de temps. Ou faire semblant de l’avoir lue.

Ceci étant, un petit rappel : les foncteurs sont des choses sur lesquelles on peut mapper, comme des listes, des Maybe, des arbres, et d’autres. En Haskell, ils sont définis par la classe de types Functor, qui n’a qu’une méthode de classe de type, fmap, ayant pour type fmap :: (a -> b) -> f a -> f b. Cela dit : donne-moi une fonction qui prend un a et retourne un b, et une boîte avec un (ou plusieurs) a à l’intérieur, et je te donnerai une boîte avec un (ou plusieurs) b à l’intérieur. Elle applique grosso-modo la fonction aux éléments dans la boîte.

Si on veut faire d’un constructeur de types une instance de Functor, il doit avoir pour sorte * -> *, ce qui signifie qu’il doit prendre exactement un type concret en paramètre de type. Par exemple, Maybe peut être une instance parce qu’il prend un paramètre de type pour produire un type concret, comme Maybe Int ou Maybe String. Si un constructeur de types prend deux paramètres, comme Either, il faut l’appliquer partiellement jusqu’à ce qu’il ne prenne plus qu’un paramètre de type. Ainsi, on ne peut pas écrire instance Functor Either where, mais on peut écrire instance Functor (Either a) where, et alors en imaginant que fmap ne fonctionne que pour les Either a, elle aurait pour déclaration de type fmap :: (b -> c) -> Either a b -> Either a c. Comme vous pouvez le voir, la partie Either a est fixée, parce que Either a ne prend qu’un paramètre de type, alors qu’Either en prend deux, et ainsi fmap :: (b -> c) -> Either b -> Either c ne voudrait rien dire.

On sait à présent comment plusieurs types (ou plutôt, des constructeurs de types) sont des instances de Functor, comme [], Maybe, Either a et un type Tree qu’on a créé nous-mêmes. On a vu comment l’on pouvait mapper des fonctions sur ceux-ci pour notre plus grand bien. Dans cette section, on va découvrir deux autres instances de foncteurs, IO et (->) r.

Si une valeur a pour type, mettons, IO String, cela signifie que c’est une action I/O qui, lorsqu’elle est exécutée, ira dans le monde réel et nous récupèrera une chaîne de caractères, qu’elle rendra comme son résultat. On peut utiliser <- dans la syntaxe do pour lier ce résultat à un nom. On a mentionné que les actions I/O sont comme des boîtes avec des petits pieds qui sortent chercher des valeurs dans le monde à l’extérieur pour nous. On peut inspecter ce qu’elles ont ramené, mais après inspection, on doit les envelopper à nouveau dans IO. En pensant à cette analogie de boîte avec des petits pieds, on peut voir comment IO agit comme un foncteur.

Voyons comment faire d’IO une instance de Functor. Quand on fmap une fonction sur une action I/O, on veut obtenir une action I/O en retour qui fait la même chose, mais applique notre fonction sur la valeur résultante.

instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)

Le résultat du mappage de quelque chose sur une action I/O sera une action I/O, donc on utilise immédiatement la notation do pour coller deux actions en une. Dans l’implémentation de fmap, on crée une nouvelle action I/O qui commence par exécuter l’action I/O originale, et on appelle son résultat result. Puis, on fait return (f result). return est, comme vous le savez, une fonction qui crée une action I/O qui ne fait rien, mais présente un résultat. L’action produite par un bloc do aura toujours pour résultat celui de sa dernière action. C’est pourquoi on utilise return pour créer une action I/O qui ne fait pas grand chose, mais présente f result comme le résultat de l’action I/O composée.

On peut jouer un peu avec pour se faire une intuition. C’est en fait assez simple. Regardez ce code :

main = do line <- getLine
          let line' = reverse line
          putStrLn $ "You said " ++ line' ++ " backwards!"
          putStrLn $ "Yes, you really said" ++ line' ++ " backwards!"

On demande une ligne à l’utilisateur, et on la lui rend, mais renversée. Voici comment réécrire ceci en utilisant fmap :

main = do line <- fmap reverse getLine
          putStrLn $ "You said " ++ line ++ " backwards!"
          putStrLn $ "Yes, you really said" ++ line ++ " backwards!"

Tout comme on peut fmap reverse sur Just "blah" pour obtenir Just "halb", on peut fmap reverse sur getLine. getLine est une action I/O qui a pour type IO String et mapper reverse sur elle nous donne une action I/O qui va aller dans le monde réel et récupérer une ligne, puis appliquer reverse dessus. Tout comme on peut appliquer une fonction à quelque chose enfermé dans une boîte Maybe, on peut appliquer une fonction à quelque chose enfermé dans une boîte IO, seulement la boîte doit toujours aller dans le monde réel pour obtenir quelque chose. Ensuite, lorsqu’on la lie à quelque chose avec <-, le nom sera lié au résultat auquel reverse aura déjà été appliquée.

L’action I/O fmap (++"!") getLine se comporte comme getLine, mais ajoute toujours "!" à son résultat !

Si on regarde ce que le type de fmap serait si elle était limitée à IO, ce serait fmap :: (a -> b) -> IO a -> IO b. fmap prend une fonction et une action I/O et retourne une nouvelle action I/O comme l’ancienne, mais avec la fonction appliquée à son résultat.

Si jamais vous liez le résultat d’une action I/O à un nom, juste pour ensuite appliquer une fonction à ce nom et lui donner un nouveau nom, utilisez plutôt fmap, ce sera plus joli. Si vous voulez appliquez des transformations multiples à une donnée dans un foncteur, vous pouvez soit déclarer une fonction dans l’espace de nom global, soit utiliser une lambda expression, ou idéalement, utiliser la composition de fonctions :

import Data.Char
import Data.List

main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine
          putStrLn line

$ runhaskell fmapping_io.hs
hello there
E-R-E-H-T- -O-L-L-E-H

Comme vous le savez probablement, intersperse '-' . reverse . map toUpper est une fonction qui prend une chaîne de caractères, mappe toUpper sur celle-ci, applique reverse au résultat, et applique intersperse '-' à ce résultat. C’est comme écrire (\xs -> intersperse '-' (reverse (map toUpper xs))), mais plus joli.

Une autre instance de Functor qu’on a utilisée tout du long sans se douter qu’elle était un foncteur est (->) r. Vous êtes sûrement un peu perdu à présent, qu’est-ce que ça veut dire (->) r ? Le type de fonctions r -> a peut être réécrit (->) r a, tout comme 2 + 3 peut être réécrit (+) 2 3. Quand on regarde (->) r a, on peut voir (->) sous un nouveau jour, et s’apercevoir que c’est juste un constructeur de types qui prend deux paramètres de types, tout comme Either. Mais souvenez-vous, on a dit qu’un constructeur de types doit prendre exactement un paramètre pour être une instance de Functor. C’est pourquoi (->) ne peut pas être une instance de Functor, mais si on l’applique partiellement en (->) r, ça ne pose plus de problème. Si la syntaxe nous permettait d’appliquer partiellement les constructeurs de types avec des sections (comme l’on peut partiellement appliquer + en faisant (2+), qui est équivalent à (+) 2), vous pourriez réécrire (->) r comme (r ->). Comment est-ce que les fonctions sont-elles des foncteurs ? Eh bien, regardons l’implémentation, qui se trouve dans Control.Monad.Instances.

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

Si la syntaxe le permettait, on aurait pu écrire :

instance Functor (r ->) where
    fmap f g = (\x -> f (g x))

Mais elle ne le permet pas, donc on doit l’écrire de la première façon.

Tout d’abord, pensons au type de fmap. C’est fmap :: (a -> b) -> f a -> f b. À présent, remplaçons mentalement les f, qui ont pour rôle d’être notre foncteur, par des (->) r. On fait cela pour voir comment fmap doit se comporter pour cette instance. On obtient fmap :: (a -> b) -> ((->) r a) -> ((->) r b). Maintenant, on peut réécrire (->) r a et (->) r b de manière infixe en r -> a et r -> b, comme on l’écrit habituellement pour les fonctions. On a donc fmap :: (a -> b) -> (r -> a) -> (r -> b).

Hmmm OK. Mapper une fonction sur une fonction produit une fonction, tout comme mapper une fonction sur un Maybe produit un Maybe et mapper une fonction sur une liste produit une liste. Qu’est-ce que le type fmap :: (a -> b) -> (r -> a) -> (r -> b) nous indique-t-il ? Eh bien, on voit que la fonction prend une fonction de a vers b et une fonction de r vers a, et retourne une fonction de r vers b. Cela ne vous rappelle rien ? Oui ! La composition de fonctions ! On connecte la sortie de r -> a à l’entrée de a -> b pour obtenir une fonction r -> b, ce qui est exactement ce que fait la composition de fonctions. Si vous regardez comment l’instance est définie ci-dessus, vous verrez qu’on a juste composé les fonctions. Une autre façon d’écrire cette instance serait :

instance Functor ((->) r) where
    fmap = (.)

Cela rend évident le fait qu’utiliser fmap sur des fonctions sert juste à composer. Faites :m + Control.Monad.Instances, puisque c’est là que l’instance est définie, et essayez de jouer à mapper sur des fonctions.

ghci> :t fmap (*3) (+100)
fmap (*3) (+100) :: (Num a) => a -> a
ghci> fmap (*3) (+100) 1
303
ghci> (*3) `fmap` (+100) $ 1
303
ghci> (*3) . (+100) $ 1
303
ghci> fmap (show . (*3)) (*100) 1
"300"

On peut appeler fmap de façon infixe pour souligner la ressemblance avec .. Dans la deuxième ligne d’entrée, on mappe (*3) sur (+100), ce qui retourne une fonction qui prend une entrée, appelle (+100) sur celle-ci, puis appelle (*3) sur ce résultat. On appelle cette fonction sur la valeur 1.

Est-ce que l’analogie des boîtes fonctionne toujours ici ? Avec un peu d’imagination, oui. Quand on fait fmap (+3) sur Just 3, il est facile d’imaginer le Maybe boîte qui a un contenu sur lequel on applique la fonction (+3). Mais qu’en est-il quand on fait fmap (*3) (+100) ? Eh bien, vous pouvez imaginer (+100) comme une boîte qui contient son résultat futur. Comme on imaginait une action I/O comme une boîte qui irait chercher son résultat dans le monde réel. Faire fmap (*3) sur (+100) crée une autre fonction qui se comporte comme (+100), mais avant de produire son résultat, applique (*3) dessus. Ainsi, on voit que fmap se comporte comme . pour les fonctions.

Le fait que fmap soit la composition de fonctions quand elle est utilisée sur des fonctions n’est pas très utile pour l’instant, mais c’est tout du moins intéressant. Cela tord aussi un peu notre esprit et nous fait voir comment des choses agissant plutôt comme des calculs que comme des boîtes (tel IO et (->) r) peuvent elles aussi être des foncteurs. La fonction mappée sur un calcul agit comme ce calcul, mais modifie son résultat avec cette fonction.

Avant de regarder les règles que fmap doit respecter, regardons encore une fois son type. Celui-ci est fmap :: (a -> b) -> f a -> f b. Il manque la contrainte de classe (Functor f) =>, mais on l’oublie par concision, parce qu’on parle de foncteurs donc on sait ce que signifie f. Quand on a découvert les fonctions curryfiées, on a dit que toutes les fonctions Haskell prennent un unique paramètre. Une fonction a -> b -> c ne prend en réalité qu’un paramètre a et retourne une fonction b -> c, qui prend un paramètre et retourne un c. C’est pourquoi, si l’on appelle une fonction avec trop peu de paramètres (c’est-à-dire qu’on l’applique partiellement), on obtient en retour une fonction qui prend autant de paramètres qu’il en manquait (on repense à nouveau à nos fonctions comme prenant plusieurs paramètres). Ainsi, a -> b -> c peut être écrit a -> (b -> c) pour faire apparaître la curryfication.

Dans la même veine, si l’on écrit fmap :: (a -> b) -> (f a -> f b), on peut imaginer fmap non pas comme une fonction qui prend une fonction et un foncteur pour retourner un foncteur, mais plutôt comme une fonction qui prend une fonction, et retourne une nouvelle fonction, similaire à l’ancienne, mais qui prend et retourne des foncteurs. Elle prend une fonction a -> b, et retourne une fonction f a -> f b. On dit qu’on lifte la fonction. Jouons avec cette idée en utilisant la commande :t de GHCi :

ghci> :t fmap (*2)
fmap (*2) :: (Num a, Functor f) => f a -> f a
ghci> :t fmap (replicate 3)
fmap (replicate 3) :: (Functor f) => f a -> f [a]

L’expression fmap (*2) est une fonction qui prend un foncteur f sur des nombres, et retourne un foncteur sur des nombres. Ce foncteur peut être une liste, un Maybe, un Either String, peu importe. L’expression fmap (replicate 3) prend un foncteur de n’importe quel type et retourne un foncteur sur des listes d’éléments de ce type.

Ceci est encore plus apparent si l’on applique partiellement, mettons, fmap (++"!") et qu’on lie cela à un nom dans GHCi.

Vous pouvez imaginer fmap soit comme une fonction qui prend une fonction et un foncteur, et mappe cette fonction sur le foncteur, ou bien comme une fonction qui prend une fonction et la lifte en une fonction sur des foncteurs. Les deux visions sont correctes et équivalentes en Haskell.

Le type fmap (replicate 3) :: (Functor f) => f a -> f [a] signifie que la fonction marchera sur n’importe quel foncteur. Ce qu’elle fera exactement dépendra du foncteur en question. Si on utilise fmap (replicate 3) sur une liste, l’implémentation de fmap pour les listes sera choisie, c’est-à-dire map. Si on l’utilise sur Maybe a, cela appliquera replicate 3 à la valeur dans le Just, alors qu’un Nothing restera un Nothing.

ghci> fmap (replicate 3) [1,2,3,4]
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]
ghci> fmap (replicate 3) (Just 4)
Just [4,4,4]
ghci> fmap (replicate 3) (Right "blah")
Right ["blah","blah","blah"]
ghci> fmap (replicate 3) Nothing
Nothing
ghci> fmap (replicate 3) (Left "foo")
Left "foo"

Maintenant, nous allons voir les lois des foncteurs. Afin que quelque chose soit un foncteur, il doit satisfaire quelques lois. On attend de tous les foncteurs qu’ils présentent certaines propriétés et comportements fonctoriels. Ils doivent se comporter de façon fiable comme des choses sur lesquelles on peut mapper. Appeler fmap sur un foncteur devrait seulement mapper une fonction sur le foncteur, rien de plus. Ce comportement est décrit dans les lois des foncteurs. Il y en a deux, et toute instance de Functor doit les respecter. Elles ne sont cependant pas vérifiées automatiquement par Haskell, il faut donc les tester soi-même.

La première loi des foncteurs dit que si l’on mappe la fonction id sur un foncteur, le foncteur retourné doit être identique au foncteur original. Si on écrit cela plus formellement, cela signifie que fmap id = id. En gros, cela signifie que si l’on fait fmap id sur un foncteur, cela doit être pareil que de faire simplement id sur ce foncteur. Souvenez-vous, id est la fonction identité, qui retourne son paramètre à l’identique. Elle peut également être écrite \x -> x. Si l’on voit le foncteur comme quelque chose sur laquelle on peut mapper, alors la loi fmap id peut sembler triviale ou évidente.

Voyons si cette loi tient pour quelques foncteurs.

ghci> fmap id (Just 3)
Just 3
ghci> id (Just 3)
Just 3
ghci> fmap id [1..5]
[1,2,3,4,5]
ghci> id [1..5]
[1,2,3,4,5]
ghci> fmap id []
[]
ghci> fmap id Nothing
Nothing

Si on regarde l’implémentation de fmap, par exemple pour Maybe, on peut se rendre compte que la première loi des foncteurs est respectée.

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

Imaginons qu’id soit à la place de f dans l’implémentation. On voit que si l’on fmap id sur Just x, le résultat sera Just (id x), et puisqu’id retourne son paramètre à l’identique, on peut en déduire que Just (id x) est égal à Just x. Ainsi, mapper id sur une valeur Maybe construite avec Just retourne la même valeur.

Voir que mapper id sur une valeur Nothing retourne la même valeur est trivial. De ces deux équations de l’implémentation de fmap, on déduit que fmap id = id est vrai.

La seconde loi dit que composer deux fonctions, et mapper le résultat sur un foncteur doit être identique à mapper d’abord une des fonctions sur le foncteur, puis mapper l’autre sur le résultat. Formellement, on veut fmap (f . g) = fmap f . fmap g. Ou, d’une autre façon, pour tout foncteur F, on souhaite : fmap (f . g) F = fmap f (fmap g F).

Si l’on peut montrer qu’un type obéit à ces deux lois des foncteurs, alors on peut avoir l’assurance qu’il aura les mêmes propriétés fondamentales vis-à-vis du mappage. On sait que lorsque l’on fait fmap sur ce type, il ne se passera rien d’autre qu’un mappage, et il se comportera comme une chose sur laquelle on mappe, i.e. un foncteur. On peut voir si un type respecte la seconde loi en regardant l’implémentation de fmap pour ce type, et en utilisant la même méthode qu’on a utilisée pour voir si Maybe obéissait à la première loi.

Si vous le voulez, on peut vérifier que la seconde loi des foncteurs est vérifiée par Maybe. Si on fait fmap (f . g) sur Nothing, on obtient Nothing, parce que quelle que soit la fonction mappée sur Nothing, on obtient Nothing. De même, faire fmap f (fmap g Nothing) retourne Nothing, pour la même raison. OK, voir que la seconde loi tient pour une valeur Nothing de Maybe était plutôt facile, presque trivial.

Et si c’est une valeur Just something ? Eh bien, si l’on fait fmap (f . g) (Just x), on voit de l’implémentation que c’est Just ((f . g) x), qui est, évidemment, Just (f (g x)). Si l’on fait fmap f (fmap g (Just x)), on voit que fmap g (Just x) est Just (g x). Donc, fmap f (fmap g (Just x)) est égal à fmap f (Just (g x)), et de l’implémentation, on voit que cela est égal à Just (f (g x)).

Si vous êtes un peu perdu dans cette preuve, ne vous inquiétez pas. Soyez sûr de bien comprendre comme fonctionne la composition de fonctions. Très souvent, on peut voir intuitivement que ces lois sont respectées parce que le type se comporte comme un conteneur ou comme une fonction. Vous pouvez aussi essayer sur un tas de valeurs et vous convaincre que le type suit bien les lois.

Intéressons-nous au cas pathologique d’un constructeur de types instance de Functor mais qui n’est pas vraiment un foncteur, parce qu’il ne satisfait pas les lois. Mettons qu’on ait un type :

data CMaybe a = CNothing | CJust Int a deriving (Show)

Le C ici est pour compteur. C’est un type de données qui ressemble beaucoup à Maybe a, mais la partie Just contient deux champs plutôt qu’un. Le premier champ du constructeur de valeurs CJust aura toujours pour type Int, et ce sera une sorte de compteur, et le second champ sera de type a, qui vient du paramètre de type, et son type dépendra bien sûr du type concret qu’on choisit pour CMaybe a. Jouons avec notre type pour se faire une intuition.

ghci> CNothing
CNothing
ghci> CJust 0 "haha"
CJust 0 "haha"
ghci> :t CNothing
CNothing :: CMaybe a
ghci> :t CJust 0 "haha"
CJust 0 "haha" :: CMaybe [Char]
ghci> CJust 100 [1,2,3]
CJust 100 [1,2,3]

Si on utilise le constructeur CNothing, il n’y a pas de champs, alors que le constructeur CJust a un champ entier et un champ de n’importe quel type. Créons une instance de Functor pour laquelle, chaque fois qu’on utilise fmap, la fonction est appliquée au second champ, alors que le premier est incrémenté de 1.

instance Functor CMaybe where
    fmap f CNothing = CNothing
    fmap f (CJust counter x) = CJust (counter+1) (f x)

C’est un peu comme l’implémentation de Maybe, à l’exception que lorsqu’on fait fmap sur une valeur qui n’est pas une boîte vide (donc sur une valeur CJust), en plus d’appliquer la fonction au contenu, on augmente le compteur de 1. Tout va bien pour l’instant, on peut même jouer un peu avec :

ghci> fmap (++"ha") (CJust 0 "ho")
CJust 1 "hoha"
ghci> fmap (++"he") (fmap (++"ha") (CJust 0 "ho"))
CJust 2 "hohahe"
ghci> fmap (++"blah") CNothing
CNothing

Est-ce que cela vérifie les lois des foncteurs ? Pour démontrer que ce n’est pas le cas, il nous suffit de trouver un contre-exemple.

ghci> fmap id (CJust 0 "haha")
CJust 1 "haha"
ghci> id (CJust 0 "haha")
CJust 0 "haha"

Ah ! La première loi dit que mapper id sur un foncteur équivaut à appeler id sur ce même foncteur, mais dans cet exemple, ce n’est pas vrai pour notre foncteur CMaybe. Bien qu’il soit membre de la classe Functor, il n’obéit pas aux lois des foncteurs, et n’est donc pas un foncteur. Si quelqu’un utilisait notre type CMaybe comme un foncteur, il s’attendrait à ce qu’il obéisse aux lois des foncteurs, comme tout bon foncteur. Mais CMaybe échoue à être un foncteur bien qu’il puisse faire semblant d’en être un, et l’utiliser en tant que tel pourrait amener à un code erroné. Lorsqu’on utilise un foncteur, cela ne devrait pas importer que l’on compose des fonctions avant de les mapper ou que l’on mappe les fonctions une à une à la suite. Mais pour CMaybe, cela compte, parce qu’il compte combien de fois on a mappé sur lui. Pas cool ! Si l’on voulait que CMaybe obéisse aux lois des foncteurs, il faudrait que le champ Int ne soit pas modifié lors d’un fmap.

Au départ, les lois des foncteurs peuvent sembler un peu déroutantes et peu nécessaires, mais on finit par s’apercevoir que si un type obéit à ces lois, alors on peut présumer son comportement. Si un type obéit aux lois des foncteurs, on sait qu’appeler fmap sur une valeur va seulement mapper la fonction, rien de plus. Cela amène à un code plus abstrait et extensible, parce qu’on peut utiliser ces lois pour raisonner sur le comportement de n’importe quel foncteur et créer des fonctions qui opèrent de façon fiable sur n’importe quel foncteur.

Toutes les instances de Functor de la bibliothèque standard obéissent à ces lois, mais vous pouvez vérifier si vous ne me croyez pas. Et la prochaine fois que vous créez une instance de Functor, prenez une minute pour vous assurer qu’elle obéit aux lois des foncteurs. Une fois que vous avez utilisé assez de foncteurs, vous développez une intuition pour ces propriétés et comportements qu’ils ont en commun et il n’est plus dur de se rendre compte intuitivement qu’un type obéit ou non aux lois des foncteurs. Mais même sans intuition, vous pouvez toujours regarder l’implémentation ligne par ligne et voir si les lois sont respectées, ou trouver un contre-exemple.

On peut aussi regarder les foncteurs comme des choses qui retournent des valeurs dans un contexte. Par exemple, Just 3 retourne la valeur 3 dans le contexte où il peut ne pas y avoir de valeur retournée. [1, 2, 3] retourne trois valeurs - 1, 2 et 3, le contexte étant qu’il peut y avoir aucune ou plusieurs valeurs. La fonction (+3) retourne une valeur, qui dépend du paramètre qu’on lui donne.

Si vous imaginez les foncteurs comme des choses qui retournent des valeurs, vous pouvez imaginer mapper sur des foncteurs comme attacher des transformations à la sortie du foncteur pour changer les valeurs qu’il retourne. Lorsqu’on fait fmap (+3) [1, 2, 3], on attache la transformation (+3) à la sortie de [1, 2, 3], donc quand on observe un des nombres que la liste retourne, (+3) lui est appliqué. Un autre exemple est celui du mappage sur des fonctions. Quand on fait fmap (+3) (*3), on attache la transformation (+3) à ce qui sortira de (*3). On voit ainsi mieux pourquoi utiliser fmap sur des fonctions consiste juste à composer les fonctions (fmap (+3) (*3) est égal à (+3) . (*3), qui est égal à \x -> ((x*3)+3)), parce qu’on prend une fonction comme (*3) et qu’on attache la transformation (+3) à sa sortie. Le résultat est toujours une fonction, seulement quand on lui donne une valeur, elle sera multipliée par trois, puis passera par la transformation attachée où on lui ajoutera trois. C’est ce qui se passe avec la composition.

Foncteurs applicatifs

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êmes 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éfinie 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) où 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 écriref <$> 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é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 produit 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 action 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.

Le mot-clé newtype

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 la 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ébarasser 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.

Utiliser newtype pour créer des instances de classes de types

Souvent, on veut faire de nos types des instances de certaines classes de types, mais les paramètres de types ne correspondent pas à ce que l’on souhaite. Il est facile de faire une instance de Functor pour Maybe, parce que la classe de types Functor est définie comme :

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

Donc on peut démarrer en faisant :

instance Functor Maybe where

Et implémenter fmap. Tous les paramètres de type s’alignent parce que Maybe vient prendre la place de f dans la définition de la classe de types Functor et donc, si l’on considère fmap comme vu des Maybe, elle se comporte ainsi :

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

N’est-ce pas chouette ? Maintenant, si l’on voulait faire des tuples une instance de Functor de manière à ce que si l’on applique fmap sur un tuple, elle est appliquée à la première composante du tuple ? Ainsi, faire fmap (+3) (1, 1) donnerait (4, 1). Il s’avère qu’écrire cette instance est plutôt difficile. Avec Maybe, on disait juste instance Functor Maybe where parce que seuls les constructeurs de types prenant exactement un paramètre peuvent être des instances de Functor. Mais cela semble impossible pour quelque chose comme (a, b) de manière à ce que ce soit a qui change quand on utilise fmap. Pour contourner ce problème, on peut envelopper notre tuple dans un newtype de manière à ce que le deuxième paramètre de type représente la première composante du tuple :

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

À présent, on peut en faire une instance de Functor qui mappe la fonction sur la première composante :

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

Comme vous le voyez, on peut filtrer par motif les types définis par newtype. On filtre par motif pour obtenir le tuple sous-jacent, puis on applique f à la première composante de ce tuple, et on utilise le constructeur de valeurs Pair pour convertir à nouveau le tuple en Pair b a. Le type de fmap si elle ne marchait que sur nos paires serait :

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

À nouveau, on a dit instance Functor (Pair c) where, et ainsi, Pair c prend la place de f dans la définition de classe de Functor :

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

Maintenant, si l’on convertit un tuple en une Pair b a, on peut utiliser fmap sur celle-ci et la fonction sera mappée sur la première composante :

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

De la paresse de newtype

On a mentionné le fait que newtype était généralement plus rapide que data. La seule chose possible avec newtype consiste à transformer un type existant en un autre type, donc en interne, Haskell peut représenter les valeurs des types définis par newtype de la même façon que celles du type original, et n’a qu’à se souvenir que leur type est distinct. Ceci fait qu’en plus d’être plus rapide, newtype est également plus paresseux. Regardons ce que cela signifie.

Comme on l’a dit précédemment, Haskell est paresseux par défaut, ce qui signifie que c’est seulement lorsque l’on essaie d’afficher les résultats de fonctions que ceux-ci sont calculés. De plus, seuls les calculs nécessaires pour trouver le résultat de notre fonction sont exécutés. La valeur undefined en Haskell représente un calcul erroné. Si on essaie de l’évaluer (c’est-à-dire, de forcer Haskell à la calculer) en l’affichant sur le terminal, Haskell piquera une crise (ou en termes techniques, lèvera une exception) :

ghci> undefined
*** Exception: Prelude.undefined

Cependant, si on crée une liste qui contient quelques valeurs undefined mais qu’on ne demande que sa tête, qui n’est pas undefined, tout se passera bien parce qu’Haskell n’a pas besoin d’évaluer les autres éléments de la liste pour trouver son premier élément :

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

À présent, considérez ce type :

data CoolBool = CoolBool { getCoolBool :: Bool }

Un type de données algébrique tout droit sorti de l’usine, défini via le mot-clé data. Il n’a qu’un constructeur de valeurs, qui n’a qu’un champ de type Bool. Créons une fonction qui filtre par motif un CoolBool et retourne la valeur "hello" quelle que soit la valeur du booléen dans CoolBool :

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

Plutôt que d’appliquer cette fonction sur une valeur CoolBool normale, envoyons lui plutôt une balle courbe en l’appliquant sur un undefined !

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

Aïe ! Une exception ! Pourquoi est-ce que cette exception a été levée ? Les types définis avec le mot-clé data peuvent avoir plusieurs constructeurs de valeurs (bien que CoolBool n’en ait qu’un). Ainsi, pour savoir si la valeur donnée à notre fonction correspond au motif (CoolBool _), Haskell doit l’évaluer juste assez pour voir quel constructeur de valeur a été utilisé pour la créer. Et lorsqu’on essaie d’évaluer la valeur undefined, même un tout petit peu, une exception est levée.

Plutôt que le mot-clé data pour CoolBool, essayons d’utiliser newtype :

newtype CoolBool = CoolBool { getCoolBool :: Bool }

Pas besoin de changer la fonction helloMe, parce que la syntaxe de filtrage par motif est la même pour newtype que pour data. Faisons-la même chose ici et appliquons helloMe à une valeur undefined :

ghci> helloMe undefined
"hello"

Ça a marché ! Hmmm, pourquoi cela ? Eh bien, comme on l’a dit, quand on utilise newtype, Haskell peut représenter en interne les valeurs du nouveau type de la même façon que les valeurs originales. Il n’a pas besoin d’ajouter une nouvelle boîte autour, mais seulement de se rappeler du fait que les valeurs ont un type différent. Et parce qu’Haskell sait que les types créés avec le mot-clé newtype ne peuvent avoir qu’un seul constructeur, il n’a pas besoin d’évaluer la valeur passée à la fonction pour savoir qu’elle se conforme au motif (CoolBool _), puisque les types créés avec newtype ne peuvent avoir qu’un seul constructeur de valeurs et qu’un seul champ !

Cette différence de comportement peut sembler triviale, mais elle est en fait assez importante pour nous aider à réaliser que, bien que les types créés avec data et newtype se comportent de façon similaire du point de vue du programmeur parce qu’ils ont chacun des constructeurs de valeurs et des champs, ils sont en fait deux mécanismes différents. Alors que data peut créer de nouveaux types à partir de rien, newtype ne peut créer de nouveau type qu’à partir d’un type existant. Le filtrage par motif sur les valeurs newtype ne sort pas les choses d’une boîte (comme le fait data), mais convertit plutôt un type en un autre immédiatement.

type vs. newtype vs. data

À ce point, vous êtes peut-être perdu concernant les différences entre type, data et newtype, alors rafraîchissons-nous la mémoire.

Le mot-clé type crée des synonymes de types. Cela signifie qu’on donne simplement un autre nom à un type existant, pour qu’il soit plus simple d’en parler. Par exemple, ceci :

type IntList = [Int]

Tout ce que cela fait, c’est nous permettre de faire référence à [Int] en tapant IntList. Les deux peuvent être utilisés de manière interchangeable. On n’obtient pas de constructeur de valeurs IntList ou quoi que ce soit du genre. Puisque [Int] et IntList sont deux façons de parler du même type, peu importe laquelle on utilise dans nos annotations de types :

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

On utilise les synonymes de types lorsqu’on veut rendre nos signatures de type plus descriptives en donnant des noms aux types qui nous disent quelque chose sur le contexte des fonctions où ils sont utilisés. Par exemple, quand on a utilisé une liste associative qui a pour type [(String,String)] pour représenter un répertoire téléphonique, on lui a donné le synonyme de type PhoneBook afin que les signatures de type des fonctions soient plus simples à lire.

Le mot-clé newtype sert à prendre des types existants et les emballer dans de nouveaux types, principalement parce que ça facilite la création d’instances de certaines classes de types. Quand on utilise newtype pour envelopper un type existant, le type qu’on obtient est différent du type original. Si l’on crée le nouveau type suivant :

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

On ne peut pas utiliser ++ pour accoler une CharList et une liste ayant pour type [Char]. On ne peut même pas utiliser ++ pour coller ensemble deux CharList, parce que ++ ne fonctionne que pour les listes, et le type de CharList n’est pas une liste, même si l’on peut dire qu’il en contient une. On peut, toutefois, convertir deux CharList en listes, utiliser ++ sur celles-ci, puis les reconvertir en CharList.

Quand on utilise la syntaxe des enregistrements dans notre déclaration newtype, on obtient des fonctions pour convertir entre le type original et le nouveau type : dans une sens, avec le constructeur de valeurs de notre newtype, et dans l’autre sens, avec la fonction qui extrait la valeur du champ. Le nouveau type n’est pas automatiquement fait instance des classes de types du type original, donc il faut les dériver ou les écrire manuellement.

En pratique, on peut imaginer les déclarations newtype comme des déclarations data qui n’ont qu’un constructeur de valeurs, et un seul champ. Si vous vous retrouvez à écrire une telle déclaration data, pensez à utiliser newtype.

Le mot-clé data sert à créer vos propres types de données, et avec ceux-ci, tout est possible. Ils peuvent avoir autant de constructeurs de valeurs et de champs que vous le voulez, et peuvent être utilisés pour implémenter n’importe quel type de données algébrique vous-même. Tout, des listes aux Maybe en passant par les arbres.

Si vous voulez seulement de plus jolies signatures de type, vous voulez probablement des synonymes de types. Si vous voulez prendre un type existant et l’envelopper dans un nouveau type pour en faire une instance d’une classe de types, vous voulez sûrement un newtype. Et si vous voulez créer quelque chose de neuf, les chances sont bonnes que le mot-clé data soit ce qu’il vous faut.

Monoïdes

Les classes de types en Haskell sont uilisé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 évident : 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.

Les listes sont des monoïdes

Oui, les listes sont des monoïdes ! Comme on l’a vu, la fonction ++ et la liste vide [] forment un monoïde. L’instance est très simple :

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

Les listes sont une instance de la classe de types Monoid quel que soit le type des éléments qu’elles contiennent. Remarquez qu’on a écrit instance Monoid [a] et pas instance Monoid [], parce que Monoid nécessite un type concret en instance.

En testant cela, pas de surprises :

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]
[]

Remarquez qu’à la dernière ligne, nous avons dû écrire une annotation de type explicite, parce que si l’on faisait seulement mempty, GHCi ne saurait pas quelle instance utiliser, on indique donc qu’on veut celle des listes. On a pu utiliser le type général [a] (plutôt qu’un type spécifique comme [Int] ou [String]) parce que la liste vide peut se faire passer pour n’importe quel type de liste.

Puisque mconcat a une implémentation par défaut, on l’obtient gratuitement lorsqu’on crée une instance de Monoid. Dans le cas des listes, mconcat s’avère être juste concat. Elle prend une liste de listes et l’aplatit, parce que c’est équivalent à faire ++ entre toutes les listes adjacentes d’une liste.

Les lois des monoïdes sont en effet respectées par l’instance des listes. Quand on a plusieurs listes et qu’on les mappend (ou ++) ensemble, peu importe l’ordre dans lequel l’opération est effectuée, parce qu’au final, elles sont toutes à la suite l’une de l’autre de toute façon. De plus, la liste vide se comporte bien comme un élément neutre, donc tout va bien. Remarquez que les monoïdes ne nécessitent pas que a `mappend` b soit égal à b `mappend` a. Dans le cas des listes, clairement ce n’est pas le cas.

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

Et ce n’est pas un problème. Le fait que pour la multiplication, 3 * 5 et 5 * 3 soient identiques n’est qu’une propriété de la multiplication, mais n’a pas à être vrai pour tous les monoïdes (et ne l’est pas pour la plupart d’ailleurs).

Product et Sum

On a déjà examiné une façon pour les nombres d’être considérés comme des monoïdes. La fonction binaire est * et l’élément neutre est 1. Il s’avère que ce n’est pas la seule façon pour les nombres de former un monoïde. Une autre façon consiste à prendre pour fonction binaire + et pour élément neutre 0.

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

Les lois des monoïdes tiennent, parce qu’ajouter 0 à tout nombre le laisse inchangé. Et l’addition est associative, donc pas de problème. À présent qu’il y a deux manières toute aussi valide l’une que l’autre pour les nombres d’être des monoïdes, quelle voie choisir ? Eh bien, pas besoin de choisir. Souvenez-vous, quand il y a plusieurs façons pour un type d’être une instance de la même classe de types, on peut l’envelopper dans un newtype et faire de ce nouveau type une autre instance de la même classe de types. On a le beurre et l’argent du beurre.

Le module Data.Monoid exporte deux types pour cela, Product et Sum. Product est défini comme :

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

Simple, un enrobage avec newtype, avec un paramètre de type et quelques instance dérivées. Son instance de Monoid ressemble à :

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

mempty est simplement 1 enveloppé dans un constructeur Product. mappend filtre par motif sur le constructeur Product, multiplie les deux nombres, et enveloppe à nouveau le résultat. Comme vous le voyez, il y a une contrainte de classe Num a. Cela veut dire que Product a est une instance de Monoid pour tout a qui est une instance de Num. Pour utiliser Product a en tant que monoïde, il faut faire un peu d’emballage et de déballage.

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

C’est pratique pour démontrer le comportement de la classe de types Monoid, mais personne de bien sensé n’irait multiplier des nombres de cette façon plutôt que d’écrire simplement 3 * 9 et 3 * 1. Mais un peu plus tard, nous verrons comment ces instances de Monoid qui peuvent sembler triviales s’avèrent pratiques.

Sum est défini comme Product et l’instance est également similaire. On l’utilise ainsi :

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

Any et All

Un autre type qui peut agir comme un monoïde de deux façons distinctes et légitimes est Bool. La première façon utilise la fonction ou || comme fonction binaire, avec False pour élément neutre. En logique, ou est True si n’importe lequel de ses paramètres est True, sinon c’est False. Ainsi, en utilisant False comme élément neutre, on retourne bien False en faisant ou avec False, et True en faisant ou avec True. Le newtype Any est une instance de monoïde de cette manière. Il est défini ainsi :

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

Quant à l’instance :

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

Il s’appelle Any parce que x `mappend` y sera True si n’importe laquelle (NDT : en anglais, any) de ses valeurs est True. Même si trois ou plus Bool enveloppés dans Any sont mappend ensemble, le résultat sera toujours True lorsque n’importe lequel d’entre eux est True :

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

L’autre façon de faire une instance de Monoid pour Bool est un peu l’opposé

utiliser && comme fonction binaire et True comme élément neutre. Le et logique retourne True si ses deux paramètres valent True. Voici la déclaration newtype, rien d’extraordinaire :

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

Et l’instance :

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

Quand on mappend des valeurs de type All, le résultat sera True seulement si toutes (NDT : en anglais, all), les valeurs passées à mappend sont True :

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

Tout comme avec la multiplication et l’addition, on utilise généralement les fonctions binaires directement plutôt que d’envelopper les valeurs dans des newtype pour ensuite utiliser mappend et mempty. mconcat semble utile pour Any et All mais généralement, il est plus simple d’utiliser les fonctions or et and qui prennent une liste de Bool et retourne True si, respectivement, l’une d’elles est True ou toutes sont True.

Le monoïde Ordering

Hé, vous vous souvenez du type Ordering ? C’est le type retourné lorsqu’on compare des choses, qui peut avoir trois valeurs : LT, EQ et GT, qui signifient inférieur, égal et supérieur respectivement :

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

Avec les listes, les nombres et les valeurs booléennes, on voit que trouver des monoïdes est juste l’affaire de regarder ce qu’on utilisait déjà afin de voir si ces choses présentent un comportement monoïdal. Pour Ordering, il faut y regarder à deux fois avant de reconnaître le monoïde, mais il s’avère que son instance de Monoid est tout aussi intuitive que celles recontrées précédemment, et plutôt utile également :

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

L’instance est créée de la sorte : quand on mappend deux valeurs Ordering, celle de gauche est préservée, à moins que la valeur à gauche soit EQ, auquel cas celle de droite est le résultat. Le neutre est EQ. Au départ, ça peut sembler arbitraire, mais cela ressemble en fait beaucoup à la façon donc on compare lexicographiquement des mots. On compare d’abord les premières lettres de chaque mot, et si elles diffèrent, on peut immédiatement décider de l’ordre des mots dans un dictionnaire. Cependant, si elles sont égales, alors on doit comparer la prochaine paire de lettres et répéter le procédé.

Par exemple, si l’on voulait comparer lexicographiquement les mots “ox” et “on”, on pourrait commencer par comparer la première lettre de chaque mot, voir qu’elles sont égales, puis comparer la seconde lettre de chaque mot. On voit que 'x' est lexicographiquement supérieure à 'n', et on peut donc savoir l’ordre des deux mots. Pour se faire une intuition sur le fait qu’EQ soit l’identité, on peut remarquer que si l’on glissait la même lettre à la même position dans les deux mots, leur ordre lexicographique ne changerait pas. "oix" est toujours lexicographiquement supérieur à "oin".

Il est important de noter que dans l’instance de Monoid pour Ordering, x `mappend` y n’est pas égal à y `mappend` x. Puisque le premier paramètre est conservé à moins d’être EQ, LT `mappend` GT retourne LT, alors que GT `mappend` LT retournera GT :

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

OK, comment est-ce que ce monoïde est utile ? Mettons que vous soiyez en train d’écrire une fonction qui prend deux chaînes de caractères, compare leur longueur, et retourne un Ordering. Mais si les chaînes sont de même longueur, au lieu de retourner EQ immédiatement, vous voulez les comparer lexicographiquement. Une façon de faire serait :

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

On appelle a le résultat de la comparaison des longueurs, et b celui de la comparaison lexicographique, et si les longueurs s’avèrent égales, on retourne l’ordre lexicographique.

Mais, en mettant à profit notre compréhension d’Ordering comme un monoïde, on peut réécrire cette fonction d’une manière bien plus simple :

import Data.Monoid

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

On peut essayer :

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

Souvenez-vous, quand on fait mappend, le paramètre de gauche est toujours gardé à moins d’être EQ, auquel cas celui de droite est gardé. C’est pourquoi on a placé la comparaison qu’on considère comme le critère le plus important en premier paramètre. Si l’on voulait étendre la fonction pour comparer le nombre de voyelles comme deuxième critère en importance, on pourrait modifier la fonction ainsi :

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")

On a fait une fonction auxiliaire qui prend une chaîne de caractères et nous dit combien de voyelles elle contient en filtrant seulement les lettres qui sont dans la chaîne "aeiou", puis en appliquant length au résultat filtré.

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

Très cool. Ici, on voit comme dans le premier exemple les longueurs sont différentes et donc LT est retourné, parce que "zen" est moins longue qu’"anna". Dans le deuxième exemple, les longueurs sont égales, mais la deuxième chaîne a plus de voyelles, donc LT est retourné à nouveau. Dans le troisième exemple, elles ont la même longueur et le même nombre de voyelles, donc elles sont comparées lexicographiquement et "zen" gagne.

Le monoïde Ordering est très cool parce qu’il permet de comparer facilement des choses selon plusieurs critères en plaçant ces critères dans l’ordre du plus important au moins important.

Maybe le monoïde

Regardons les différentes façons de faire de Maybe une instance de Monoid, et comment ces instances sont utiles.

Une façon est de traiter Maybe comme un monoïde seulement lorsque son paramètre de type a est un monoïde également, et d’implémenter mappend de façon à ce qu’il utilise l’opération mappend des valeurs enveloppées dans le Just. Nothing est l’élément neutre, et ainsi si l’une des deux valeurs qu’on mappend est Nothing, on conserve l’autre valeur. Voici la déclaration d’instance :

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)

Remarquez la contrainte de classe. Elle dit que Maybe a est une instance de Monoid seulement si a est une instance de Monoid. Si l’on mappend quelque chose avec Nothing, le résultat est cette chose. Si on mappend deux valeurs Just, le contenu des Just est mappend et est enveloppé de nouveau dans un Just. On peut faire cela parce que la contrainte de classe nous garantit que le type à l’intérieur du Just est une instance de Monoid.

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})

Cela s’avère utile lorsque vous utilisez des monoïdes comme résultats de calculs pouvant échouer. Grâce à cette instance, on n’a pas besoin de vérifier si les calculs ont échoué en regardant si les valeurs sont Nothing ou Just, on peut simplement continuer à les traiter comme des monoïdes ordinaires.

Mais, et si le type du contenu de Maybe n’est pas une instance de Monoid ? Remarquez que dans la déclaration d’instance précédente, on ne se repose sur le fait que le contenu soit un monoïde que lorsque mappend est appliqué à deux valeurs Just. Mais si l’on ne sait pas si le contenu est un monoïde, on ne peut pas faire mappend sur ces valeurs, donc que faire ? Eh bien, on peut par exemple toujours jeter la deuxième valeur et garder la première. Pour cela, le type First a existe, et voici sa définition :

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

On prend un Maybe a et on l’enveloppe avec un newtype. L’instance de Monoid est comme suit :

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

Comme on l’a dit. mempty est Nothing emballé dans un constructeur de newtype First. Si le premier paramètre de mappend est une valeur Just, on ignore le second. Si le premier est Nothing, alors on retourne l’autre, qu’il soit un Just ou un Nothing.

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'

First est utile quand on a plein de valeurs Maybe et qu’on souhaite juste savoir s’il y a un Just dans le tas. La fonction mconcat s’avère utile :

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

Si l’on veut un monoïde sur Maybe a de manière à ce que le deuxième paramètre soit gardé lorsque les deux paramètres de mappend sont des valeurs Just, Data.Monoid fournit un type Last a, qui fonctionne comme First a, à l’exception que c’est la dernière valeur différente de Nothing qui est gardée par mappend et mconcat :

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

Utiliser des monoïdes pour plier des structures de données

Une des façons les plus intéressantes de mettre les monoïdes à l’usage est de les utiliser pour nous aider à définir des plis sur diverses structures de données. Jusqu’ici, nous n’avons fait que des plis sur des listes, mais les listes ne sont pas les seules structures de données pliables. On peut définir des plis sur presque toute structure de données. Les arbres se prêtent particulièrement bien à l’exercice du pli.

Puisqu’il y a tellement de structures de données qui fonctionnent bien avec les plis, la classe de types Foldable a été introduite. Comme Functor est pour les choses sur lequelles on peut mapper, Foldable est pour les choses qui peuvent être pliées ! Elle est trouvable dans Data.Foldable et puisqu’elle exporte des fonctions dont les noms sont en collision avec ceux du Prelude, elle est préférablement importée qualifiée (et servie avec du basilic) :

import qualified Foldable as F

Pour nous éviter de précieuses frappes de clavier, on l’importe qualifiée par F. Bien, donc quelles sont les fonctions que cette classe de types définit ? Eh bien, parmi celles-ci sont foldr, foldl, foldr1, foldl1. Hein ? Mais on connaît déjà ces fonctions, quoi de neuf ? Comparons le type de foldr dans Foldable avec celui de foldr du Prelude pour voir ce qui diffère :

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

Ah ! Donc, alors que foldr prend une liste et la plie, le foldr de Data.Foldable accepte tout type qui peut être plié, pas seulement les listes ! Comme on peut s’y attendre, les deux fonctions font la même chose sur les listes :

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

Ok, quelles autres structures peuvent être pliées ? Eh bien, le Maybe qu’on connaît tous et qu’on aime tant !

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

Mais plier une simple valeur Maybe n’est pas très intéressant, parce que quand il s’agit de se plier, elle se comporte comme une liste avec un élément si c’est un Just, et comme une liste vide si c’est Nothing. Examinons donc une structure de données un peu plus complexe.

Vous rappelez-vous la structure de données arborescente du chapitre Créer nos propres types et classes de types ? On l’avait définie ainsi :

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

On disait qu’un arbre était soit un arbre vide qui ne contient aucune valeur, soit un neud qui contient une valeur ainsi que deux autres arbres. Après l’avoir défini, on en a fait une instance de Functor et on a gagné la possibilité de faire fmap sur ce type. À présent, on va en faire une instance de Foldable afin de pouvoir le plier. Une façon de faire d’un constructeur de types une instance de Foldable consiste à implémenter directement foldr. Une autre façon, souvent bien plus simple, consiste à implémenter la fonction foldMap, qui fait aussi partie de la classe de types Foldable. foldMap a pour type :

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

Son premier paramètre est une fonction qui prend une valeur du type que notre structure de données pliable contient (ici dénoté a) et retourne une valeur monoïdale. Son second paramètre est une structure pliable contenant des valeurs de type a. Elle mappe la fonction sur la structure pliable, produisant ainsi une structure pliable contenant des valeurs monoïdales. Ensuite, en faisant mappend entre toutes ces valeurs monoïdales, elle les joint en une unique valeur monoïdale. Cette fonction peut paraître bizarre pour l’instant, mais on va voir qu’elle est très simple à implémenter. Ce qui est aussi cool, c’est qu’il suffit simplement d’implémenter cette fonction pour que notre type soit une instance de Foldable. Ainsi, si l’on implémente foldMap pour un type, on obtient foldr et foldl sans effort !

Voici comment un Tree est fait instance de Foldable :

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

On pense ainsi : si l’on nous donne une fonction qui prend un élément de notre arbre et retourne une valeur monoïdale, comment réduit-on notre arbre à une simple valeur monoïdale ? Quand nous faisions fmap sur notre arbre, on appliquait la fonction mappée au nœud, puis on mappait récursivement la fonction sur le sous-arbre gauche et sur le sous-arbre droit. Ici, on nous demande non seulement de mapper la fonction, mais également de joindre les résultats en une simple valeur monoïdale à l’aide de mappend. On considère d’abord le cas de l’arbre vide - un pauvre arbre tout triste et solitaire, sans valeur ni sous-arbre. Il n’a pas de valeur qu’on puisse passer à notre fonction créant des monoïdes, donc si notre arbre est vide, la valeur monoïdale sera mempty.

Le cas d’un nœud non vide est un peu plus intéressant. Il contient deux sous-arbres ainsi qu’une valeur. Dans ce cas, on foldMap récursivement la même fonction f sur les sous-arbres gauche et droit. Souvenez-vous, notre foldMap retourne une simple valeur monoïdale. On applique également la fonction f à la valeur du nœud. À présent, nous avons trois valeurs monoïdales (deux venant des sous-arbres et une venant de l’application de f sur la valeur du nœud) et il suffit de les écraser en une seule valeur. Pour ce faire, on utilise mappend, et naturellement, le sous-arbre gauche vient avant la valeur du nœud, suivi du sous-arbre droit.

Remarquez qu’on n’a pas eu besoin d’écrire la fonction qui prend une valeur et retourne une valeur monoïdale. On la reçoit en paramètre de la fonction foldMap et tout ce qu’on a besoin de décider est où l’appliquer et comment joindre les monoïdes qui en résultent.

Maintenant qu’on a une instance de Foldable pour notre type arborescent, on a foldr et foldl gratuitement ! Considérez cet arbre :

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

Il a 5 pour racine, puis son nœud gauche contient 3 avec 1 à sa gauche et 6 à sa droite. Le nœud droit de la racine contient 9 avec un 8 à sa gauche et un 10 tout à droite. Avec une instance de Foldable, on peut faire tous les plis qu’on fait sur des listes :

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

foldMap ne sert pas qu’à créer les instances de Foldable, elle sert également à réduire une structure à une simple valeur monoïdale. Par exemple, si l’on voulait savoir si n’importe quel nombre de notre arbre est égal à 3, on pourrait faire :

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

Ici, \x -> Any $ x == 3 est une fonction qui prend un nombre et retourne une valeur monoïdale, dans ce cas un Bool enveloppé en Any. foldMap applique la fonction à chaque élément de l’arbre, puis réduit les monoïdes résultants en une unique valeur monoïdale à l’aide de mappend. Si l’on faisait :

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

Tous les nœuds de notre arbre contiendraient la valeur Any False après avoir appliqué la fonction dans la lambda à chacun d’eux. Pour valoir True, mappend sur Any doit avoir au moins un True passé en paramètre. C’est pourquoi le résultat final est False, ce qui est logique puisqu’aucune valeur de notre arbre n’excède 15.

On peut aussi facilement transformer notre arbre en une liste en faisant foldMap avec la fonction \x -> [x]. En projetant d’abord la fonction sur l’arbre, chaque élément devient une liste singleton. Puis, mappend a lieu entre tous ces singletons et retourne une unique liste qui contient tous les éléments de notre arbre :

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

Ce qui est vraiment cool, c’est que toutes ces techniques ne sont pas limitées aux arbres, elles fonctionnent pour toute instance de Foldable.