Les bases des monades

De nombreux nouveaux venus dans Haskell sont déconcertés par le concept de monades. Les monades sont fréquemment rencontrées dans Haskell : le système d'entrée/sortie est construit à l'aide d'une monade, une syntaxe spéciale pour les monades a été fournie (expressions do) et les bibliothèques standard contiennent un module entier dédié aux monades. Dans cette page, nous explorons la programmation monadique plus en détail.

Cette page est peut-être moins «douce» que les autres. Nous y abordons non seulement les fonctionnalités du langage de programmation impliquant les monades, mais nous essayons également de révéler la situation dans son ensemble : pourquoi les monades sont un outil si important et comment elles sont utilisées.

Classes monadiques

Le Prélude contient un certain nombre de classes définissant les monades telles qu'elles sont utilisées dans Haskell. Ces classes sont basées sur la construction monad de la théorie des catégories ; Bien que la terminologie de la théorie des catégories fournisse les noms des classes et des opérations monadiques, il n'est pas nécessaire de plonger dans les mathématiques abstraites pour comprendre intuitivement comment utiliser les classes monadiques.

Une monade est construite sur un type polymorphe tel que IO. La monade elle-même est définie par des déclarations d'instance associant le type à certaines ou à toutes les classes monadiques, Functor, Monad et MonadPlus. Aucune des classes monadiques n'est dérivable. En plus de IO, deux autres types du Prélude sont membres des classes monadiques : les listes ([]) et Maybe.

Mathématiquement, les monades sont régies par un ensemble de lois devant s'appliquer aux opérations monadiques. Cette idée de lois n'est pas propre aux monades : Haskell inclut d'autres opérations étant régies, au moins de manière informelle, par des lois. Par exemple, x /= y et not (x == y) devraient être les mêmes pour tout type de valeurs comparées. Cependant, il n'y a aucune garantie à ce sujet : == et /= sont des méthodes distinctes dans la classe Eq et il n'y a aucun moyen de garantir que == et =/ sont liés de cette manière. Dans le même sens, les lois monadiques présentées ici ne sont pas appliquées par Haskell, mais doivent être respectées par toutes les instances d'une classe monadique. Les lois monadiques donnent un aperçu de la structure sous-jacente des monades : en examinant ces lois, nous espérons donner une idée de la façon dont les monades sont utilisées.

