Les programmeurs Haskell aiment bien l'abstraction. Les classes de types servent à ça : elles permettent de déclarer des opérations qu'on peut effectuer sur beaucoup de types différents. Il existe des classes plutôt simples, comme Num ou Eq : on comprend très vite leur utilité et comment s'en servir. Mais d'autres sont plus compliquées : c'est le cas des classes Functor et Applicative que vous allez découvrir dans ce chapitre. Ils permettent d'abstraire beaucoup d'opérations courantes, comme par exemple le fait d'appliquer à une fonction "pure" des arguments donc l'évaluation peut échouer, entrainer des effets sur l'extérieur ou dépendre des opérations effectuées précédemment.
Les foncteurs
Avant de commencer à expliquer les foncteurs, voilà la classe en question :
1 2 | class Functor f where fmap :: (a -> b) -> f a -> f b |
Différentes sortes de constructeurs de types
Contrairement à ce que vous avez pu voir avant, le paramètre f de cette classe n'est pas un type : f a n'a pas de sens si f est un type. Par contre, si on remplace f par un constructeur de type (comme par exemple Maybe, on trouve fmap :: (a -> b) -> Maybe a -> Maybe b. Maybe n'est pas un type en lui-même, mais on peut lui passer un type pour obtenir un type : c'est pour cela qu'on dit que c'est un constructeur de type.
On peut aussi créer des types prenant un constructeur de type prenant un paramètre en paramètre. On rajoute une instance de Show qui ne fait rien pour pouvoir l'utiliser plus facilement dans ghci.
1 2 3 4 | data OfInt c = OfInt (c Int) instance Show (OfInt c) where show _ = "OfInt" |
On peut construire quelques valeurs de ce type (mais pas les afficher, parce qu'on n'a pas défini de vraie instance de Show).
1 2 3 4 5 6 7 8 9 10 | *Main> :set +t (Active l'affichage des types après chaque expression) *Main> OfInt [] OfInt it :: OfInt [] *Main> OfInt (Just 42) OfInt it :: OfInt Maybe *Main> OfInt (Right 12) OfInt it :: OfInt (Either a) |
On pourrait même créer des données de type OfInt IO contenant un IO Int, c'est-à-dire une action IO renvoyant un entier. Le troisième exemple est le plus intéressant à voir : on a appliqué partiellement le type Either à a, et on a obtenu quelque chose d'équivalent à un constructeur de type comme Maybe.
Vous vous doutez peut-être de la suite : il y a bien des types là-dessous, ou plutôt des types de types. Ils sont appelés kind (sortes), et on peut les voir avec la commande :kind dans ghci. Un type a le kind *, et on utilise, comme pour les types normaux, -> pour noter une fonction. Quelques exemples :
1 2 3 4 5 6 7 8 9 10 11 12 | *Main> :kind Int Int :: * *Main> :kind Maybe Maybe :: * -> * *Main> :kind Either Int Either Int :: * -> * *Main> :kind Either Either :: * -> * -> * *Main> :kind OfInt OfInt :: (* -> *) -> * *Main> :kind (->) (->) :: ?? -> ? -> * |
Le dernier kind peut vous intriguer un peu. (->), qui permet de définir le type des fonctions, est un constructeur de type comme les autres. Cependant, les kinds de ses arguments sont ?? et ?, et pas * comme on pourrait s'y attendre normalement. En réalité, ?? et ? sont des kind qui contiennent le kind , en plus d'autres kind particuliers beaucoup moins utilisés. Vous pouvez donc, pour l'instant, les considérer comme des .
Qu'est-ce qu'un foncteur
Un foncteur dispose donc, d'après la définition, d'une fonction fmap. Un premier exemple de foncteur, c'est les listes : il suffit de poser fmap = map. Sur les listes, fmap f applique donc f à tous les éléments contenus dans la liste. On peut utiliser cette idée pour trouver les instances de Functor pour d'autres types de conteneurs.
Par exemple, on peut définir une instance de Functor pour Maybe (vous n'avez pas besoin de charger cette définition, elle est déjà dans le Prelude) :
1 2 3 | instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just a) = Just (f a) |
1 2 3 4 | Prelude> fmap (*2) Nothing Nothing Prelude> fmap (*2) (Just 21) Just 42 |
On peut aussi, de la même façon, définir une instance pour Either. Cependant, Either prend deux paramètres : il faut donc l'appliquer partiellement pour obtenir un type qui prend un seul paramètre :
1 2 3 | instance Functor (Either a) where fmap f (Left l) = Left l fmap f (Right r) = Right (f r) |
Si on définit un autre conteneur, par exemple un arbre, on peut aussi définir une instance associée :
1 2 3 4 5 6 | data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving Show instance Functor Tree where fmap f Leaf = Leaf fmap f (Branch l e r) = Branch (fmap f l) (f e) (fmap f r) |
Il y a une instance de Functor pour les paires : on applique la fonction au deuxième élément, en laissant le premier inchangé.
1 2 | instance Functor ((,) e) where fmap f (e, x) = (e, f x) |
Sur des conteneurs, pour définir une instance de Functor, il suffit donc d'appliquer la fonction à toutes les valeurs de type a. Mais Functor ne s'applique pas qu'à des conteneurs : si vous listez les instances de Functor définies par défaut avec la commande :info, vous trouverez qu'IO est une instance de Functor :
1 2 3 4 5 6 | Prelude> :info Functor class Functor f where fmap :: (a -> b) -> f a -> f b -- Defined in GHC.Base instance Functor Maybe -- Defined in Data.Maybe instance Functor IO -- Defined in GHC.IOBase instance Functor [] -- Defined in GHC.Base |
En effet, on peut définir une fonction mapIO comme ceci (elle est déjà définie dans Control.Monad et s'appelle liftM).
1 2 3 4 | mapIO :: (a -> b) -> IO a -> IO b mapIO f x = do vx <- x return $ f vx |
On peut aussi définir une instance pour les fonctions : la première ligne est instance Functor ((->) r) where. Comme avec les opérateurs normaux, on a transformé -> en un opérateur utilisable comme une fonction, et on l'a appliqué partiellement. Le type de fmap doit donc être : fmap :: (a -> b) -> (->) r a -> (->) r b, c'est-à-dire : fmap :: (a -> b) -> (r -> a) -> (r -> b) : on retrouve la composition de fonctions, et fmap = (.).
Des règles à respecter
Quand on écrit une instance de Functor, on s'attend à ce que quelques règles soient respectées : le foncteur doit bien se comporter par rapport à l'identité et la composition de fonctions. On peut écrire ces règles comme ceci :
1 2 | fmap id == id fmap (f . g) == fmap f . fmap g |
Vous pouvez définir des instances ne respectant pas ces lois, mais c'est une mauvaise idée puisque certaines fonctions sur les foncteurs peuvent supposer qu'elles sont vraies, et donc donner un résultat faux avec votre foncteur.
On peut par exemple vérifier que notre instance de Maybe respecte ces lois : on a fmap id Nothing == Nothing et fmap id (Just a) == Just (id a) == Just a, donc la première loi est respectée. Pour la deuxième loi, fmap (f . g) Nothing == Nothing et fmap f (fmap g Nothing) == fmap f Nothing == Nothing, et pour Just : fmap f (fmap g (Just a)) == fmap f (Just (g a)) == Just (f (g a)) == Just ((f . g) a) == fmap (f . g) (Just a). Les deux lois sont respectées, on a donc une instance valide.
Composer des foncteurs
La structure des foncteurs est assez simple, mais elle a l'avantage de s'appliquer à beaucoup de types. Il est aussi très facile de composer des foncteurs simples pour créer des foncteurs plus complexes. Par exemple, une liste de liste est un foncteur : on peut créer une fonction map2 f = map (map f), c'est-à-dire : map2 = map . map. Cependant, on ne peut pas écrire une instance de Functor pour les listes de listes, puisqu'ensuite, quand on utilise fmap, il n'est pas toujours possible de déterminer si on souhaite utiliser fmap sur les listes (avec les listes comme éléments), ou sur les listes de listes.
On peut de même composer généralement deux foncteurs f et g, en définissant un type O f g représentant la composition des deux constructeurs de types :
1 2 3 4 5 | newtype O f g a = O (f (g a)) deriving Show instance (Functor f, Functor g) => Functor (O f g) where fmap f (O v) = O $ fmap (fmap f) v |
newtype permet, comme data, de définir un nouveau type, mais avec quelques restrictions : le type ne doit avoir qu'un seul constructeur, qui ne prend qu'un argument. Ces restrictions permettent au compilateur de ne pas avoir à mettre un constructeur et à l'enlever : à l'exécution, le type est exactement le même que le type original, mais il est différent pour la vérification de types. Cette astuce sert souvent à créer une copie d'un type, mais ayant des instances différentes de certaines classes de types. On a aussi indiqué une contrainte sur l'instance, notée (Functor f, Functor g) => : pour que O f g soit un foncteur avec cette définition, f et g doivent avoir des instances de Functor.
Si vous ne voulez pas , vous pouvez utiliser fmap . fmap. Avec l'instance de Functor pour les fonctions, on peut aussi écrire fmap2 = fmap fmap fmap (et pour cumuler les niveaux, rajoutez des fmap).
Il existe d'autres manières de composer des foncteurs. Par exemple, une paire de foncteurs est aussi un foncteur.
1 2 3 4 5 | newtype P f g a = P (fmap f a, fmap g a) deriving Show instance (Functor f, Functor g) => Functor (P f g) where fmap f (P (a,b)) = P (f a, f b) |
On peut tester ces deux instances :
1 2 3 4 5 6 | *Main> fmap fmap fmap (*2) [[1..2],[5..9]] [[2,4],[10,12,14,16,18]] *Main> fmap (*2) (O [[1..2],[5..9]]) O [[2,4],[10,12,14,16,18]] *Main> fmap (*2) (P (Just 12, [1,2,3])) P (Just 24,[2,4,6]) |
Qu'est-ce qui n'est pas un foncteur ?
Vous avez vu qu'on peut déclarer une instance valide de Functor pour beaucoup de types. Mais existe-t-il des types pour lesquels il n'y a pas d'instance de Functor ? La réponse est oui.
Il y a d'abord le problème des constructeurs de types qui prennent une contrainte sur leur argument : par exemple, le type Set du module Data.Set sert à stocker un ensemble de valeur. Pour des raisons d'efficacité, il suppose que les valeurs sont stockées dans un certain ordre dans l'ensemble (la structure de données utilisée est une variante des arbres binaires de recherche). Après l'opération fmap, on est donc obligé de retrier la structure, mais pour ça il faut rajouter une contrainte sur le type d'arrivée pour qu'il soit ordonné. On a donc une sorte de foncteur restreint, avec une opération (Ord b) => (a -> b) -> Set a -> Set b, mais pas de foncteur général.
Mais certains types ne sont même pas des foncteurs restreints. C'est par exemple le cas de l'application de fonction, par rapport à son premier argument, donc en fixant le deuxième :
1 | newtype RFun b a = RFun { unRFun :: a -> b } |
On utilise ici la syntaxe des enregistrements, puisqu'elle permet de créer en même temps la fonction permettant de sortir le type original du conteneur créé par newtype. Si on voulait une instance de Functor pour RFun t, la fonction fmap aurait le type fmap :: (a -> b) -> RFun t a -> RFun t b, c'est-à-dire un type équivalent à (a -> b) -> (a -> t) -> (b -> t). Mais il n'existe pas de fonctions de ce type respectant les règles pour un foncteur (intuitivement, comme les types a, b et t sont inconnus, on ne peut utiliser que les fonctions prises en paramètre pour les traiter et un paramètre de type b, mais on ne peut pas construire de valeur de type t de cette façon). Le type des fonctions est donc un foncteur pour la valeur à droite de la flèche (le type renvoyé), mais pas pour le type pris en entrée. On peut cependant définir une sorte d'«anti foncteur» qui serait l'équivalent des foncteurs pour ce type, avec une fonction mapf :: (a -> b) -> (f b -> f a). Ici, la fonction devrait (si on oublie RFun) être de type mapf :: (a -> b) -> (b -> t) -> (a -> t), et la définition mapf = flip (.) convient.
Quelques utilisations des foncteurs
On peut par exemple utiliser les foncteurs pour créer plus facilement des fonctions pouvant échouer (donc renvoyant une valeur de type Maybe a ou Either a b). Par exemple, si on souhaite créer un site web regroupant des informations sur les meilleures glaces, on dispose d'une base de données (qu'on représentera ici par une liste d'enregistrements) et une fonction rechercher renvoyant une glace par son nom. On a aussi une fonction pageGlace, renvoyant la page associée à une glace.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | data Glace = Glace { parfum :: String, fabriquant :: String, note :: Int } deriving Show base = [Glace "Framboise" "Ice Crime" 20, Glace "Chocolat" "Miam Glaces" 17, Glace "Vanille" "Pole Sud" 16] rechercher :: [Glace] -> String -> Either String Glace rechercher base gl = case filter (\g -> parfum g == gl) base of [] -> Left "Cette glace n'existe pas" x:_ -> Right x pageGlace :: Glace -> String pageGlace g = "Glace goût " ++ parfum g ++ " fabriquée par " ++ fabriquant g ++ ". Note des lecteurs : " ++ show (note g) |
Pour afficher la page d'une glace ou une erreur (si on suppose que le serveur web s'occupera de générer automatiquement un message d'erreur avec une réponse Left), il suffit donc de faire servirPage g = fmap pageGlace (rechercher base g). Si la base de données était stockée à l'extérieur, le résultat de rechercher serait de type IO (Either String Glace). Mais comme la composée de deux foncteurs est un foncteur, le traitement peut se poursuivre presque de la même manière, et il n'y a pas besoin de changer la fonction pageGlace.
Appliquez des fonctions : les foncteurs applicatifs
Appliquer plusieurs arguments
Dans le chapitre sur les fonctions, on a vu qu'on pouvait définir des fonctions plus, moins, … qui renvoient Nothing en cas d'erreur comme une division par zéro :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | plus Nothing _ = Nothing plus _ Nothing = Nothing plus (Just a) (Just b) = Just (a + b) moins Nothing _ = Nothing moins _ Nothing = Nothing moins (Just a) (Just b) = Just (a - b) fois Nothing _ = Nothing fois _ Nothing = Nothing fois (Just a) (Just b) = Just (a * b) divise Nothing _ = Nothing divise _ Nothing = Nothing -- la division par 0 donne un résultat indéfini divise _ (Just 0) = Nothing divise (Just a) (Just b) = Just (a / b) |
On peut essayer d'utiliser les foncteurs pour définir plus, moins et fois de façon plus simple. On commence simplement par traiter le premier argument avec fmap (+). Mais là on se retrouve devant un problème : fmap (+) a est de type Maybe (Integer -> Integer), alors qu'on a besoin d'une fonction d'une fonction de type <mincode type="haskell">Maybe Integer -> Maybe Integer.
On a donc besoin d'une fonction de type Maybe (a -> b) -> Maybe a -> Maybe b, qu'on peut voir comme une fonction qui applique une fonction contenue dans Maybe à une valeur contenue dans Maybe, ou alors une fonction qui transforme une fonction en une autre, suivant le point de vue. On peut la coder pour Maybe :
1 2 3 | app :: Maybe (a -> b) -> Maybe a -> Maybe b app (Just f) (Just x) = Just (f x) app _ _ = Nothing |
Mais cette fonction peut très facilement se généraliser à d'autres foncteurs, comme IO :
1 2 3 4 5 | appIO :: IO (a -> b) -> IO a -> IO b appIO fm xm = do f <- fm x <- xm return $ f x |
On peut ensuite utiliser ces fonctions (les lignes surlignées représentent l'entrée) :
1 2 3 4 5 6 7 8 9 10 | *Main> app (fmap (+) (Just 1)) (Just 2) Just 3 *Main> app (fmap (+) Nothing) (Just 2) Nothing *Main> app (fmap (+) (Just 1)) Nothing Nothing *Main> appIO (fmap (+) readLn) readLn 1 2 3 |
Les foncteurs applicatifs
Définition
Puisque cette fonction se retrouve avec plusieurs types, on la généralise en utilisant la classe de type Applicative, et on dit qu'un type est un foncteur applicatif (puisqu'on peut appliquer les fonctions). La classe Applicative est définie dans le module Control.Applicative comme ceci :
1 2 3 | class (Functor f) => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b |
L'opérateur <*> correspond à la fonction qu'on a appelée app, mais est plus pratique à utiliser. Le module Control.Applicative définit aussi l'opérateur <$> comme un synonyme de fmap : on peut donc écrire (+) <$> readLn <*> readLn au lieu de appIO (fmap (+) readLn) readLn.
La fonction pure sert à créer une valeur du foncteur applicatif à partir d'une valeur normale. L'instance d'Appicative doit être liée à l'instance de Functor par la relation suivante : pure f <*> v == fmap f v. Une autre règle est qu'on doit avoir : pure f <*> pure x == pure (f x) : pure transforme l'application de fonctions en <*>. Il y a trois autres règles à respecter, qui sont un peu plus compliquées à comprendre et moins utiles :
1 2 3 | pure id <*> v == v pure (.) <*> u <*> v <*> w == u <*> (v <*> w) u <*> pure y == pure ($ y) <*> u |
Importer Control.Applicative ajoute un certain nombre d'instances de Functor : vous risquez de vous retrouver avec des problèmes d'instances dupliquées. Il suffit d'enlever les définitions d'instances concernées pour régler le problème.
Exemples d'instances
Il y a aussi beaucoup d'instances d'Applicative. On a vu avant que Maybe et IO disposaient d'une fonction <*>, mais on peut aussi leur donner une fonction pure :
1 2 3 4 5 6 7 8 9 10 11 | instance Applicative Maybe where pure = Just Just f <*> Just x = Just $ f x _ <*> _ = Nothing instance Applicative IO where pure = return fm <*> xm = do f <- fm x <- xm return (f x) |
Par contre, même si on peut définir une instance de Functor pour (,) e, il n'y a pas d'instance d'Applicative : pour cela, il faudrait un moyen de créer une valeur de type e, et de combiner deux valeurs, qui permette de respecter les règles des foncteurs applicatifs. Si on choisit de spécialiser l'instance (par exemple aux entiers), on obtient une instance qui marche :
1 2 3 | instance Applicative ((,) Integer) where pure x = (0,x) (a,f) <*> (b,x) = (a+b, f x) |
Mais si vous essayez de définir cette instance, vous allez rencontrer une erreur du compilateur :
1 2 3 4 5 6 7 | /home/gnomnain/haskell/tuto/functor.hs:54:0: Illegal instance declaration for `Applicative ((,) Integer)' (All instance types must be of the form (T a1 ... an) where a1 ... an are type *variables*, and each type variable appears at most once in the instance head. Use -XFlexibleInstances if you want to disable this.) In the instance declaration for `Applicative ((,) Integer)' |
Cela vient d'une limitation des définitions possible de typeclasses dans la version Haskell 98 du langage. Mais GHC supporte beaucoup d'extensions à Haskell 98. Ici, il nous indique d'utiliser l'extension FlexibleInstances. Vous pouvez l'activer de deux façons : en lançant ghci avec l'option -XFlexibleInstances, ou en rajoutant tout en haut de votre fichier un commentaire avec le contenu suivant : {-# LANGUAGE FlexibleInstances #-}.
Il est possible de définir une instance similaire en faisant le produit de deux entiers, en concaténant des listes, en prenant le minimum ou le maximum, …
Pour continuer sur la gestion des erreurs, on peut aussi créer une instance d'Applicative pour Either : il suffit de prendre la première valeur d'erreur rencontrée sur les deux arguments de <*> :
1 2 3 4 5 | instance Applicative (Either e) where pure = Right Right f <*> Right x = Right $ f x Left e <*> _ = Left e Right _ <*> Left e = Left e |
Mais on pourrait aussi imaginer une instance qui prend l'erreur placée la plus à droite, et pas celle-là plus à gauche :
1 2 3 4 5 | instance Applicative (Either e) where pure = Right Right f <*> Right x = Right $ f x _ <*> Left e = Left e Left e <*> _ = Left e |
On peut même envisager de stocker une liste de toutes les erreurs rencontrées :
1 2 3 4 5 6 | instance Applicative (Either [e]) where pure = Right Right f <*> Right x = Right $ f x Left e <*> Right _ = Left e Right _ <*> Left f = Left f Left e <*> Left f = Left (e ++ f) |
Mais la première instance est la plus utilisée, puisqu'elle est compatible avec l'instance de la classe Monad pour Either, que vous découvrirez dans un autre chapitre. Celle qui récupère toutes les erreurs est cependant utile, si on souhaite par exemple présenter le plus d'erreurs possibles à l'utilisateur.
On a vu que les fonctions disposaient d'une instance de Functor. On peut aussi les rendre membres de la classe Applicative. pure doit renvoyer une fonction de type r -> a à partir d'une valeur de type a : il faut logiquement renvoyer une fonction constante. On voit aussi que le type de l'opérateur <*> doit être (r -> a -> b) -> (r -> a) -> (r -> b). On en déduit alors la définition (qui est déjà présente par défaut) :
1 2 3 | instance Applicative ((->) r) where pure = const f <*> x = (\r -> (f r) (x r) |
Cette instance d'Applicative permet de composer des actions qui accèdent à un contexte pour leur exécution. Par exemple, si on code un interpréteur, le contexte serait la liste des variables définies et leur valeur.
Il existe aussi une instance d'Applicative pour les listes. La fonction pure renvoie une liste à un élément, et <*> crée toutes les combinaisons possibles des valeurs dans les listes de ses deux éléments. Cette fonction se créer facilement grâce à concatMap, qui combine concat et map en concaténant les résultats de la fonction donnée sur les chaque élément :
1 2 3 4 5 | instance Applicative [] where pure x = [x] fs <*> xs = concatMap (\f -> map f xs) fs -- on pourrait écrire -- fs <*> xs = concat $ map (\f -> map f xs) fs |
Cette instance est pratique dans les cas où on veut tester toutes les possibilités. Par exemple, on peut s'en servir pour savoir si une formule logique est toujours vraie (ici, ~> note l'implication) :
1 2 3 4 5 6 7 8 9 | True ~> False = False _ ~> _ = True prop a b c = (a ~> b ~> c) ~> ((a ~> b) ~> (a ~> c)) prop2 a b c = (a ~> b) ~> ((a ~> c) ~> (b ~> c)) bool = [True,False] test prop = prop <$> bool <*> bool <*> bool |
Grâce à ce code, on peut tester une propriété sur les 8 combinaisons possibles de a, b et c :
1 2 3 4 | *Main> test prop [True,True,True,True,True,True,True,True] *Main> test prop2 [True,True,True,True,True,False,True,True] |
On voit alors que prop est toujours vraie, mais pas prop2.
Fonctions utiles
Le module Control.Applicative définit quelques fonctions utiles pour travailler avec les foncteurs. La fonction liftA2 :: (Functor f) => (a -> b -> c) -> f a -> f b -> f c permet de transformer une fonction qui travaille sur des valeurs "pures" en une fonction qui agit sur les valeurs du foncteur. Elle est facile à coder, et nous permet de factoriser les fonctions plus, moins et fois vue en introduction. La fonction liftA3 fait la même chose avec les fonctions à trois arguments :
1 2 3 4 5 6 7 | liftA2 f x y = f <$> x <*> y liftA3 f x y z = f <$> x <*> y <*> z plus, moins, fois :: (Num a, Functor f) => f a -> f a -> f a plus = liftA2 (+) moins = liftA2 (-) fois = liftA2 (*) |
Pour voir le fonctionnement des fonctions suivantes, un bon exemple est le type Log, qui a une instance d'Applicative (ce n'est qu'un cas particulier des instances pour les paires) :
1 2 3 4 5 6 7 | data Log e a = Log [e] a instance Applicative (Log e) where pure = Log [] Log e1 f <*> Log e2 x = Log (e1 ++ e2) (f x) log a = Log [a] () |
On voit qu'avec cette instance, l'ordre d'exécution a une importance : liftA2 (+) (Log "1" 1) (Left "2" 2) renvoie Log "12" 3, alors que si on inverse les arguments, on obtient Log "21" 3.
Les fonctions *> et <* s'occupent d'abord du premier argument puis du deuxième, mais renvoient la valeur qui est du côté de la flèche. Par exemple, log "123" *> (log "456" *> pure 2) renvoie Log "123456" 2, alors que (log "456" *> pure 2) <* log "123" renvoie Log "456123" 2. Elles sont donc importantes quand le foncteur a une notion d'ordre. La fonction <**> est comme <*>, sauf que la séquence est inversée : f <*> x applique d'abord l'effet de f, puis de x, alors que <**> applique d'abord l'effet de x, puis celui de f. Enfin, le module Data.Traversable définit une fonction sequenceA. Elle s'applique à tous les conteneurs ayant une instance de la classe Traversable. Pour les listes, le type de la fonction est : sequenceA :: (Applicative f) => [f a] -> f [a] : les actions contenues dans la liste sont séquencées, et on renvoie la liste de leur résultats.
Une autre construction
On peut aussi construire les foncteurs applicatifs d'une autre façon. La construction avec pure et <*> est assez naturelle, mais donne des règles difficiles à établir et à interpréter. On va garder la fonction pure, mais essayer de trouver un remplacement pour ><*>. La fonction liftA2 est une bonne candidate : en effet, on a f <*>x = liftA2 ($) f x. On a donc une première définition équivalente.
La deuxième remarque qu'on peut faire c'est que les fonctions à deux arguments peuvent être converties en fonction qui prennent une coupe et vice-versa grâce aux fonctions curry :: ((a,b) -> c) -> a -> b -> c et uncurry :: (a -> b -> c) -> (a,b) -> c. Le problème qui se pose pour coder liftA2 à partir de fmap, c'est qu'il faut transormer des f a et f b en f (a,b). Si on a une fonction pour cela, on peut retrouver les opérations sur les foncteurs applicatifs.
La fonction pure n'est même pas nécessaire, elle peut être remplacée par une valeur unit = pure (). En effet, on a pure a = const a <$> unit. Ces définitions sont donc liées par les relations suivantes :
1 2 3 4 5 6 | unit = pure () pure a = const a <$> unit (<&>) = liftA2 (,) liftA2 f a b = f <$> (a <&> b) f <*>x = liftA2 ($) f x |
Les propriétés des foncteurs applicatifs s'écrivent de façon plus sympathique avec cette notation, et sont plus naturelles :
1 2 3 4 5 6 7 8 9 10 | -- On pose : assoc (a,(b,c)) = ((a,b),c) (f *** g) (x,y) = (f x, f y) -- Les règles : fmap (f *** g) (x <&> y) == fmap f x <&> fmap f y fmap fst (x <&> unit) == x fmap snd (unit <&> x) == x fmap assoc (u <&> (v <&> w)) = (u <&> v) <&> w |
Cependant, en général, cette définition ne facilite pas beaucoup la définition d'une instance d'Applicative, mais risque plutôt de la compliquer puisqu'il faut définir des fonctions annexes.
Applications intéressantes
Généraliser la fonction zipWith à plus d'arguments
La fonction zipWith permet d'appliquer une fonction aux éléments de deux listes pris deux à deux. On a zipWith f [x1,x2,...] [y1,y2,...] = [f x1 y1, f x2 y2, ...]. Il existe de même une fonction zipWith3 qui prend une fonction à trois arguments et trois listes. Mais il faut recréer une fonction pour chaque nombre d'arguments, ce n'est donc pas très pratique.
Cependant, on peut coder les fonctions zipWithN (où N vaut 3, 4, …) simplement à partir de la fonction zipWith : on applique d'abord partiellement la fonction f à tous les éléments de la première liste, puis on applique les éléments de la liste obtenue à la deuxième liste, … Par exemple :
1 | zipWith3' f xs ys zs = zipWith (zipWith ($) (map f xs) ys) zs |
En fait, on remarque que zipWith ($) joue le rôle de l'opérateur <*>. Il reste à trouver une fonction pure qui correspond. Il faut répéter l'élément donné un certain nombre de fois. Mais si on ne le met qu'un nombre fini de fois, on peut trouver une liste plus longue, et dans ce cas on n'a pas la propriété pure id <*> u == u, puisque la liste sera tronquée. Il faut donc générer une liste infinie : c'est ce que fait la fonction repeat :: a -> [a]. Mais il y a un dernier problème : on a déjà une instance d'Applicative pour les listes. On va donc utiliser un newtype pour définir un synonyme pour les listes. Dans la bibliothèque standard, il est nommé ZipList.
1 2 3 4 5 | data ZipList a = ZipList { unZipList :: [a] } instance Applicative ZipList where pure = ZipList . repeat (ZipList f) <*> (ZipList x) = ZipList $ zipWith ($) f x |
Traiter des formulaires
Si vous avez déjà programmé des sites web, par exemple en PHP, vous savez surement que traiter des formulaires peut devenir très lourd : on se retrouve parfois avec beaucoup de conditions imbriquées, du code répétitif, … C'est un cas classique de traitement des erreurs, et on a vu que les foncteurs applicatifs s'y prêtaient plutôt bien. On veut en général présenter toutes les erreurs de traitement à l'utilisateur. De plus, on a un contexte d'exécution à transporter : ce sont les valeurs reçues du formulaire. Or, comme pour les foncteurs, on peut composer les foncteurs applicatifs, donc on peut à la fois transporter un contexte et récupérer les erreurs.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | type Dict = [(String,String)] data Acc a b = Error [a] | Result b deriving Show instance Functor (Acc e) where fmap f x = pure f <*> x instance Applicative (Acc e) where pure = Result Result f <*> Result x = Result (f x) Error e <*> Result _ = Error e Result _ <*> Error f = Error f Error e <*> Error f = Error (e ++ f) newtype Form a = Form { runForm :: Dict -> Acc String a } instance Functor Form where fmap f x = pure f <*> x instance Applicative Form where pure = Form . pure . pure Form fe <*> Form xe = Form (liftA2 (<*>) fe xe) |
On a appelé Acc le foncteur applicatif qui accumule les erreurs. La définition de <*> pour Form est en fait la définition générale pour une composée de foncteurs applicatifs : si on appelle F et G les deux foncteurs, on a une fonction G (a -> b) -> G a -> G b et on veut une fonction F (G (a -> b)) -> F (G a) -> F (G b). Il est donc naturel d'utiliser la fonctionliftA2 associée à F.
On doit ensuite coder quelques fonctions pour récupérer et vérifier les données. Le but est de créer une structure qui contient toutes les données nécessaires pour le résultat. La fonction clé est check, qui prend un prédicat (une fonction renvoyant un booléen), et vérifie s'il est respecté par les données. On a aussi quelques fonctions pour récupérer les valeurs : getInt, getString, …
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | getString :: String -> Form String getString s = Form $ (\env -> case lookup s env of Just a -> Result a Nothing -> Result "") getInt :: String -> Form Int getInt s = Form $ (\env -> case lookup s env of Just a | all (`elem` ['0'..'9']) a -> Result (read a) _ -> Error ["Le champ " ++ s ++ " n'est pas un entier"]) check :: String -> (a -> Bool) -> Form a -> Form a check err pred val = Form $ (\env -> case runForm val env of Error e -> Error e Result v -> if pred v then Result v else Error [err]) |
On peut ensuite traiter un formulaire simple, pour récupérer un enregistrement de type Glace défini plus haut :
1 2 3 4 5 6 7 | parseGlace :: Form Glace parseGlace = liftA3 Glace (check "Le champ \"parfum\" doit faire entre 1 et 40 caractères" (\p -> let l = length p in 1 <= l && l <= 40) $ getString "parfum") (getString "fabriquant") (check "La note doit être comprise entre 0 et 20" (\n -> 0 <= n && n <= 20) $ getInt "note") |
1 | </mincode> |
Les foncteurs et les foncteurs applicatifs sont donc un moyen de créer des fonctions pures qui ont des effets : elles peuvent garder une trace de ce qui a été exécuté, renvoyer des erreurs ou accéder à un contexte d'exécution. Ils s'appliquent aussi à beaucoup de situations, mais cela fait qu'ils ne sont pas aussi puissants qu'on le voudrait : par exemple, il n'est pas possible en général de faire dépendre l'effet d'une valeur qui est elle-même le résultat d'une action : si on a une fonction de type a -> f b, on ne peut pas en tirer une fonction f a -> f b, et donc faire dépendre l'effet du résultat des effets précédents.