A Gentle Introduction to Haskell, version 98

Le préambule contient un certain nombre de classes définissant les monades, qui sont utilisées en Haskell. Ces classes sont basées sur la construction des monades à partir de la théorie des catégories. Bien que la terminologie de la théorie des catégories fournit des noms pour les classes monadiques et pour les opérations, il n'est pas nécessaire de trop rentrer dans une telle abstraction mathématique pour avoir une compréhension intuitive de l'utilisation des monades.

Une monade est construite par-dessus un type polymorphe, comme IO. La monade en elle-même est définie comme une suite de déclarations associant un type avec une ou plusieurs classes monadiques, Functor, Monad et MonadPlus. Aucune de ses classes monadiques n'est dérivable.
En plus de IO, deux autres types présents dans le préambule sont des monades : les listes ([]) et Maybe.

Mathématiquement, les monades sont régies par un ensemble de règles qui devraient faire office d'opérations. Cette idée de règles n'est pas une spécificité des monades, Haskell contient d'autres opérations qui sont en fait régies par des règles. Par exemple, x /= y et not (x == y) devraient être les mêmes quel que soit le type des variables comparées. Cependant, on n'en a aucune garantie : les opérateurs == et /= sont des méthodes distinctes de la classe Eq, et on ne peut garantir un lien entre elles de cette manière.
Dans la même logique, les règles régissant les monades présentées ici ne sont pas imposées par Haskell, mais sont pourtant respectées par toutes les instances des classes monadiques. Les règles monadiques donnent donc un indice sur la structure sous-jacente des monades ; en les examinant, on peut donc acquérir une intuition suffisante pour utiliser les monades.

La classe Functor, dont on a déjà parlé dans la partie V, définit une seule opération : fmap. Cette fonction applique une opération aux éléments d'un conteneur, et renvoie un conteneur avec les valeurs calculées. On peut d'ailleurs voir les types polymorphes comme des conteneurs de variables d'un autre type.
Ces lois régissent la méthode fmap de la classe Functor.

fmap   id     = id
fmap (f . g)  = fmap f . fmap g

Ces règles assurent que la structure du conteneur reste inchangée après le passage de fmap, et que son contenu n'est pas réordonné.
La classe Monad définit deux opérateurs de base: >>= (bind) et return.

infixl 1  >>, >>=
class  Monad m  where
    (>>=)            :: m a -> (a -> m b) -> m b
    (>>)             :: m a -> m b -> m b
    return           :: a -> m a
    fail             :: String -> m a
 
    m >> k           =  m >>= \_ -> k

Les opérations bind, >>> et >>=, combinent deux valeurs monadiques, tandis que l'opération return injecte une variable dans la monade (le conteneur).
La signature de >>= nous permet de mieux la comprendre : ma >>= \v -> mb combine la valeur monadique ma contenant des variables de type a, et une fonction qui prend en argument une variable v de type a pour renvoyer la valeur monadique mb. Le résultat doit alors combiner ma et mb dans une monade contenant des variables de type b.
L'opérateur >> est utilisé lorsqu'on n'a pas besoin de la variable produite par le premier opérateur.

Une définition plus précise du binding dépend, bien entendu, des monades. Par exemple, dans la monade IO, x >>= y effectue deux actions séquentiellement, en passant le résultat de la première à la seconde. Pour les autres monades implémentées, les listes et le type Maybe, ces opérations monadiques peuvent être vues comme le passage de zéro variable, ou plus, d'une exécution à la suivante. On va bientôt montrer quelques exemples.
La syntaxe do permet une prise en main facile des chaînes d'opérations monadiques. Sa signification peut se résumer avec les deux règles suivantes :

do e1 ; e2      =        e1 >> e2
do p <- e1; e2  =        e1 >>= \p -> e2

Quand le motif présent dans la seconde règle est « réfutable », on peut appeler l'opération fail. Cela permet d'indiquer une erreur (comme dans la monade IO), ou retourner la valeur zéro (comme dans la monade liste). Par conséquent, une traduction plus complexe de cette opération pourrait être :

do p <- e1; e2  =   e1 >>= (\v -> case v of p -> e2; _ -> fail "s")

où « s » est une chaîne de caractères signalant l'emplacement de la déclaration do pour pouvoir l'utiliser dans un message d'erreur. Par exemple, dans la monade IO, une action telle que 'a' <- getChar appellera fail si le caractère saisi n'est pas 'a'. Cela va, à son tour, terminer brutalement le programme, car le fail d'IO appelle la fonction error.
Les règles qui régissent >>>= et return sont