La classe Functor, définit une seule opération : fmap. La fonction map applique une opération aux objets à l'intérieur d'un conteneur (les types polymorphes peuvent être considérés comme des conteneurs pour des valeurs d'un autre type), renvoyant un conteneur de la même forme. Ces lois s'appliquent à fmap dans la classe Functor :

Ces lois garantissent que la forme du conteneur reste inchangée par fmap et que le contenu du conteneur n'est pas réorganisé par l'opération de cartographie.

La classe Monad définit deux opérateurs de base : >>= (bind) et return :

Les opérations de liaison, >> et >>=, combinent deux valeurs monadiques tandis que l'opération de retour injecte une valeur dans la monade (conteneur). La signature de >>= nous aide à comprendre cette opération : ma >>= \v -> mb combine une valeur monadique ma contenant des valeurs de type a et une fonction qui opère sur une valeur v de type a, renvoyant la valeur monadique mb. Le résultat est de combiner ma et mb en une valeur monadique contenant b. La fonction >> est utilisée lorsque la fonction n'a pas besoin de la valeur produite par le premier opérateur monadique.

La signification précise de la liaison dépend, bien sûr, de la monade. Par exemple, dans la monade IO, x >>= y exécute deux actions séquentiellement, en passant le résultat de la première à la seconde. Pour les autres monades intégrées, les listes et le type Maybe, ces opérations monadiques peuvent être comprises en termes de passage de zéro ou plusieurs valeurs d'un calcul à l'autre. Nous verrons des exemples de cela sous peu.

La syntaxe do fournit un raccourci simple pour les chaînes d'opérations monadiques. La traduction essentielle de do est capturée dans les deux règles suivantes :

Lorsque le modèle de cette deuxième forme de do est réfutable, l'échec de correspondance de modèle appelle l'opération fail. Cela peut générer une erreur (comme dans la monade IO) ou renvoyer un «zéro» (comme dans la monade list). Ainsi, la traduction la plus complexe est :

où «s» est une chaîne de caractères identifiant l'emplacement de l'instruction do pour une utilisation possible dans un message d'erreur. Par exemple, dans la monade d'entreée/sortie, une action telle que «a» <- getChar appellera fail si le caractère saisi n'est pas «a». Cela, à son tour, termine le programme puisque dans la monade d'entrée/sortie, fail appelle error.

Les lois régissant >>= et return sont :

La classe MonadPlus est utilisée pour les monades qui ont un élément zéro et une opération plus :

L'élément zéro obéit aux lois suivantes :

Pour les listes, la valeur zéro est [], la liste vide. La monade I/O n'a pas d'élément zéro et n'est pas membre de cette classe.

Les lois régissant l'opérateur mplus sont les suivantes :

L'opérateur mplus est une concaténation de liste ordinaire dans la monade de liste.

Monades intégrées

Étant donné les opérations monadiques et les lois les régissant, que pouvons-nous construire ? Nous avons déjà examiné en détail la monade d'entrée/sortie, nous commençons donc par les deux autres monades intégrées.

Pour les listes, la liaison monadique consiste à joindre un ensemble de calculs pour chaque valeur de la liste. Lorsqu'elle est utilisée avec des listes, la signature de >>= devient :

Autrement dit, étant donné une liste de a et une fonction cartographiant un a sur une liste de b, la liaison applique cette fonction à chacun des a dans l'entrée et renvoie tous les b générés concaténés dans une liste. La fonction de retour crée une liste singleton. Ces opérations devraient déjà vous être familières : les compréhensions de liste peuvent facilement être exprimées à l'aide des opérations monadiques définies pour les listes. Ces trois expressions suivantes sont toutes des syntaxes différentes pour la même chose :

Cette définition dépend de la définition de fail dans cette monade en tant que liste vide. Essentiellement, chaque <- génère un ensemble de valeurs étant transmis au reste du calcul monadique. Ainsi x <- [1,2,3] invoque le reste du calcul monadique trois fois, une fois pour chaque élément de la liste. L'expression renvoyée, (x,y), sera évaluée pour toutes les combinaisons possibles de liaisons l'entourant. Dans ce sens, la monade de liste peut être considérée comme décrivant des fonctions de paramètres à valeurs multiples. Par exemple, cette fonction :

transforme une fonction ordinaire de deux paramètres (f) en une fonction sur plusieurs valeurs (listes de paramètres), renvoyant une valeur pour chaque combinaison possible des deux arguments d'entrée. Par exemple :

Cette fonction est une version spécialisée de la fonction LiftM2 dans la bibliothèque monade. Vous pouvez la considérer comme le transport d'une fonction de l'extérieur de la monade de liste, f, dans la monade de liste dans laquelle les calculs prennent plusieurs valeurs.

La monade définie pour Maybe est similaire à la monade de liste : la valeur Nothing sert de [] et Just x de [x].

Utilisation des monades

L'explication des opérateurs monadiques et de leurs lois associées ne montre pas vraiment à quoi servent les monades. Ce qu'elles offrent vraiment, c'est la modularité. C'est-à-dire qu'en définissant une opération de manière monadique, nous pouvons cacher les mécanismes sous-jacents d'une manière permettant d'incorporer de nouvelles fonctionnalités dans la monade de manière transparente. L'article de Wadler est un excellent exemple de la façon dont les monades peuvent être utilisées pour construire des programmes modulaires. Nous commencerons par une monade tirée directement de cet article, la monade d'état, puis nous construirons une monade plus complexe avec une définition similaire.

En bref, une monade d'état construite autour d'un type d'état S ressemble à ceci :

Cet exemple définit un nouveau type, SM, comme étant un calcul qui porte implicitement un type S. Autrement dit, un calcul de type SM t définit une valeur de type t tout en interagissant également avec (en lisant et en écrivant) l'état de type S. La définition de SM est simple : elle consiste en des fonctions prenant un état et produisent deux résultats : une valeur renvoyée (de n'importe quel type) et un état mis à jour. Nous ne pouvons pas utiliser de synonyme de type ici : nous avons besoin d'un nom de type comme SM pouvant être utilisé dans les déclarations d'instance. La déclaration newtype est souvent utilisée ici à la place de data.

Cette déclaration d'instance définit la «plomberie» de la monade : comment séquencer deux calculs et la définition d'un calcul vide. Le séquençage (l'opérateur >>=) définit un calcul (noté par le constructeur SM) passant un état initial, s0, dans c1, puis passe la valeur issue de ce calcul, r, à la fonction renvoyant le deuxième calcul, c2. Enfin, l'état sortant de c1 est passé dans c2 et le résultat global est le résultat de c2.

La définition de return est plus simple : return ne change pas du tout l'état ; il sert uniquement à apporter une valeur dans la monade.

Bien que >>= et return soient les opérations de séquençage monadique de base, nous avons également besoin de quelques primitives monadiques. Une primitive monadique est simplement une opération qui utilise l'intérieur de l'abstraction de la monade et exploite les «roues et engrenages» faisant fonctionner la monade. Par exemple, dans la monade IO, des opérateurs tels que putChar sont primitifs car ils traitent du fonctionnement interne de la monade IO. De même, notre monade d'état utilise deux primitives : readSM et updateSM. Notez que celles-ci dépendent de la structure interne de la monade - une modification de la définition du type SM nécessiterait une modification de ces primitives.

La définition de readSM et updateSM est simple : readSM fait sortir l'état de la monade pour observation tandis que updateSM permet à l'utilisateur de modifier l'état dans la monade. (Nous aurions aussi pu utiliser writeSM comme primitive mais update est souvent une façon plus naturelle de gérer l'état).

