Comprendre les monades

Il y a quelques temps est passé en bêta une traduction d’un article sur les monades. Celle-ci a été retirée, en raison des reproches faits à l’article d’origine. Alors j’ai décidé de me frotter à l’exercice d’un cours d’introduction aux monades en programmation.

Mon cours se veut basique : expliquer ce que sont les monades, et à quoi elles servent, dans les grandes lignes. L’idée étant qu’il constitue le premier jalon d’une série, qui pourrait s’organiser ainsi.

• La présente introduction.
• La classe de type Monad en Haskell, ses super-classes Functor et Applicative, et les lois régissant tout cela.
• Les concepts avancés liés aux monades : monades additives, transformateurs de monades, limitations des monades, Arrow…
• Les maths derrière les monades, ce dernier n’ayant pas besoin de s’appuyer sur les deux précédents.

Le cours n'est pas accessible aux débutants complets en programmation, mais il devrait être compréhensible même sans connaître particulièrement Haskell. Mieux encore, une section entière est consacrée à montrer à quoi peuvent ressembler des monades dans d’autres langages.

J'aime bien ton cours. Franchement, il est bien. Peut-être que tu aurais pu montrer directement la typeclass Monad après la liste des conditions pour avoir une monade, pour aider le lecteur à visualiser. Autre chose, je trouve dommage de ne pas avoir expliqué ce que fait bind dans le cas de la liste en tant que monade, c'est pourtant assez pratique. Je ne parle pas de donner un exemple d'utilisation mais d'expliquer très vite fait ce que ça fait.

Pour Rust, c'est vrai que ça se prête bien à certains éléments du fonctionnel mais je rêve toujours qu'ils implémentent les types d'ordre supérieur pour pouvoir définir une sorte de typeclass.

Quand tu parlais de Maybe pour la gestion des erreurs, j'aurais rajouté que cela ressemble à l'utilisation de NULL en C.

Il est de retour ! Merci pour le tutoriel, je te fais mes remarques. Pour information, je connais très vaguement le Haskell mais ai fait de l'OCaml (basique) en prépa.

Définition et exemples

Une monade, c’est une boite, pouvant contenir un ou plusieurs objets de même nature, conçue de telle manière que l’on puisse placer un objet dans la boite

J'ai un peu buté sur l'expression "placer un objet dans la boite", parce qu'elle sous-entend, je crois, qu'on ne place qu'un seul objet. Après réflexion, c'est débile, mais c'est ce que je me suis dit à la première lecture, donc je le relève. Tu pourrais utiliser le terme "ajouter" ou un truc du genre.

sortir l’objet de sa boite juste le temps d’effectuer une action sur lui, avant de le remettre dans la boite.

Peut-on sortir un objet sans le remettre ?

data MaMonade a = MonConstructeur a

Ca fait un peu bizarre d'appeler le type MaMonade, puisque tu dis plus haut qu'une monade est, pour être pédant, un triplet contenant un type paramétré, etc.

En fait, je ne suis pas sûr de comprendre à quoi correspond cette ligne, puisque je ne vois pas en quoi ce type permet "d’encapsuler un ou plusieurs objets de même type". Je m'attendais à un truc du genre une liste.

le a signale que c’est un type paramétré à un seul paramètre

J'ai peur que la notion de type paramétré ne soit pas claire pour certains, comme peut le dénoter ma remarque précédente.

bind :: MaMonade a -> (a -> MaMonade b) -> MaMonade b

Je ne comprends pas tellement le typage ici. J'ai peut-être mal interprété tes propos, mais il me semble que bind permet de "sortir l’objet de sa boite juste le temps d’effectuer une action sur lui, avant de le remettre dans la boite". Comme la boite ne contient que des objets du même type a, on devrait avoir a = b, non ?

bind (MaMonade contenu) fonction = fonction contenu

objet me semble plus clair que contenu, vu que tu as dit plus haut qu'on encapsulait des objets.

return = Just

Peut-être pourrais-tu indiquer en commentaire que c'est équivalent à return x = Just x ? Ca me semble plus clair, même si je n'ai pas d'argument à te donner.