return a >>= k    =    k a 
m >>= return    =    m 
xs >>= return . f    =    fmap f xs
m >>= (\x -> k x >>= h)    =    (m >>= k) >>= h

La classe MonadPlus est utilisée pour les monades qui possèdent un élément zero et un opérateur plus.

class  (Monad m) => MonadPlus m  where
    mzero             :: m a
    mplus             :: m a -> m a -> m a

L'élément zero obéit aux règles suivantes :

m >>= \x -> mzero    =    mzero
mzero >>= m        =    mzero

En ce qui concerne les listes, la valeur nulle est [], la liste vide. La monade IO ne contient pas d'élément nul, et n'est pas un membre de cette classe…
Les règles régissant l'opérateur mplus sont :

m `mplus` mzero    =    m
mzero `mplus` m    =    m

L'opérateur mplus de la monade liste est la concaténation standard des listes.

Avec les opérations monadiques et les règles qui les régissent, que pouvons-nous faire ? Nous avons déjà étudié la monade IO en détail, nous allons donc nous intéresser aux deux autres monades intégrées à Haskell.
Pour les listes, le binding associe un ensemble de calculs pour chaque valeur dans la liste. Quand on l'utilise avec les listes, la signature de >>= devient :

(>>=)                   :: [a] -> (a -> [b]) -> [b]

Etant données une liste d'éléments de type a, et une fonction associant à une variable de type a une liste d'éléments de type b, binding applique cette fonction à chaque élément de type a contenu dans la variable d'entrée, et renvoie la liste contenant les valeurs de type b générées. La fonction return créera une liste à un seul élément. Ces opérations devraient nous sembler familières, car les opérations sur les listes peuvent facilement être exprimées sous forme d'opérations monadiques définies sur les listes. Par exemple, voici trois expressions distinctes représentant la même chose :

[(x,y) | x <- [1,2,3] , y <- [1,2,3], x /= y]
 
do x <- [1,2,3]
   y <- [1,2,3]
   True <- return (x /= y)
   return (x,y)
 
[1,2,3] >>= (\ x -> [1,2,3] >>= (\y -> return (x/=y) >>=
   (\r -> case r of True -> return (x,y)
                    _    -> fail "")))

Cette définition dépend de la définition du fail dans cette monade, comme étant la liste vide. Pour résumer, chaque <- génère un ensemble de valeurs qui est passé en argument à l'exécution de la monade. Par conséquent, x <- [1,2,3] appelle trois fois l'exécution de la monade, une fois par élément de la liste. L'expression renvoyée, (x,y), sera évaluée pour toutes les combinaisons possibles de binding. Dans cette optique, la liste monade peut être vue comme des fonctions à nombre d'arguments variable. Par exemple, la fonction suivante

mvLift2                :: (a -> b -> c) -> [a] -> [b] -> [c]
mvLift2 f x y          =  do x' <- x
                              y' <- y
                              return (f x' y')

transforme une fonction standard à deux arguments en une fonction à nombres d'arguments variable (grâce à une liste d'arguments), renvoyant la valeur pour toutes les combinaisons possibles de deux arguments d'entrée. Par exemple,

mvLift2 (+) [1,3] [10,20,30]     =>    [11,21,31,13,23,33]
mvLift2 (\a b->[a,b]) "ab" "cd"     =>    ["ac","ad","bc","bd"]
mvLift2 (*) [1,2,4] []     =>    []

Cette fonction est une version spécialisée de la fonction LiftM2 de la classe Monad. On peut la voir comme une fonction injectant une fonction quelconque dans la monade des listes, donc avec un nombre d'arguments en entrée variable.
La monade Maybe est similaire la monade listes : la valeur Nothing équivaut à [] et Just x équivaut à [x].

Attention il ne suffit pas de décrire les opérateurs monadiques et les règles qui les régissent, pour décrire les domaines où il est utile d'utiliser les monades. On peut voir qu'elles apportent une certaine modularité. En définissant une opération monadique, on peut construire tout ce qui est nécessaire pour intégrer de nouvelles fonctionnalités aux monades, et ce de manière transparente. L'article de Wadler est d'ailleurs un excellent exemple de l'utilisation des monades pour obtenir un programme modulaire.
On va commencer par utiliser une monade décrite de cet article, la state monad, pour construire une monade plus complexe autour d'un type state S, ressemblant à cela :

data SM a = SM (S -> (a,S))  – The monadic type
 