Enfin, nous avons besoin d'une fonction exécutant des calculs dans la monade, runSM. Cela prend un état initial et un calcul et donne à la fois la valeur renvoyée du calcul et l'état final.

En regardant la situation dans son ensemble, ce que nous essayons de faire est de définir un calcul global comme une série d'étapes (fonctions de type SM a), séquencées à l'aide de >>= et return. Ces étapes peuvent interagir avec l'état (via readSM ou updateSM) ou peuvent ignorer l'état. Cependant, l'utilisation (ou la non-utilisation) de l'état est cachée : nous n'invoquons ni ne séquencons nos calculs différemment selon qu'ils utilisent ou non S.

Plutôt que de présenter des exemples utilisant cette monade d'état simple, nous passons à un exemple plus complexe incluant la monade d'état. Nous définissons un petit langage intégré de calculs utilisant des ressources. C'est-à-dire que nous construisons un langage à usage spécial implémenté sous la forme d'un ensemble de types et de fonctions Haskell. Ces langages utilisent les outils de base de Haskell, les fonctions et les types, pour construire une bibliothèque d'opérations et de types spécifiquement adaptés à un domaine d'intérêt.

Dans cet exemple, considérons un calcul qui nécessite une sorte de ressource. Si la ressource est disponible, le calcul se poursuit; lorsque la ressource n'est pas disponible, le calcul s'arrête. Nous utilisons le type R pour désigner un calcul utilisant des ressources contrôlées par notre monade. La définition de R est la suivante :

Chaque calcul est une fonction des ressources disponibles vers les ressources restantes, couplée soit à un résultat, de type a, soit à un calcul suspendu, de type R a, capturant le travail effectué jusqu'au point où les ressources ont été épuisées.

L'instance Monad pour R est la suivante :

Le type de ressource est utilisé de la même manière que l'état dans la monade d'état. Cette définition se lit comme suit : pour combiner deux calculs «pleins de ressources», c1 et fc2 (une fonction produisant c2), transmettez les ressources initiales à c1. Le résultat sera soit :