Merci.

bind :: MaMonade a -> (a -> MaMonade b) -> MaMonade b

Je ne comprends pas tellement le typage ici. J'ai peut-être mal interprété tes propos, mais il me semble que bind permet de "sortir l’objet de sa boite juste le temps d’effectuer une action sur lui, avant de le remettre dans la boite". noComme la boite ne contient que des objets du même type a, on devrait avoir a = b, non ?

En fait non, la "bidouille" à appliquer sur l'objet "extrait" de la boîte peut très bien changer son type. Par exemple, on pourrait appliquer une fonction qui transforme un Int en Maybe String. Le cas a = b est un cas particulier. Il faut bien voir que la monade c'est Maybe, donc un type d'ordre supérieur, et pas Maybe Int qui est de kind * contrairement à Maybe qui est de kind * -> *.

Oui, ça c'est une bonne idée de le préciser.

En fait non, la "bidouille" à appliquer sur l'objet "extrait" de la boîte peut très bien changer son type.

On ne peut donc pas le remettre dans la boite par la suite ? En fait, j'ai du mal avec cette notion de boite, vu que je ne comprends pas tellement comment un type paramétré peut contenir plusieurs objets.

Une monade c'est un type prenant un autre type en paramètre, d'où l'appellation de type d'ordre supérieur. Imagine que ta monade c'est un colis contenant quelque chose de type X. bind, écrit le plus souvent >>= en Haskell, revient à dire que si tu as un colis contenant quelque chose de type X et un sous-traitant qui sait faire un colis contenant un truc de type Y à partir de seulement un truc de type X. Si on regarde la typeclass Monad (j'ai enlevé des trucs dont on se fiche, c'est pour l'exemple):

1
2
3

class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

Tu vois bien qu'une monade prend un type a en paramètre (regarde le constructeur return), et que l'opérateur >>= prend un objet de type m a et une fonction capable de transformer ce a en m b, et >>= va se charger de renvoyer ce fameux m b.

Le problème c'est que cette approche avec des boîtes marche bien pour expliquer le principe dans le cas de Maybe mais dans le cas de List c'est pas joli joli. C'est bien pour commencer à se forger une intuition de ce qu'est une monade dans des cas simples mais la vraie définition de ce qu'est une monade c'est simplement sa typeclass. Á un moment il faut juste accepter la définition.

Au passage, l'approche des boîtes est un peu trop similaire à mon goût à la description d'un foncteur (au sens fonctionnel hein, pas au sens C++, rien à voir), qui peut se voir comme un conteneur qui permet d'appliquer des fonctions directement à son contenu sans l'en sortir.

Je pense que ça serait bien plus simple/clair d'introduire la notion de Monade avec la construction return+fmap+join à la place de return+bind.