instance Monad SM where
  – defines state propagation
  SM c1 >>= fc2         =  SM (\s0 -> let (r,s1) = c1 s0 
                                          SM c2 = fc2 r in
                                         c2 s1)
  return k              =  SM (\s -> (k,s))
 
 – extracts the state from the monad
readSM                  :: SM S
readSM                  =  SM (\s -> (s,s))
 
 – updates the state of the monad
updateSM                :: (S -> S) -> SM ()  – alters the state
updateSM f              =  SM (\s -> ((), f s)) 
 
– run a computation in the SM monad
runSM                   :: S -> SM a -> (a,S)
runSM s0 (SM c)         =  c s0

Cet exemple définit un nouveau type, SM, pour être une structure qui contient implicitement un type S. Une structure du type SM t définit donc une variable de type t, qui pourra accéder en lecture et en écriture à l'état du type S. La définition de SM consiste simplement en celle de fonctions qui prennent en argument un état, et qui produisent deux résultats : la valeur renvoyée (de n'importe quel type), et un état mis à jour. Ici, on ne peut pas utiliser un type « synonyme », car on a besoin du nom du type comme SM, qui pourra être utilisé dans les déclarations instance. La déclaration newtype est souvent utilisée à la place de data.

La déclaration instance définit la « tuyauterie » de la monade : comment ordonnancer deux exécutions et la définition d'une exécution vide. L'ordonnancement (avec l'opérateur >>=) définit une exécution (notée par le constructeur SM) passant un état initial, s0, dans c1, et donnant le résultat de ce calcul, r, à c2, et renvoyant finalement le résultat de c2.

La définition de return est plus facile : il ne change pas d'état du tout… il sert juste à insérer une variable dans une monade.

Tandis que >>= et return sont de simples opérations monadiques de séquentialisation, on a aussi besoin de primitives monadiques. Une primitive monadique est juste une opération qui est utilisée dans l'abstraction d'une monade et qui sert à « passer les vitesses » durant le travail de la monade. Par exemple, dans la monade IO, des opérateurs comme putChar sont des primitives puisqu’elles concernent le fonctionnement interne de la monade IO. De la même manière, la monade que nous sommes en train de présenter utilise deux primitives : readSM et updateSM. Remarquez qu'elles dépendent de la structure interne de la monade (un changement de la définition de SM obligerait à modifier ces primitives).

Les définitions de readSM et updateSM sont simples : readSM exporte l'état de la monade pour pouvoir l'observer, alors que updateSM autorise l'utilisateur à modifier l'état de la monade. (On aurait aussi pu définir writeSM comme une primitive, mais updateSM semble la manière la plus naturelle d'effectuer une telle opération).

Finalement, on a besoin d'une fonction qui lance l'exécution de la monade, runSM. Elle prend en argument l'état initial et une séquence d'instructions, et donne à la fois la valeur renvoyée et l'état final.

D'un point de vue plus général, ce qu'on essaie de faire est de définir une exécution globale d'une série d'étapes (fonctions du type SM a), ordonnancées à l'aide de >>= et return. Ces étapes peuvent interagir avec l'état (via readSM ou updateSM), ou l'ignorer. Cependant, l'utilisation (ou la non-utilisation) de cet état est cachée : la forme des appels de fonctions ne diffère pas.

Plutôt que de présenter plusieurs petits exemples utilisant juste cette state monade, on va s'intéresser à un exemple plus complexe qui utilise, entre autres, la state monade. On définit un petit langage pour effectuer des calculs sur des ressources.
Pour cela, on construit un langage dans le but d'implémenter un sous-ensemble des types et des fonctions de Haskell. De tels langages utilisent les outils de base de Haskell, types et fonctions, afin de construire une bibliothèque d'opérations et de types spécialement adaptée à nos besoins.

Dans cet exemple, on considère une exécution qui nécessite des « ressources ». Si cette ressource est indisponible, l'exécution est suspendue. On utilise le type R pour signaler une commande utilisant les ressources contrôlées par notre monade. La définition de R est :

data R a = R (Resource -> (Resource, Either a (R a)))

Chaque exécution est une fonction qui prend en arguments les ressources disponibles, qui renvoie les ressources restantes, couplée à un éventuel résultat, du type a, ou à une exécution suspendue, du type R a, qui contient tout le travail fait jusqu'à l'épuisement des ressources nécessaires.

instance Monad R where
  R c1 >>= fc2          = R (\r -> case c1 r of
                                (r', Left v)    -> let R c2 = fc2 v in
                                                     c2 r'
                                (r', Right pc1) -> (r', Right (pc1 >>= fc2)))
  return v              = R (\r -> (r, (Left v)))

Le type Resource est utilisé de la même manière que l'état à l'intérieur de la state monade. Cette définition se voit comme : pour effectuer deux exécutions nécessitant des ressources, c1 et fc2 (une fonction produisant c2), on donne les ressources initiales à c1. Le résultat sera :

• une valeur, v, et les ressources restantes, qui seront utilisées pour le lancement de la commande suivante (l'appel fc2 v)
• une suspension d'exécution, pc1, et les ressources restantes au moment de la suspension

La suspension doit prendre en compte la seconde commande à exécuter : pc1 suspend la première exécution, c1, on doit donc propager cette information à c2 afin de produire la suspension de l'exécution dans son ensemble. La définition de return laisse les ressources inchangées, tout en insérant v dans la monade.

La déclaration d'instance définit la structure de base de la monade, mais ne dit pas comment les ressources seront utilisées. La monade peut être utilisée pour contrôler de nombreux types de ressources, ou pour implémenter de nombreuses politiques d'utilisation des ressources. On va donner un exemple très simple de définition de ressources, en choisissant que Resource soit un Integer représentant les étapes disponibles de l'exécution.

type Resource           =  Integer

Cette fonction prend une étape à moins qu'aucune ne soit disponible.

step                    :: a -> R a
step v                  =  c where
                              c = R (\r -> if r /= 0 then (r-1, Left v)
                                                     else (r, Right c))

Les constructeurs Left et Right font partie du type Either. Cette fonction poursuit l'exécution dans R en renvoyant v tant qu'il reste au moins une étape de l'exécution dont les ressources nécessaires sont encore disponibles. Si plus aucune étape n'est disponible, la fonction step suspend l'exécution courante (la suspension est capturée par c), et range cette exécution suspendue dans la monade.

À partir de là, on dispose des outils définissant une suite d'exécutions utilisant des ressources (les monades), et on peut exprimer une sorte d'utilisation des ressources avec step. Enfin, on a besoin d'indiquer comment les exécutions dans cette monade seront exprimées.
On considérera une fonction d'incrémentation dans notre monade.

inc                     :: R Integer -> R Integer
inc i                   =  do iValue <- i
                              step (iValue+1)

Cela définit l'incrémentation comme une simple étape d'exécution. Le <- est nécessaire pour sortir de la monade la valeur en argument. Le type de iValue est Integer au lieu de R Integer.

Toutefois, cette définition n'est pas particulièrement satisfaisante, en comparaison aux définitions standards des fonctions d'incrémentation. Ne pourrait-on pas, à la place, surcharger des opérateurs existants, comme le +, afin qu'ils puissent travailler dans le monde des monades ? On va commencer avec un ensemble de fonctions de lifting. Celles-ci importent des fonctionnalités existantes dans les monades. Considérons une définition de lift1 (qui est légèrement différente de liftM1 de la bibliothèque Monad) :

lift1                   :: (a -> b) -> (R a -> R b)
lift1 f                 =  \ra1 -> do a1 <- ra1
                                      step (f a1)

Cela prend une fonction à un argument, f, et crée une fonction dans R qui exécute la fonction liftée en une étape. En utilisant lift1, inc est devenue :

inc                     :: R Integer -> R Integer
inc i                   =  lift1 (i+1)

Cela est mieux, mais pas encore idéal. Dans un premier temps, on va ajouter lift2 :

lift2                   :: (a -> b -> c) -> (R a -> R b -> R c)
lift2 f                 =  \ra1 ra2 -> do a1 <- ra1
                                          a2 <- ra2
                                          step (f a1 a2)

Remarquez que la fonction définit explicitement l'ordre d'évaluation de la fonction liftée : l'exécution concernant a1 se produira avant celle pour a2.
En utilisant lift2, on peut créer une nouvelle version de == dans la monade R :

(==*) : : Ord un => R a - > R a - > R Bool
(==*) = lift2 (==)

On a dû employer un nom légèrement différent pour cette nouvelle fonction, puisque le == est déjà pris. Mais dans certains cas, on peut utiliser le même nom pour la fonction liftée et pour celle d'origine. Cette déclaration d'instance permet à tous les opérateurs de Num d'être utilisés dans R:

instance Num a => Num (R a) where
  (+)                   =  lift2 (+)
  (-)                   =  lift2 (-)
  negate                =  lift1 negate
  (*)                   =  lift2 (*)
  abs                   =  lift1 abs
  fromInteger           =  return . fromInteger

La fonction fromInteger est appliquée implicitement à toutes les constantes entières dans Haskell (voir la section X-3). La définition permet aux constantes entières d'avoir le type R Integer. On peut maintenant, enfin, écrire une fonction d'incrémentation dans un style complètement naturel :

inc                     :: R Integer -> R Integer
inc x                   =  x + 1

Remarquez qu'on ne peut pas lifter la classe Eq de la même manière que la classe Num. En effet, la signature de ==* n'est pas compatible avec les surcharges autorisées de ==, car le résultat de ==* est de type R Bool et non pas Bool.

Pour exprimer des exécutions intéressantes dans R, on va avoir besoin de conditions. Comme on ne pourra pas utiliser le nom if, qui requiert que le test soit de type Bool et non R Bool, on prendra le nom ifR.

ifR                     :: R Bool -> R a -> R a -> R a
ifR tst thn els         =  do t <- tst
                              if t then thn else els

Maintenant, on est prêt pour un long programme dans la monade R.

fact                    :: R Integer -> R Integer
fact x                  =  ifR (x ==* 0) 1 (x * fact (x-1))

Désormais, ce sera bien moins facile qu'avec la simple fonction factorielle, mais ça devrait tout de même rester lisible. L'idée de proposer des nouvelles définitions pour les opérations existantes comme + ou if est une partie essentielle de la création du langage embarqué dans Haskell. Les monades sont particulièrement utiles pour encapsuler les sémantiques de ces langages de manière propre et modulaire.

On est maintenant prêt pour faire tourner quelques programmes. Cette fonction lance un programme dans M en lui donnant le nombre maximal d'étapes d'exécution.

run                     :: Resource -> R a -> Maybe a
run s (R p)             =  case (p s) of 
                             (_, Left v) -> Just v
                             _           -> Nothing

On peut utiliser le type Maybe pour donner à l'exécution la possibilité de ne pas finir dans le nombre d'étapes accordé. Ainsi, on peut obtenir :

run 10 (fact 2)     =>     Just 2
run 10 (fact 20)     =>    Nothing

Finalement, on peut ajouter des fonctionnalités intéressantes à cette monade. Regardons la fonction suivante :

(|||)                   :: R a -> R a -> R a

Cela lance en parallèle deux exécutions, et renvoie la valeur de la première. Une définition possible d'une telle fonction serait :

c1 ||| c2                =  oneStep c1 (\c1' -> c2 ||| c1')
   where
        oneStep          :: R a -> (R a -> R a) -> R a
        oneStep (R c1) f =
             R (\r -> case c1 1 of
                         (r', Left v) -> (r+r'-1, Left v)
                         (r', Right c1') ->  – r' must be 0
                          let R next = f c1' in
                            next (r+r'-1))

Cette fonction prend une étape dans c1, et renvoie sa valeur complète c1, ou si c1 a renvoyé une exécution suspendue (c1'), évalue c2 ||| c1'. La fonction oneStep prend une étape élémentaire en argument, et renvoie la valeur évaluée, ou passe le reste de l'exécution à f. La définition de oneStep est simple: elle donne à c1 un 1 comme valeur d'entrée. Si la valeur finale est atteinte, elle est renvoyée, ce qui ajuste le compteur d'étapes renvoyé (il est possible que l'exécution renvoie, après n'avoir pris aucune étape, donc le compteur de ressources renvoyé n'est pas forcément 0). Si l'exécution est suspendue, un compteur de ressource « patché » sera passé à la continuation finale.

On peut maintenant évaluer des expressions comme run 100 (fact (-1) ||| (fact 3)) sans boucler grâce à l'exécution de deux processus en parallèle. (Notre définition de fact boucle pour -1). De nombreuses variantes sont possibles autour de cette structure de base. Par exemple, on peut étendre l'état, de façon à inclure la trace de toutes les étapes de l'exécution. On peut aussi inclure cette monade dans la monade standard IO, ce qui autoriserait les exécutions dans M à interagir avec le reste du monde.
Même si cet exemple est peut-être plus avancé que les autres de ce tutoriel, il sert à illustrer la puissance des monades, en tant qu'outils pour définir la sémantique de base d'un système. On présente aussi cet exemple comme un modèle d'un petit langage spécifique à un domaine (DSL), domaine que Haskell peut particulièrement bien définir. De nombreux autres DSLs ont été développés dans Haskell; regardez haskell.org pour plus de détails. Les plus intéressants sont Fran, un langage d'animations réactives, et Haskore, un langage de synthèse musicale.