• une valeur, v, et les ressources restantes, étant utilisées pour déterminer le prochain calcul (l'appel fc2 v), soit
• un calcul suspendu, pc1, et les ressources restantes au point de suspension.

La suspension doit prendre en compte le deuxième calcul : pc1 suspend uniquement le premier calcul, c1, nous devons donc lier c2 à celui-ci pour produire une suspension du calcul global. La définition de return laisse les ressources inchangées tout en déplaçant v dans la monade.

Cette déclaration d'instance définit la structure de base de la monade mais ne détermine pas comment les ressources sont utilisées. Cette monade pourrait être utilisée pour contrôler de nombreux types de ressources ou implémenter de nombreux types différents de politiques d'utilisation des ressources. Nous allons démontrer une définition très simple des ressources à titre d'exemple : nous choisissons Resource comme un entier, représentant les étapes de calcul disponibles :

Cette fonction effectue une étape à moins qu'aucune étape ne soit disponible :

Les constructeurs Left et Right font partie du type Either. Cette fonction continue le calcul dans R en renvoyant v tant qu'il y a au moins une ressource d'étape de calcul disponible. Si aucune étape n'est disponible, la fonction step suspend le calcul en cours (cette suspension est capturée dans c) et renvoie ce calcul suspendu à la monade.

Jusqu'à présent, nous avons les outils pour définir une séquence de calculs «ingénieux» (la monade) et nous pouvons exprimer une forme d'utilisation des ressources à l'aide de step. Enfin, nous devons aborder la manière dont les calculs dans cette monade sont exprimés.

Considérons une fonction d'incrément dans notre monade :

Cela définit l'incrément comme une seule étape de calcul. Le <- est nécessaire pour extraire la valeur du paramètre de la monade ; le type de iValue est Integer au lieu de R Integer.

Cette définition n'est cependant pas particulièrement satisfaisante, comparée à la définition standard de la fonction d'incrément. Pouvons-nous plutôt «habiller» des opérations existantes comme + pour qu'elles fonctionnent dans notre monde monadique ? Nous commencerons par un ensemble de fonctions de levage. Celles-ci apportent des fonctionnalités existantes dans la monade. Considérez la définition de lift1 (elle est légèrement différente de liftM1 trouvée dans la bibliothèque Monad) :

Cela prend une fonction d'un seul paramètre, f, et crée une fonction dans R qui exécute la fonction levée en une seule étape. En utilisant lift1, inc devient :

C'est mieux mais ce n'est toujours pas idéal. Tout d'abord, nous ajoutons lift2 :

Notez que cette fonction définit explicitement l'ordre d'évaluation dans la fonction levée : le calcul donnant a1 intervient avant le calcul pour a2.

En utilisant lift2, nous pouvons créer une nouvelle version de == dans la monade R :

Nous avons dû utiliser un nom légèrement différent pour cette nouvelle fonction puisque == est déjà pris, mais dans certains cas, nous pouvons utiliser le même nom pour la fonction levée et non levée. Cette déclaration d'instance permet à tous les opérateurs de Num d'être utilisés dans R :

La fonction fromInteger s'applique implicitement à toutes les constantes entières d'un programme Haskell; cette définition permet aux constantes entières d'avoir le type R Integer. Nous pouvons enfin écrire increment dans un style tout à fait naturel :

Notez que nous ne pouvons pas lever la classe Eq de la même manière que la classe Num : la signature de ==* n'est pas compatible avec les surcharges autorisées de == puisque le résultat de ==* est R Bool au lieu de Bool.

Pour exprimer des calculs intéressants dans R, nous aurons besoin d'une condition. Comme nous ne pouvons pas utiliser if (cela nécessite que le test soit de type Bool au lieu de R Bool), nous nommons la fonction ifR :

Nous sommes maintenant prêts pour un programme plus grand dans la monade R :

Ce n'est pas tout à fait la même chose qu'une fonction factorielle ordinaire, mais elle reste tout à fait lisible. L'idée de fournir de nouvelles définitions pour des opérations existantes comme + ou if est un élément essentiel de la création d'un langage intégré dans Haskell. Les monades sont particulièrement utiles pour encapsuler la sémantique de ces langages intégrés de manière propre et modulaire.

Nous sommes maintenant prêts à exécuter des programmes. Cette fonction exécute un programme en M à partir d'un nombre maximal d'étapes de calcul :

Nous utilisons le type Maybe pour gérer la possibilité que le calcul ne se termine pas dans le nombre d'étapes alloué. Nous pouvons maintenant calculer :

Enfin, nous pouvons ajouter quelques fonctionnalités plus intéressantes à cette monade. Considérons la fonction suivante :

Cette fonction exécute deux calculs en parallèle, renvoyant la valeur du premier à se terminer. Une définition possible de cette fonction est :

Cela prend une étape dans c1, renvoyant sa valeur de c1 complète ou, si c1 renvoie un calcul suspendu (c1'), il évalue c2 ||| c1'. La fonction oneStep prend une seule étape dans son argument, renvoyant soit une valeur évaluée, soit passant le reste du calcul dans f. La définition de oneStep est simple : elle donne à c1 un 1 comme argument de ressource. Si une valeur finale est atteinte, elle est renvoyée, ajustant le nombre d'étapes renvoyées (il est possible qu'un calcul revienne après n'avoir effectué aucune étape, de sorte que le nombre de ressources renvoyées ne soit pas nécessairement 0). Si le calcul est suspendu, un nombre de ressources corrigé est transmis à la continuation finale.

Nous pouvons maintenant évaluer des expressions comme run 100 (fact (-1) ||| (fact 3)) sans boucle puisque les deux calculs sont entrelacés. (Notre définition de fact boucle pour -1). De nombreuses variantes sont possibles sur cette structure de base. Par exemple, nous pourrions étendre l'état pour inclure une trace des étapes de calcul. Nous pourrions également intégrer cette monade dans la monade IO standard, permettant aux calculs en M d'interagir avec le monde extérieur. Bien que cet exemple soit peut-être plus avancé que d'autres dans ce tutoriel, il sert à illustrer la puissance des monades en tant qu'outil pour définir la sémantique de base d'un système. Nous présentons également cet exemple comme un modèle d'un petit langage spécifique au domaine, quelque chose que Haskell est particulièrement doué pour définir. De nombreux autres DSL ont été développés en Haskell ; voir le site de haskell.org pour de nombreux autres exemples. Fran, un langage d'animations réactives, et Haskore, un langage de musique informatique, sont particulièrement intéressants.