Je trouve que comme ça, on voit directement l'interêt principal que peut apporter ce genre de construction: une Monade apporte les outils nécessaires pour transférer mes Type d'un monde à un autre (à l'aide de ton constructeur, par exemple), mes objets en des objets du deuxième monde (à l'aide de 'return') ainsi que mes fonctions vers des fonctions du deuxième monde (à l'aide de 'fmap'). On a donc de la réutilisabilité! Cool!

Exemple: Monade Liste

• L'image des types int, float par la monade seront dans ce cas, list<int> et list<float>
• L'image de 1 sera une liste [1] de type list<int>
• L'image d'un fonction de type int -> float sera une fonction de type list<int>->list<float>. Notamment, fmap((x) => x*pi) sera la fonction qui multipliera par pi tous les elements de la liste en argument et regroupera les résultats dans une liste de float.

L'autre point serait de montrer la composabilité des monades (exemple, une monade List+Either), de montrer la lourdeur que peut avoir des définition de nouvelles fonctions et de comment résoudre ça avec les Monads Transformers.

Pour moi, ce sont les deux points clés qui justifient l'importance des monades et facilitent la compréhension de celles ci.

J'aime bien mis à part le fait que je trouve mieux d'avoir vu la théorie avant pour vraiment apprécier les monades. Le plus important pour moi, c'est de faire comprendre l'idée, le concept, et la théorie formalise bien tout ça justement.

Sinon en petit exemple d'utilisation sympa, basé sur le défi de la calculatrice (uniquement en notation polonaise inverse).

Je suis en train d'apprendre Haskell et je ne peux qu'approuver ce tutoriel et suis impatient de le lire.

J'aime bien mis à part le fait que je trouve mieux d'avoir vu la théorie avant pour vraiment apprécier les monades. Le plus important pour moi, c'est de faire comprendre l'idée, le concept, et la théorie formalise bien tout ça justement.

Bien que je sois d'accord avec toi à 1000%, je pense qu'un amuse-gueule a tout à fait sa place. ça introduira la notion aux gens qui ne connaissent pas et ça poussera les plus curieux (ceux qui veulent s'approfondir) à lire des tuto/livres de référence (et pourquoi pas, un autre tuto ZdS). Tant que ça répond bien au "pourquoi devrais-je m'y intéressé?".

En parlant d'exemples, on peut penser aussi aux futures/promises. En C++ par exemple, on a std::future pour la Monade, std::make_ready_future() pour 'return', std::future::then() pour map (à un binding d'argument près), std::future::unwrap() pour 'join'.

Wah ! Déjà tant de réponses en une nuit !

Peut-être que tu aurais pu montrer directement la typeclass Monad après la liste des conditions pour avoir une monade, pour aider le lecteur à visualiser.

Je préfère laisser la classe de type Monad dans un cours à part, pour trois raisons.

• Je m’efforce que le cours soit accessible même sans connaître le Haskell, et ça m’obligerait à introduire la notion de classe de types, qui est assez lourde et peut induire en confusion les gens qui viennent de la POO si l’explication n’est pas assez détaillée.
• Autant que possible, je me limite ici aux aspects de la question qui ne sont pas spécifique au Haskell, pour garder au cours son caractère généraliste.
• La présentation en serait nécessairement bâclée, puisque si j’introduis les contraintes Functor et Applicative, je phagocyte totalement le second cours.

Autre chose, je trouve dommage de ne pas avoir expliqué ce que fait bind dans le cas de la liste en tant que monade, c'est pourtant assez pratique. Je ne parle pas de donner un exemple d'utilisation mais d'expliquer très vite fait ce que ça fait.

Je vais voir si je peux rendre ça un peu plus explicite.

Pour Rust, c'est vrai que ça se prête bien à certains éléments du fonctionnel mais je rêve toujours qu'ils implémentent les types d'ordre supérieur pour pouvoir définir une sorte de typeclass.

Ça existe, les classes de type en Rust. Ils appellent ça des traits, et ça oblige à adopter la syntaxe de méthode, mais ça recouvre totalement le concept. Ça permet même de faire des contraintes de type sur des fonctions / types paramétrés.

Je ne suis pas convaincu. NULL n’est pas typé, et c’est plutôt considéré comme un défaut du langage qu’une fonctionnalité. Plus le fait que la comparaison ne parlera qu’à ceux qui connaissent le C, et je veux que le cours reste aussi général que possible.

Il est de retour !

Je fais que passer.

J'ai un peu buté sur l'expression "placer un objet dans la boite", parce qu'elle sous-entend, je crois, qu'on ne place qu'un seul objet. Après réflexion, c'est débile, mais c'est ce que je me suis dit à la première lecture, donc je le relève. Tu pourrais utiliser le terme "ajouter" ou un truc du genre.

Je vais reformuler pour rester cohérent.

Peut-on sortir un objet sans le remettre ?

Ça dépend de la monade. En général, c’est possible, mais certaines monades ne le permettent pas, comme IO. En tout état de cause, la monade elle-même n’intègre pas ce mécanisme, c’est le reste du langage (généralement par le biais du filtrage par motif) qui offre cette possibilité.

Ca fait un peu bizarre d'appeler le type MaMonade, puisque tu dis plus haut qu'une monade est, pour être pédant, un triplet contenant un type paramétré, etc.

Tout juste.

En fait, je ne suis pas sûr de comprendre à quoi correspond cette ligne, puisque je ne vois pas en quoi ce type permet "d’encapsuler un ou plusieurs objets de même type". Je m'attendais à un truc du genre une liste.

Une liste n’est qu’une des nombreuses possibilités. Ce que je fais dans cette ligne de code-là correspondrait à ça en C++.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

template <typename A> // Le `a` de `MaMonade a` et `MonConstructeur a`.
class MaMonade {      // Le type s’appelle MaMonade.
    private:
    A param;          // L’objet qui est encapsulé.
    MaMonade(const A& a) : param(a) { }
                      // Le constructeur ne s’appelle pas `MaMonade` donc
                      // le constructeur de C++ ne doit pas être accessible.
    public:
    static MaMonade MonConstructeur(const A& a) {
        return MaMonade(a);
    }                 // Le constructeur avec le bon nom.
};

J’ai donné un exemple très simple, parce que je cherchais à montrer la plus simple des monades possibles, mais on peut tout à fait encapsuler plusieurs objets, du moment qu’ils restent du même type. Par exemple, on peut imaginer ce type-ci, même si je ne vois pas trop quelle utilité pourrait avoir une monade qui s’en servirait comme base.

1

data Pixel a = PixelConstr a a a

Le type Pixel encapsule bien trois objets de même type.

J'ai peur que la notion de type paramétré ne soit pas claire pour certains, comme peut le dénoter ma remarque précédente.

C’est sans doute vrai. Je ne sais pas quoi te répondre, là, tout de suite. Je vais y réfléchir.

Je ne comprends pas tellement le typage ici. J'ai peut-être mal interprété tes propos, mais il me semble que bind permet de "sortir l’objet de sa boite juste le temps d’effectuer une action sur lui, avant de le remettre dans la boite". Comme la boite ne contient que des objets du même type a, on devrait avoir a = b, non ?

Alors je n’ai sans doute pas été suffisamment clair. Si la boite contient plusieurs objets à un instant t du programme, alors ces objets doivent être du même type. Tu ne peux pas mettre des Int et des Float en même temps, en revanche, tu peux sortir des Float et y remettre des Int.

objet me semble plus clair que contenu, vu que tu as dit plus haut qu'on encapsulait des objets.

C’est noté.

Tu as raison, tout le monde n’est pas familier des fonctions curryfiées.

Pour moi, un foncteur, c’est une généralisation du concept de liste.

Je pense que ça serait bien plus simple/clair d'introduire la notion de Monade avec la construction return+fmap+join à la place de return+bind.

Je trouve justement qu’elle est moins simple, raison pour laquelle je ne l’ai pas utilisée. Du coup, je préfère laisser cette approche pour le second cours, celui qui abordera les foncteurs, donc fmap.

Beaucoup trop complexe pour un cours d’introduction. Les transformeurs de monades, je les laisse pour le troisième cours, celui sur les concepts avancés.

Il est souvent reproché aux cours sur les monades d'adopter une approche trop mathématique, qui ne parle pas à grand monde. C’est ce que j’ai voulu éviter. Je me place dans l’optique de quelqu’un qui cherche à comprendre ce que c’est sans forcément même être familier avec la programmation fonctionnelle.

J’ai donné un exemple très simple, parce que je cherchais à montrer la plus simple des monades possibles, mais on peut tout à fait encapsuler plusieurs objets, du moment qu’ils restent du même type.

Du coup, tu pourrais indiquer qu'on crée une monade dont le type ne peut contenir qu'un objet. Autrement dit, expliciter le "essayons de créer la plus simple des monades".

en revanche, tu peux sortir des Float et y remettre des Int.

Par contre, si je veux remettre des Int, il faut que j'aie sorti tous les Float ? Mais comme on n' a qu'un seul objet encapsulé dans notre exemple, on peut se permettre de transformer notre objet sans s'occuper du type (puisque le sortir de la boite revient à vider celle-ci, donc on peut y remettre ce qu'on veut).

C’est sans doute vrai. Je ne sais pas quoi te répondre, là, tout de suite. Je vais y réfléchir.

Après réflexion, cette notion ne pose pas tellement problème. Tu pourrais l'expliciter un peu, en donnant un exemple (typiquement, une liste), mais je pense que ça se comprend plutôt facilement. Par contre, j'ai plus de mal à faire le rapport entre la définition des monades et l'analogie du départ. Si je ne m'abuse, le type paramétré correspond à la boite et les objets "contenus" par ce type, ben les objets. Peut-être que spécifier le constructeur du premier exemple plutôt que de mettre un MonConstructeur aiderait ?

Je comprends ton point de vue. Je pense juste qu'il est nécessaire de voir la théorie derrière, sans avoir quelque chose de très poussé non plus. Par exemple, le wikibook sur la théorie des catégories (appliquée à Haskell) me semble accessible.

Euh ouais mais non. Il faut déjà être familier avec les notions d'application pour comprendre ce qu'est un morphisme, de composition, d'associativité, de morphisme identité … C'est clairement pas accessible avant un certain niveau en maths. Tu as les notions nécessaires, mais ce n'est probablement pas le cas de tout le monde sur ce site.

Ben je sais pas, mais les notions de composition, d'application et d'identité tu les as certainement déjà appliquées aux fonctions. Après, je pense que de toute façon les monades ne sont pas un concept facile.

Après avoir cogité un peu sur la question, je commence à comprendre ce qu'est une monade. Par contre, j'ignore à quoi ça sert. Ca tombe bien…

Utilité

Reprenons notre fonction divM de plus haut, ainsi que les fonctions return et bind que nous avions écrites dans la première section. Voici comment on pourrait écrire divM_3.

J'ai eu du mal avec le code, du fait que je ne suis pas familier avec la syntaxe. J'ignore si c'est possible en Haskell mais tu pourrais passer par des variables intermédiaires, bien que ce ne soit pas idiomatique. C'est en fait en quelque sorte ce que tu fais en-dessous, sans les appels à bind.

En pratique, bind ressort les données de la boite, mais la fonction passée en paramètre de bind les y remet aussitôt

Je ne suis pas sûr de comprendre ça. Il me semble que bind prend une seule valeur monadique en paramètre (un seul objet). Comment ça se passe si la boite en contient plusieurs ?

En la « marquant » du sceau de l’impureté

Mouarfarfarf !

Dans le premier code, prénom et nom ne dépendent pas l’une de l’autre : rien ne vous permet de savoir si votre programme va commencer par demander le prénom ou le nom

Tu pourrais peut-être expliciter cela. En effet, comme prénom apparaît en premier dans le code, on pourrait s'attendre à ce que l'appel correspondant à getLine soit effectué avant l'autre.

Un outil multi-langages

Notez bien que la bibliothèque standard du Rust propose le type Option

C'est également le cas de OCaml : http://ocaml-lib.sourceforge.net/doc/Option.html.

Pas de remarques particulières sur la dernière section.

Merci.

En terme de fmap et join, on a ceci: (bind m f) == join(fmap f m)

Ainsi, si par exemple f associe à chaque entier la liste de ses décimales et si mest une liste d'entiers, alors bind m f serait une liste qui contiendrait toutes les décimales de tous les entiers contenus dans m.

Du coup, bind [10, 25, 2002] f == [1, 0, 2, 5, 2, 0, 0, 2] fmap f m == [[1, 0], [2, 5], [2, 0, 0, 2]] et le join c'est une concaténation de ces liste. Ce qui donne le résultat du bind.

Très sincèrement, non. Je ne comprends pas grand chose à la théorie des catégories, alors même que je n’ai aucune difficulté à utiliser les monades en programmation. Je préfère vraiment laisser les aspects mathématiques à un autre cours.

D’ailleurs, je n’ai peut-être pas été assez explicite, mais j’invite chaudement quiconque se sent de le faire à rédiger le quatrième tuto, celui sur les maths derrière les monades, car je ne pourrai pas m’en occuper.

J'ai eu du mal avec le code, du fait que je ne suis pas familier avec la syntaxe. J'ignore si c'est possible en Haskell mais tu pourrais passer par des variables intermédiaires, bien que ce ne soit pas idiomatique.

J’ai essayé, mais ce n’est vraiment pas idiomatique du tout, et ça donne un code encore plus incompréhensible. Désolé.

J’ai reformulé la définition de ce qu’est une valeur monadique, car elle t’a visiblement induit en confusion. Dans Maybe 2, 2 est l’objet encapsulé, Maybe est le type monadique, et c’est l’ensemble Maybe 2 qui constitue la valeur monadique. Donc pour une monade où le type monadique encapsule plusieurs objets, comme le type liste, on peut très bien avoir des valeurs monadiques comme [12, 13, 14] (qui constitue bien une seule valeur monadique contenant plusieurs objets).

Voilà ! J’ai pris en compte toutes les remarques que je n’ai pas explicitement récusées dans mes réponses, et ça donne cette nouvelle mouture du tuto. J’ai pris le parti de ne pas rédiger un passage spécifiquement dédié à expliquer ce qu’est un type paramétré, car je n’ai pas trouvé où le placer élégamment. Dites-moi si c’est compréhensible quand même.

Je suis ouvert à toute remarque supplémentaire sur le fond mais le texte ne devrait plus vraiment bouger. Je suis donc en attente d’un relevé des fôtes, d’orthographe comme de typographie, que j’aurais pu laisser passer.

Je teste un nouveau système pour commenter les contenus : j'en exporte l'archive, l'importe, ajoute des blocs de citation (et uniquement cela) sur le tutoriel cloné, et ajoute l'auteur dans les auteurs. C'est plus simple que de faire des citations sous forme de copier-coller et tu pourras travailler sur le clone et mettre à jour l'original via un export/import. Dis-moi ce que tu en penses.

C'est pas bête du tout comme idée. Si vous vous rendez compte avec Dominus Carnufex que c'est efficace, peut-être que vous pourriez proposer de créer une fonctionnalité "cloner" pour simplifier xe processus.

Il y a un léger souci avec le code C++ du Maybe. Les objets temporaires en C++ ont une durée de vie limitée. Typiquement, une fois sorti de la fonction à laquelle tu passes fait ton objet temporaire, l'objet cesse d'exister et tout pointeur dessus devient invalide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main()  {
    std::function<const Maybe<double> (const double&)> div0M
        = [](const double x){ return divM(x, 0.0); };
    std::function<const Maybe<double> (const double&)> div5M
        = [](const double x){ return divM(x, 5.0); };
    std::function<const Maybe<double> (const double&)> div7M
        = [](const double x){ return divM(x, 7.0); };
    std::function<const Maybe<double> (const double&)> print
        = [](const double x){ std::cout<<x<<std::endl; return Maybe<double>::Just(x); };

    Maybe<double>::Just(35.0).bind(div5M).bind(print).bind(div0M).bind(div7M);
    return 0;
}

Pour implémenter un Maybe en C++, on est obligé de copier l'objet. T'as donc deux possibilités: (1) utiliser des unions (ou une union sur des tableaux de char comme ce que fait boost::optional) en utilisant des placement new et des appels explicites aux destructeurs (option clean mais beaucoup plus complexe pour un exemple aussi simple) ou (2) utiliser des shared_ptr (ou boost::optional) comme le code suivant (lignes 2, 13 et 16).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <functional>
#include <memory> // ou #include <boost/optional.hpp>

template <typename A>
class Maybe {
    private:
    enum class Constr {
        Nothing,
        Just
    };

    const Constr    _c;
    const std::shared_ptr<const A>  _a; // ou const boost::optional<const A> _a;

    Maybe()           noexcept : _c(Constr::Nothing), _a(nullptr) { } // ou _a(boost::none)
    Maybe(const A& a) noexcept : _c(Constr::Just), _a(std::make_shared<const A>(a)) { } // ou _a(a)

// ..le reste est inchangé
};