Une monade (T, eta, mu) sur une catégorie C est formée d'un foncteur T de C dans C et de deux transformations naturelles : eta de l'identité sur C vers T et mu de TT vers T, satisfaisant certaines équations.
(Haskell en dix secondes : expr :: type indique que l'expression expr est de type type; \id -> expr déclare une nouvelle fonction anonyme prenant en paramètre une variable id et ayant pour corps expr. Par exemple,
ajoute2 x = x + 2
est équivalent à \x.x + 2.)
Haskell, est un langage purement fonctionnel, ce qui signifie que ses fonctions ne font pas d'effets de bords : appliquées au même argument, elles rendent toujours le même résultat, comme en mathématiques. Évidemment, on ne peut parfois pas échapper aux effets de bords : par exemple, pour faire des entrées sorties !
Imaginons, par exemple, une fonction readLine qui lit une chaîne de caractères sur la console. En Haskell, chaque programme se voit attribuer un type unique par le compilateur*; imaginons celui de notre fonction readLine. Premier jet :
readLine :: QQchose -> String
Qu'est-ce que ce QQchose ? A priori, rien de bien particulier. En C, on déclarerait une fonction sans paramètres (pour les dinos, void); en Haskell ça n'a pas de sens. On dispose justement d'un type approprié : () (à prononcer « younite »), habité par une unique valeur, elle aussi notée (), ce qui peut d'ailleurs entretenir une certaine confusion.
On a donc :
readLine :: () -> String
Problème plus grave : ça ne correspond pas à ce que j'ai décrit plus haut. Il est évident qu'un appel readLine () renverra différentes valeurs selon ce que rentre l'utilisateur... Intuitivement, le coeur du problème est que readLine, en faisant un effet de bord, agit sur le environnement qui l'entoure. On pourrait modéliser cela par le fait qu'on dispose d'un type Envir symbolisant ce fameux monde/environnement; son type deviendrait alors :
readLine :: Envir -> String
Se pose un nouveau problème : de toute évidence, readLine a... changé le monde ! Plus précisément, elle a entre autres consommé l'entrée de l'utilisateur sur le terminal où est lancé notre application. Elle doit donc nous renvoyer le nouveau monde obtenu après qu'elle ait effectué ses opérations.
readLine :: Envir -> (String, Envir)
Bien, il semblerait que nous ayons progressé dans notre modélisation. Maintenant, imaginons par exemple une fonction putLine qui affiche une chaîne sur la console puis passe à la ligne (un équivalent du puts de C). Nous savons que le type :
putLine :: String -> ()
Ne fonctionnera pas; notre fonction faisant des effets de bords, on va imiter la méthode utilisée ci-dessus et prendre un argument supplémentaire, sous forme du monde, et renvoyer le nouveau monde obtenu :
putLine :: String -> Envir -> ((), Envir)
Maintenant, nous pouvons écrire du code de ce style :
repete w = let (ligne, w') = readLine w in
putLine ("Vous avez entre " ++ ligne) w'
Petit exercice : quel sera le type de notre fonction demandeAge ?
demandeAge :: Envir -> ((), Envir)
Ça fonctionne. Toutefois, a priori il reste un problème : je peux me tromper en passant mes « mondes » d'appel en appel, ici par exemple en confondant w et w' dans l'appel à putLine. En fait, idéalement, la « plomberie » de passage du « monde » ne devrait pas être réalisée explicitement par le programmeur.
Pour résoudre ce problème, on peut commencer par remarquer l'apparition progressive d'un motif récurrent dans nos types :
Envir -> (truc, Envir)
Étant programmeurs, nous sommes feignants : et si on s'abstrayait de ce type en l'encapsulant dans une nouvelle abbréviation ? On va déclarer un nouveau type, synonyme du précédent** :
type IO truc = Envir -> (truc, Envir)
Et là, on vient mine de rien de réaliser une petite percée conceptuelle : on est désormais capable de distinguer, en regardant son type, un programme faisant potentiellement des effets de bords d'un programme n'en faisant pas. Nos types deviennent :
Maintenant, il est intéressant de se demander quelles fonctions génériques sont communes à tous nos « programmes à effets de bords potentiels ». Déjà, on peut voir tout programme comme faisant potentiellement des effets de bords, en remarquant qu'il suffit qu'il ne modifie pas le monde qu'il reçoit :
return :: a -> IO a
return a =\w.(a, w)
Ensuite, on aimerait, comme dit précédemment, éliminer la plomberie, c'est-à-dire le passage explicite du monde d'une fonction à l'autre. Essayons de nos laissons guider par, par exemple, la composition des fonctions readLine et putLine. Imaginons une hypothétique fonction compose portant bien son nom; quel serait son type ?
Qu'avons nous gagné ? Et bien, si on cache a l'utilisateur la nature de notre type IO, par exemple dans une bibliothèque séparée, il n'est plus possible de se tromper dans le passage des mondes. Il deviendra également impossible de mélanger arbirairement code « pur » et code à effets de bords. Cerise sur le gatal, Haskell propose du sucre syntaxique automatique se traduisant simplement dans le style utilisé ci-dessus, mais qui permet d'écrire :
demandeAge :: IO ()
demangeAge = do {
ligne <- readLine;
putLine ("Vous avez entré " ++ ligne);
}
Comme vous devez déjà vous en douter depuis un petit moment, ce triplet (IO, return, >>=) est... une monade. Et il s'avère que ce genre de construction apparaît TRÈS souvent en programmation, grosso-modo dès qu'on a besoin de parler d'un calcul se faisant dans un certain contexte; citons par exemple la monade des listes qui nous permet de programmer de façon non-déterministe. Elles viennent de la théorie des catégories, une jolie branche des mathématiques abstraites qui sert de plus en plus en théorie (et pratique :-) ?) des langages de programmation.
Donc, pour la définition programmatique : une monade est un triplet (T, return :: a -> T a, (>>=) : T a -> (a -> T b) -> T b), satisfaisant six équations que je vous épargnerais, mais qui, intuitivement, impliquent que return et >>= « coopèrent » bien.
Une monade est donc une façon simple de représenter et encapsuler des programmes s'exécutant dans un certain contexte, de les distinguer par leurs types, et de les composer. Pour plus de détails, je suggère la lecture de l'excellent papier de Philip Wadler : http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba(...)
...
Bon, ok, le Haskell n'est pas simple; mais au moins, il est différent, et je pense qu'il vaut la peine d'être appris, à défaut d'être utilisé.
* : Je simplifie un peu.
** : Je prends mes aise avec les déclarations de type Haskell pour la clareté de l'exposé, que les puristes m'épargnent.
[^] # Re: La simplicité d'Haskell????
Posté par auve . En réponse à la dépêche Concours de logo Haskell. Évalué à 10.
(Haskell en dix secondes : expr :: type indique que l'expression expr est de type type; \id -> expr déclare une nouvelle fonction anonyme prenant en paramètre une variable id et ayant pour corps expr. Par exemple,
ajoute2 x = x + 2
est équivalent à \x.x + 2.)
Haskell, est un langage purement fonctionnel, ce qui signifie que ses fonctions ne font pas d'effets de bords : appliquées au même argument, elles rendent toujours le même résultat, comme en mathématiques. Évidemment, on ne peut parfois pas échapper aux effets de bords : par exemple, pour faire des entrées sorties !
Imaginons, par exemple, une fonction readLine qui lit une chaîne de caractères sur la console. En Haskell, chaque programme se voit attribuer un type unique par le compilateur*; imaginons celui de notre fonction readLine. Premier jet :
readLine :: QQchose -> String
Qu'est-ce que ce QQchose ? A priori, rien de bien particulier. En C, on déclarerait une fonction sans paramètres (pour les dinos, void); en Haskell ça n'a pas de sens. On dispose justement d'un type approprié : () (à prononcer « younite »), habité par une unique valeur, elle aussi notée (), ce qui peut d'ailleurs entretenir une certaine confusion.
On a donc :
readLine :: () -> String
Problème plus grave : ça ne correspond pas à ce que j'ai décrit plus haut. Il est évident qu'un appel readLine () renverra différentes valeurs selon ce que rentre l'utilisateur... Intuitivement, le coeur du problème est que readLine, en faisant un effet de bord, agit sur le environnement qui l'entoure. On pourrait modéliser cela par le fait qu'on dispose d'un type Envir symbolisant ce fameux monde/environnement; son type deviendrait alors :
readLine :: Envir -> String
Se pose un nouveau problème : de toute évidence, readLine a... changé le monde ! Plus précisément, elle a entre autres consommé l'entrée de l'utilisateur sur le terminal où est lancé notre application. Elle doit donc nous renvoyer le nouveau monde obtenu après qu'elle ait effectué ses opérations.
readLine :: Envir -> (String, Envir)
Bien, il semblerait que nous ayons progressé dans notre modélisation. Maintenant, imaginons par exemple une fonction putLine qui affiche une chaîne sur la console puis passe à la ligne (un équivalent du puts de C). Nous savons que le type :
putLine :: String -> ()
Ne fonctionnera pas; notre fonction faisant des effets de bords, on va imiter la méthode utilisée ci-dessus et prendre un argument supplémentaire, sous forme du monde, et renvoyer le nouveau monde obtenu :
putLine :: String -> Envir -> ((), Envir)
Maintenant, nous pouvons écrire du code de ce style :
repete w =
let (ligne, w') = readLine w in
putLine ("Vous avez entre " ++ ligne) w'
Petit exercice : quel sera le type de notre fonction demandeAge ?
demandeAge :: Envir -> ((), Envir)
Ça fonctionne. Toutefois, a priori il reste un problème : je peux me tromper en passant mes « mondes » d'appel en appel, ici par exemple en confondant w et w' dans l'appel à putLine. En fait, idéalement, la « plomberie » de passage du « monde » ne devrait pas être réalisée explicitement par le programmeur.
Pour résoudre ce problème, on peut commencer par remarquer l'apparition progressive d'un motif récurrent dans nos types :
Envir -> (truc, Envir)
Étant programmeurs, nous sommes feignants : et si on s'abstrayait de ce type en l'encapsulant dans une nouvelle abbréviation ? On va déclarer un nouveau type, synonyme du précédent** :
type IO truc = Envir -> (truc, Envir)
Et là, on vient mine de rien de réaliser une petite percée conceptuelle : on est désormais capable de distinguer, en regardant son type, un programme faisant potentiellement des effets de bords d'un programme n'en faisant pas. Nos types deviennent :
readLine :: IO String
putLine :: String -> IO ()
demandeAge :: IO ()
Maintenant, il est intéressant de se demander quelles fonctions génériques sont communes à tous nos « programmes à effets de bords potentiels ». Déjà, on peut voir tout programme comme faisant potentiellement des effets de bords, en remarquant qu'il suffit qu'il ne modifie pas le monde qu'il reçoit :
return :: a -> IO a
return a = \w.(a, w)
Ensuite, on aimerait, comme dit précédemment, éliminer la plomberie, c'est-à-dire le passage explicite du monde d'une fonction à l'autre. Essayons de nos laissons guider par, par exemple, la composition des fonctions readLine et putLine. Imaginons une hypothétique fonction compose portant bien son nom; quel serait son type ?
compose :: (IO String) -> (String -> IO ()) -> IO ()
Soit, en s'abstrayant des types « concrets » String et () :
compose :: IO truc -> (truc -> IO bidule) -> IO bidule
Cette fonction est traditionnellement notée « >>= », à prononcer « bind ». Notre code devient donc :
demandeAge :: IO ()
demandeAge = readLine >>= (\ligne.putLine ("Vous avez entré " ++ ligne))
Qu'avons nous gagné ? Et bien, si on cache a l'utilisateur la nature de notre type IO, par exemple dans une bibliothèque séparée, il n'est plus possible de se tromper dans le passage des mondes. Il deviendra également impossible de mélanger arbirairement code « pur » et code à effets de bords. Cerise sur le gatal, Haskell propose du sucre syntaxique automatique se traduisant simplement dans le style utilisé ci-dessus, mais qui permet d'écrire :
demandeAge :: IO ()
demangeAge = do {
ligne <- readLine;
putLine ("Vous avez entré " ++ ligne);
}
Comme vous devez déjà vous en douter depuis un petit moment, ce triplet (IO, return, >>=) est... une monade. Et il s'avère que ce genre de construction apparaît TRÈS souvent en programmation, grosso-modo dès qu'on a besoin de parler d'un calcul se faisant dans un certain contexte; citons par exemple la monade des listes qui nous permet de programmer de façon non-déterministe. Elles viennent de la théorie des catégories, une jolie branche des mathématiques abstraites qui sert de plus en plus en théorie (et pratique :-) ?) des langages de programmation.
Donc, pour la définition programmatique : une monade est un triplet (T, return :: a -> T a, (>>=) : T a -> (a -> T b) -> T b), satisfaisant six équations que je vous épargnerais, mais qui, intuitivement, impliquent que return et >>= « coopèrent » bien.
Une monade est donc une façon simple de représenter et encapsuler des programmes s'exécutant dans un certain contexte, de les distinguer par leurs types, et de les composer. Pour plus de détails, je suggère la lecture de l'excellent papier de Philip Wadler : http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba(...)
...
Bon, ok, le Haskell n'est pas simple; mais au moins, il est différent, et je pense qu'il vaut la peine d'être appris, à défaut d'être utilisé.
* : Je simplifie un peu.
** : Je prends mes aise avec les déclarations de type Haskell pour la clareté de l'exposé, que les puristes m'épargnent.