Qu’est ce qu’une monade?

Après avoir brièvement examiné Haskell récemment, quelle serait une explication brève, succincte et pratique de ce qu’est essentiellement une monade?

J’ai trouvé la plupart des explications que j’ai trouvées assez inaccessibles et manquant de détails pratiques.

Premièrement: le terme monade est un peu vide si vous n’êtes pas mathématicien. Un terme alternatif est le générateur de calcul qui décrit un peu plus ce pour quoi ils sont réellement utiles.

Vous demandez des exemples pratiques:

Exemple 1: Compréhension de liste :

[x*2 | x<-[1..10], odd x] 

Cette expression renvoie les doubles de tous les nombres impairs compris entre 1 et 10. Très utile!

Il s'avère que ce n'est vraiment que du sucre syntaxique pour certaines opérations de la monade List. La même compréhension de liste peut être écrite comme:

 do x <- [1..10] if odd x then [x * 2] else [] 

Ou même:

 [1..10] >>= (\x -> if odd x then [x*2] else []) 

Exemple 2: Entrée / Sortie :

 do putStrLn "What is your name?" name <- getLine putStrLn ("Welcome, " ++ name ++ "!") 

Les deux exemples utilisent des monads, des générateurs de calcul AKA. Le thème commun est que la monade enchaîne les opérations de manière spécifique et utile. Dans la compréhension de liste, les opérations sont chaînées de telle sorte que si une opération renvoie une liste, les opérations suivantes sont effectuées sur chaque élément de la liste. La monade IO, quant à elle, exécute les opérations de manière séquentielle, mais passe une "variable cachée", qui représente "l'état du monde", ce qui nous permet d'écrire du code E / S de manière fonctionnelle.

Il s'avère que le modèle des opérations de chaînage est très utile et est utilisé pour de nombreuses choses différentes dans Haskell.

Les exceptions sont un autre exemple: en utilisant la monade d' Error , les opérations sont chaînées de telle sorte qu'elles sont effectuées séquentiellement, sauf si une erreur est générée, auquel cas le rest de la chaîne est abandonné.

La syntaxe de liste de compréhension et la notation de do sont toutes les deux des syntaxes de sucre pour les opérations de chaînage utilisant l'opérateur >>= . Une monade est simplement un type qui supporte l'opérateur >>= .

Exemple 3: Un parsingur

C'est un parsingur très simple qui parsing une chaîne entre guillemets ou un nombre:

 parseExpr = parseSsortingng <|> parseNumber parseSsortingng = do char '"' x <- many (noneOf "\"") char '"' return (StringValue x) parseNumber = do num <- many1 digit return (NumberValue (read num)) 

Les opérations char , digit , etc. sont assez simples. Ils correspondent ou ne correspondent pas. La magie est la monade qui gère le stream de contrôle: les opérations sont effectuées séquentiellement jusqu'à ce qu'une correspondance échoue, auquel cas la monade revient en arrière sur la dernière <|> et tente l'option suivante. Encore une fois, un mode de chaînage des opérations avec une sémantique supplémentaire utile.

Exemple 4: Programmation asynchrone

Les exemples ci-dessus sont dans Haskell, mais il s'avère que F # supporte également les monades. Cet exemple est volé à Don Syme :

 let AsyncHttp(url:ssortingng) = async { let req = WebRequest.Create(url) let! rsp = req.GetResponseAsync() use stream = rsp.GetResponseStream() use reader = new System.IO.StreamReader(stream) return reader.ReadToEnd() } 

Cette méthode récupère une page Web. La ligne de frappe est l'utilisation de GetResponseAsync - elle attend réellement la réponse sur un thread séparé, tandis que le thread principal revient de la fonction. Les trois dernières lignes sont exécutées sur le thread généré lorsque la réponse a été reçue.

Dans la plupart des autres langues, vous devez créer explicitement une fonction distincte pour les lignes qui gèrent la réponse. La monade async est capable de "séparer" le bloc seul et de retarder l'exécution de la seconde moitié. (La syntaxe async {} indique que le stream de contrôle dans le bloc est défini par la monade async .)

Comment ils travaillent

Alors, comment une monade peut-elle faire tout ce truc de contrôle-stream sophistiqué? Ce qui se passe réellement dans un bloc de tâches (ou une expression de calcul comme on l'appelle dans F #), c'est que chaque opération (essentiellement chaque ligne) est encapsulée dans une fonction anonyme distincte. Ces fonctions sont ensuite combinées à l'aide de l'opérateur bind (orthographié >>= dans Haskell). L'opération de bind combinant des fonctions, elle peut les exécuter comme bon lui semble: séquentiellement, plusieurs fois, en sens inverse, en supprimer, en exécuter certaines sur un thread distinct, etc.

À titre d'exemple, il s'agit de la version étendue du code IO de l'exemple 2:

 putStrLn "What is your name?" >>= (\_ -> getLine) >>= (\name -> putStrLn ("Welcome, " ++ name ++ "!")) 

C'est plus moche, mais c'est aussi plus évident que ce qui se passe réellement. L'opérateur >>= est l'ingrédient magique: il prend une valeur (à gauche) et le combine avec une fonction (à droite) pour produire une nouvelle valeur. Cette nouvelle valeur est ensuite prise par l'opérateur suivant >>= et combinée à nouveau avec une fonction pour produire une nouvelle valeur. >>= peut être considéré comme un mini-évaluateur.

Notez que >>= est surchargé pour différents types, donc chaque monade a sa propre implémentation de >>= . (Toutes les opérations de la chaîne doivent être du type de la même monade, sinon l'opérateur >>= ne fonctionnera pas.)

L'implémentation la plus simple possible de >>= prend simplement la valeur à gauche et l'applique à la fonction de droite et renvoie le résultat, mais comme indiqué précédemment, ce qui rend tout le modèle utile, c'est qu'il y a quelque chose de supplémentaire dans le la mise en œuvre de >>= de >>= .

La manière dont les valeurs sont transmises d'une opération à l'autre présente un peu plus d'intelligence, mais cela nécessite une explication plus approfondie du système de type Haskell.

Résumer

Dans Haskell-terms, une monade est un type paramétré qui est une instance de la classe de type Monad, qui définit >>= avec quelques autres opérateurs. En termes simples, une monade est juste un type pour lequel l'opération >>= est définie.

En soi >>= est juste une manière encombrante de chaîner des fonctions, mais avec la présence de la do-notation qui cache la "plomberie", les opérations monadiques s'avèrent être une abstraction très agréable et utile, utile dans de nombreux endroits du langage , et utile pour créer vos propres mini-langues dans la langue.

Pourquoi les monades sont-elles difficiles?

Pour de nombreux apprenants Haskell, les monades sont un obstacle qu'ils rencontrent comme un mur de briques. Ce n'est pas que les monades elles-mêmes soient complexes, mais que l'implémentation repose sur de nombreuses autres fonctionnalités Haskell avancées telles que les types paramétrés, les classes de types, etc. Le problème est que les E / S Haskell sont basées sur des monades, et les E / S sont probablement l’une des premières choses à comprendre lors de l’apprentissage d’une nouvelle langue - après tout, créer des programmes qui ne produisent pas de sortie. Je n'ai pas de solution immédiate pour ce problème de la poule et de l'œuf, sauf pour traiter les E / S comme "la magie se produit ici" jusqu'à ce que vous ayez suffisamment d'expérience avec d'autres parties du langage. Pardon.

Excellent blog sur les monades: http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

Expliquer “qu’est-ce qu’une monade”, c’est un peu comme dire “qu’est-ce qu’un nombre?” Nous utilisons des chiffres tout le temps. Mais imaginez que vous ayez rencontré quelqu’un qui ne connaissait rien aux chiffres. Comment diable pourriez-vous expliquer quels sont les chiffres? Et comment commenceriez-vous à décrire pourquoi cela pourrait être utile?

Qu’est ce qu’une monade? La réponse courte: c’est une manière spécifique de chaîner les opérations ensemble.

Essentiellement, vous écrivez les étapes d’exécution et les reliez avec la “fonction de liaison”. (Dans Haskell, il s’appelle >>= .) Vous pouvez écrire les appels à l’opérateur de liaison vous-même ou utiliser la syntaxe sugar pour que le compilateur insère ces appels de fonctions pour vous. Mais de toute façon, chaque étape est séparée par un appel à cette fonction de liaison.

Donc, la fonction de liaison est comme un point-virgule; il sépare les étapes d’un processus. Le travail de la fonction de liaison consiste à extraire la sortie de l’étape précédente et à l’intégrer à l’étape suivante.

Ca ne sonne pas trop fort, non? Mais il y a plus d’une sorte de monade. Pourquoi? Comment?

Eh bien, la fonction de liaison peut simplement prendre le résultat d’une étape et l’alimenter à l’étape suivante. Mais si c’est “tout” la monade le fait … ce n’est en fait pas très utile. Et c’est important de comprendre: chaque monade utile fait autre chose que d’être simplement une monade. Chaque monade utile a un “pouvoir spécial”, ce qui la rend unique.

(Une monade qui ne fait rien de spécial s’appelle la “monade de l’identité”. Plutôt comme la fonction d’identité, cela ressemble à une chose totalement inutile, mais s’avère ne pas être … Mais c’est une autre histoire ™.)

Fondamentalement, chaque monade a sa propre implémentation de la fonction bind. Et vous pouvez écrire une fonction de liaison de manière à ce que les choses se passent bien entre les étapes d’exécution. Par exemple:

  • Si chaque étape renvoie un indicateur de réussite / échec, vous pouvez faire en sorte que bind exécute l’étape suivante uniquement si la précédente a réussi. De cette manière, une étape défaillante annule la séquence entière “automatiquement”, sans aucun test conditionnel de votre part. (The Failure Monad .)

  • En étendant cette idée, vous pouvez implémenter des “exceptions”. (La Monade d’erreur ou la Monade d’ exception .) Étant donné que vous les définissez vous-même plutôt que comme une fonctionnalité linguistique, vous pouvez définir leur fonctionnement. (Par exemple, vous voulez peut-être ignorer les deux premières exceptions et abandonner uniquement lorsqu’une troisième exception est levée.)

  • Vous pouvez faire en sorte que chaque étape retourne plusieurs résultats et que la fonction de liaison passe par-dessus, transmettant chacune à l’étape suivante pour vous. De cette façon, vous n’avez pas à continuer à écrire des boucles partout lorsque vous traitez plusieurs résultats. La fonction de liaison “automatiquement” fait tout cela pour vous. (La liste Monad .)

  • En plus de transmettre un “résultat” d’une étape à une autre, vous pouvez également faire en sorte que la fonction de liaison transmette des données supplémentaires . Ces données ne s’affichent plus dans votre code source, mais vous pouvez toujours y accéder de n’importe où sans avoir à les transmettre manuellement à chaque fonction. (Le lecteur Monad .)

  • Vous pouvez le faire pour que les “données supplémentaires” puissent être remplacées. Cela vous permet de simuler des mises à jour destructives sans effectuer de mises à jour destructives. (L’ État Monad et son cousin l’ écrivain Monad .)

  • Parce que vous ne faites que simuler des mises à jour destructives, vous pouvez sortingvialement faire des choses qui seraient impossibles avec des mises à jour destrucsortingces réelles . Par exemple, vous pouvez annuler la dernière mise à jour ou revenir à une version antérieure .

  • Vous pouvez créer une monade où les calculs peuvent être interrompus , de sorte que vous puissiez interrompre votre programme, entrer et bricoler des données d’état internes, puis les reprendre.

  • Vous pouvez implémenter des “continuations” en tant que monade. Cela vous permet de briser les esprits!

Tout cela est possible avec les monades. Bien sûr, tout cela est également parfaitement possible sans monades. C’est simplement plus facile d’ utiliser des monades.

En réalité, contrairement à la compréhension commune des Monades, elles n’ont rien à voir avec l’état. Les monades sont simplement un moyen d’emballer des choses et de fournir des méthodes pour effectuer des opérations sur les choses emballées sans les déballer.

Par exemple, vous pouvez créer un type pour en envelopper un autre, dans Haskell:

 data Wrapped a = Wrap a 

Pour emballer des choses que nous définissons

 return :: a -> Wrapped a return x = Wrap x 

Pour effectuer des opérations sans dérouler, disons que vous avez une fonction f :: a -> b , vous pouvez le faire pour que cette fonction agisse sur les valeurs encapsulées:

 fmap :: (a -> b) -> (Wrapped a -> Wrapped b) fmap f (Wrap x) = Wrap (fx) 

C’est à peu près tout ce qu’il y a à comprendre. Cependant, il apparaît qu’il existe une fonction plus générale pour effectuer cette levée , à savoir:

 bind :: (a -> Wrapped b) -> (Wrapped a -> Wrapped b) bind f (Wrap x) = fx 

bind peut faire un peu plus que fmap , mais pas l’inverse. En fait, fmap ne peut être défini qu’en termes de bind et return . Donc, lors de la définition d’une monade .. vous donnez son type (ici, il a été Wrapped a ) et ensuite dites comment fonctionnent ses opérations de return et de bind .

Ce qui est cool, c’est que cela se révèle être un modèle si général qu’il apparaît partout, l’encapsulation pure de l’état n’est que l’un d’eux.

Pour un bon article sur la façon dont les monades peuvent être utilisées pour introduire des dépendances fonctionnelles et contrôler ainsi l’ordre d’évaluation, comme il est utilisé dans la monade IO de Haskell, consultez IO Inside .

En ce qui concerne la compréhension des monades, ne vous inquiétez pas trop à ce sujet. Lisez à leur sujet ce que vous trouvez intéressant et ne vous inquiétez pas si vous ne comprenez pas tout de suite. Alors, il suffit de plonger dans une langue comme Haskell. Les monades sont l’une de ces choses où la compréhension se répand dans votre cerveau par la pratique, un jour vous réalisez soudain que vous les comprenez.

Mais tu aurais pu inventer des Monads!

Sigfpe dit:

Mais tout cela introduit des monades comme quelque chose d’ésotérique ayant besoin d’explication. Mais ce que je veux dire, c’est qu’ils ne sont pas du tout ésotériques. En fait, face à divers problèmes de functional programming, vous auriez été amené inexorablement à certaines solutions, qui sont toutes des exemples de monades. En fait, j’espère que vous pourrez les inventer maintenant si vous ne l’avez pas déjà fait. C’est alors un petit pas pour remarquer que toutes ces solutions sont en fait la même solution déguisée. Et après avoir lu ceci, vous pourriez être en meilleure position pour comprendre d’autres documents sur les monades, car vous reconnaîtrez tout ce que vous voyez comme quelque chose que vous avez déjà inventé.

Bon nombre des problèmes que les monades tentent de résoudre sont liés à la question des effets secondaires. Nous allons donc commencer avec eux. (Notez que les monades vous permettent de faire plus que gérer les effets secondaires, en particulier de nombreux types d’objects conteneur peuvent être considérés comme des monades. Certaines des introductions aux monades ont du mal à concilier ces deux utilisations différentes des monades et à se concentrer sur une seule ou L’autre.)

Dans un langage de programmation impératif tel que C ++, les fonctions ne se comportent pas comme les fonctions des mathématiques. Par exemple, supposons que nous ayons une fonction C ++ qui prend un seul argument en virgule flottante et renvoie un résultat en virgule flottante. Superficiellement, cela peut sembler un peu comme une fonction mathématique mappant des réels sur des réels, mais une fonction C ++ peut faire plus que simplement renvoyer un nombre qui dépend de ses arguments. Il peut lire et écrire les valeurs des variables globales, ainsi qu’écrire la sortie sur l’écran et recevoir les entrées de l’utilisateur. Dans un langage purement fonctionnel, cependant, une fonction ne peut que lire ce qui lui est fourni dans ses arguments et la seule façon dont elle peut avoir un effet sur le monde passe par les valeurs qu’elle renvoie.

Une monade est un type de données qui a deux opérations: >>= (aka bind ) et return (aka unit ). return prend une valeur arbitraire et crée une instance de la monade. >>= prend une instance de la monade et associe une fonction à celle-ci. (Vous pouvez déjà voir qu’une monade est un type de données étrange, car dans la plupart des langages de programmation, vous ne pouvez pas écrire une fonction qui en prend une valeur arbitraire. Les monades utilisent une sorte de polymorphism paramésortingque .)

En notation Haskell, l’interface monad est écrite

 class Monad m where return :: a -> ma (>>=) :: forall ab . ma -> (a -> mb) -> mb 

Ces opérations sont supposées obéir à certaines “lois”, mais ce n’est pas extrêmement important: les “lois” codifient simplement la manière dont les implémentations sensibles des opérations doivent se comporter (fondamentalement, que >>= et return doivent convenir de la façon dont les valeurs sont transformées) dans des instances de monade et que >>= est associatif).

Les monades ne concernent pas seulement l’état et les E / S: elles décrivent un modèle commun de calcul qui inclut le travail avec l’état, les E / S, les exceptions et le non-déterminisme. Les monades les plus simples à comprendre sont probablement les listes et les types d’option:

 instance Monad [ ] where [] >>= k = [] (x:xs) >>= k = kx ++ (xs >>= k) return x = [x] instance Monad Maybe where Just x >>= k = kx Nothing >>= k = Nothing return x = Just x 

[] et : sont les constructeurs de listes, ++ est l’opérateur de concaténation et Just et Nothing sont les constructeurs Maybe . Ces deux monades encapsulent des modèles de calcul communs et utiles sur leurs types de données respectifs (notez que cela n’a rien à voir avec les effets secondaires ou les E / S).

Vous devez vraiment vous efforcer d’écrire du code Haskell non sortingvial pour comprendre ce que sont les monades et pourquoi elles sont utiles.

Vous devez d’abord comprendre ce qu’est un foncteur. Avant cela, comprendre les fonctions d’ordre supérieur.

Une fonction d’ordre supérieur est simplement une fonction qui prend une fonction comme argument.

Un foncteur est une construction de type T pour laquelle il existe une fonction d’ordre supérieur, appelez-la map , qui transforme une fonction de type a -> b (en donnant deux types a et b ) en une fonction T a -> T b . Cette fonction de map doit également respecter les lois d’identité et de composition de sorte que les expressions suivantes renvoient la valeur true pour tout p et q (notation Haskell):

 map id = id map (p . q) = map p . map q 

Par exemple, un constructeur de type appelé List est un foncteur s’il est équipé d’une fonction de type (a -> b) -> List a -> List b qui obéit aux lois ci-dessus. La seule implémentation pratique est évidente. La fonction List a -> List b résultante effectue List a -> List b itération sur la liste donnée, appelant la fonction (a -> b) pour chaque élément et renvoie la liste des résultats.

Une monade est essentiellement un foncteur T avec deux méthodes supplémentaires, join , de type T (T a) -> T a , et unit (parfois appelée return , fork ou pure ) de type a -> T a . Pour les listes dans Haskell:

 join :: [[a]] -> [a] pure :: a -> [a] 

Pourquoi est-ce utile? Parce que vous pouvez, par exemple, map une liste avec une fonction qui renvoie une liste. Join prend la liste de listes résultante et les concatène. List est une monade car cela est possible.

Vous pouvez écrire une fonction qui map , puis join . Cette fonction s’appelle bind ou flatMap ou (>>=) ou (=<<) . Ceci est normalement la façon dont une instance de monade est donnée dans Haskell.

Une monade doit satisfaire certaines lois, à savoir que la join doit être associative. Cela signifie que si vous avez une valeur x de type [[[a]]] alors la join (join x) devrait être égale à join (map join x) . Et pure doit être une identité pour join telle que join (pure x) == x .

[Clause de non-responsabilité: j’essaie toujours de faire des monades. Ce qui suit est juste ce que j’ai compris jusqu’ici. Si cela ne va pas, j’espère que quelqu’un bien informé va m’appeler sur le tapis.]

Arnar a écrit:

Les monades sont simplement un moyen d’emballer des choses et de fournir des méthodes pour effectuer des opérations sur les choses emballées sans les déballer.

C’est justement ça. L’idée va comme ceci:

  1. Vous prenez une sorte de valeur et l’enveloppez avec des informations supplémentaires. Tout comme la valeur est d’un certain type (par exemple, un entier ou une chaîne), les informations supplémentaires sont d’un certain type.

    Par exemple, ces informations supplémentaires peuvent être un Maybe ou un IO .

  2. Ensuite, vous avez des opérateurs qui vous permettent de manipuler les données emballées tout en apportant ces informations supplémentaires. Ces opérateurs utilisent les informations supplémentaires pour décider comment modifier le comportement de l’opération sur la valeur encapsulée.

    Par exemple, Maybe Int peut-être Maybe Int peut être un Just Int ou Nothing . Maintenant, si vous ajoutez un Maybe Int à Maybe IntMaybe Int , l’opérateur vérifiera s’il s’agit des deux Just Int s à l’intérieur, et si tel est le cas, déballera les Int s, leur passera l’opérateur additionnel, dans un nouveau Just Int (qui est un Maybe Int ), et retourner ainsi un Maybe Int . Mais si l’un d’entre eux était un Nothing intérieur, cet opérateur renverra immédiatement Nothing , ce qui est encore une fois Maybe Int . De cette façon, vous pouvez prétendre que vos s Maybe IntMaybe Int sont que des nombres normaux et les exécuter régulièrement. Si vous deviez obtenir un Nothing , vos équations produiraient toujours le bon résultat – sans que vous ayez à jeter des chèques pour Nothing partout .

Mais l’exemple est juste ce qui se passe pour Maybe . Si les informations supplémentaires étaient un IO , alors cet opérateur spécial défini pour les IO S serait appelé à la place, et il pourrait faire quelque chose de totalement différent avant d’effectuer l’addition. (OK, append deux IO Int s ensemble est probablement absurde – je ne suis pas encore sûr.) (De plus, si vous portez attention à l’exemple Maybe , vous avez remarqué que «envelopper une valeur avec des choses supplémentaires» n’est pas toujours correct. Mais il est difficile d’être exact, correct et précis sans être impénétrable.)

Fondamentalement, «monad» signifie grossièrement «pattern» . Mais au lieu d’un livre rempli de modèles expliqués de manière informelle et spécifiquement nommé, vous avez maintenant une construction de langage – la syntaxe et tout le rest – qui vous permet de déclarer de nouveaux modèles comme des éléments dans votre programme . (L’imprécision ici est que tous les modèles doivent suivre une forme particulière, donc une monade n’est pas aussi générique qu’un modèle. Mais je pense que c’est le terme le plus proche que la plupart des gens connaissent et comprennent.)

Et c’est pourquoi les gens trouvent les monades si déroutantes: parce qu’elles sont un concept générique. Demander ce qui fait de quelque chose une monade est aussi vague que de demander ce qui fait de quelque chose un modèle.

Mais pensez aux implications du support syntaxique dans le langage pour l’idée d’un motif: au lieu de lire le livre de Gang of Four et de mémoriser la construction d’un motif particulier, vous écrivez simplement du code qui implémente ce motif dans un agnostique, façon générique une fois et puis vous avez terminé! Vous pouvez ensuite réutiliser ce modèle, comme Visitor ou Strategy ou Façade ou autre, simplement en décorant les opérations dans votre code sans avoir à les ré-implémenter encore et encore!

C’est pourquoi les gens qui comprennent les monades les trouvent si utiles : ce n’est pas un concept de tour d’ivoire que les snobs intellectuels se targuent de comprendre (bien sûr, bien sûr, teehee), mais rend le code plus simple.

Après beaucoup d’efforts, je pense enfin comprendre la monade. Après avoir relu ma longue critique de la réponse largement votée, je vais vous donner cette explication.

Il faut répondre à trois questions pour comprendre les monades:

  1. Pourquoi avez-vous besoin d’une monade?
  2. Qu’est ce qu’une monade?
  3. Comment une monade est-elle mise en œuvre?

Comme je l’ai noté dans mes commentaires originaux, trop d’explications de monade sont sockets en compte dans la question 3, sans et avant de couvrir de manière vraiment adéquate la question 2 ou la question 1.

Pourquoi avez-vous besoin d’une monade?

Les langages fonctionnels purs comme Haskell sont différents des langages impératifs tels que C ou Java, car un programme fonctionnel pur n’est pas nécessairement exécuté dans un ordre spécifique, une étape à la fois. Un programme Haskell s’apparente davantage à une fonction mathématique, dans laquelle vous pouvez résoudre «l’équation» dans un nombre quelconque d’ordres potentiels. Cela confère un certain nombre d’avantages, parmi lesquels le fait qu’il élimine la possibilité de certains types de bogues, en particulier ceux liés à des aspects tels que “l’état”.

Cependant, certains problèmes ne sont pas si simples à résoudre avec ce type de programmation. Certaines choses, telles que la programmation de la console et les entrées / sorties de fichiers, nécessitent des opérations dans un ordre particulier ou doivent être conservées. Une façon de résoudre ce problème consiste à créer une sorte d’object représentant l’état d’un calcul et une série de fonctions qui prennent un object d’état en entrée et renvoient un nouvel object d’état modifié.

Créons donc une hypothétique “valeur d’état”, qui représente l’état d’un écran de console. exactly how this value is constructed is not important, but let’s say it’s an array of byte length ascii characters that represents what is currently visible on the screen, and an array that represents the last line of input entered by the user, in pseudocode. We’ve defined some functions that take console state, modify it, and return a new console state.

 consolestate MyConsole = new consolestate; 

So to do console programming, but in a pure functional manner, you would need to nest a lot of function calls inside eachother.

 consolestate FinalConsole = print(input(print(myconsole, "Hello, what's your name?")),"hello, %inputbuffer%!"); 

Programming in this way keeps the “pure” functional style, while forcing changes to the console to happen in a particular order. But, we’ll probably want to do more than just a few operations at a time like in the above example. Nesting functions in that way will start to become ungainly. What we want, is code that does essentially the same thing as above, but is written a bit more like this:

 consolestate FinalConsole = myconsole: print("Hello, what's your name?"): input(): print("hello, %inputbuffer%!"); 

This would indeed be a more convenient way to write it. How do we do that though?

What is a monad?

Once you have a type (such as consolestate ) that you define along with a bunch of functions designed specifically to operate on that type, you can turn the whole package of these things into a “monad” by defining an operator like : (bind) that automatically feeds return values on its left, into function parameters on its right, and a lift operator that turns normal functions, into functions that work with that specific kind of bind operator.

How is a monad implemented?

See other answers, that seem quite free to jump into the details of that.

(See also the answers at What is a monad? )

A good motivation to Monads is sigfpe (Dan Piponi)’s You Could Have Invented Monads! (And Maybe You Already Have) . There are a LOT of other monad tutorials , many of which misguidedly try to explain monads in “simple terms” using various analogies: this is the monad tutorial fallacy ; avoid them.

As DR MacIver says in Tell us why your language sucks :

So, things I hate about Haskell:

Let’s start with the obvious. Monad tutorials. No, not monads. Specifically the tutorials. They’re endless, overblown and dear god are they tedious. Further, I’ve never seen any convincing evidence that they actually help. Read the class definition, write some code, get over the scary name.

You say you understand the Maybe monad? Good, you’re on your way. Just start using other monads and sooner or later you’ll understand what monads are in general.

[If you are mathematically oriented, you might want to ignore the dozens of tutorials and learn the definition, or follow lectures in category theory 🙂 The main part of the definition is that a Monad M involves a “type constructor” that defines for each existing type “T” a new type “MT”, and some ways for going back and forth between “regular” types and “M” types.]

Also, surprisingly enough, one of the best introductions to monads is actually one of the early academic papers introducing monads, Philip Wadler’s Monads for functional programming . It actually has practical, non-sortingvial motivating examples, unlike many of the artificial tutorials out there.

A monad is, effectively, a form of “type operator”. It will do three things. First it will “wrap” (or otherwise convert) a value of one type into another type (typically called a “monadic type”). Secondly it will make all the operations (or functions) available on the underlying type available on the monadic type. Finally it will provide support for combining its self with another monad to produce a composite monad.

The “maybe monad” is essentially the equivalent of “nullable types” in Visual Basic / C#. It takes a non nullable type “T” and converts it into a “Nullable“, and then defines what all the binary operators mean on a Nullable.

Side effects are represented simillarly. A structure is created that holds descriptions of side effects alongside a function’s return value. The “lifted” operations then copy around side effects as values are passed between functions.

They are called “monads” rather than the easier-to-grasp name of “type operators” for several reasons:

  1. Monads have ressortingctions on what they can do (see the definiton for details).
  2. Those ressortingctions, along with the fact that there are three operations involved, conform to the structure of something called a monad in Category Theory, which is an obscure branch of mathematics.
  3. They were designed by proponents of “pure” functional languages
  4. Proponents of pure functional languages like obscure twigs of mathematics
  5. Because the math is obscure, and monads are associated with particular styles of programming, people tend to use the word monad as a sort of secret handshake. Because of this no one has bothered to invest in a better name.

I wrote this mostly for me but I hope others find it useful 🙂

I believe this explanation is more correct. However, I think this treatment is still valuable and will contemplate incorporating it at a later time. Suffice it to say, where conventional function composition deals with functions plain values, Monads are about composing functions that operate on function values (higher order functions). When you are dealing with higher order functions (functions that accepts or return functions), the composition must be customized or tailor made so as to evaluate the operands when the composition is evaluated. This evaluation process can be exotic such as collecting the results of asynchronous processes. Nonetheless, this tailoring can be made to follow a pattern. A version of that pattern is called the Monad and follows very much Algebraic addition. In particular, with respect to the following content such higher order functions would be regarded as the mathematical operators in the expression accepting as operand other partially applied operators and so the functions, 1+ 2*, 3/, and 7+ in 1+ ( 2* ( 3/ ( 7+ (..) ) ) )

Monads address a problem which also shows up in arithmetic as division by zero, DivByZero . Specifically, calculations involving division must detect or allow for a DivByZero exception. This requirement makes coding such expressions in the general case messy.

The Monadic solution is to embrace DivByZero by doing the following

  1. Expand the Number type to include DivByZero as a specific value that is not a regular number: NaN , Infinity , or Null . Let’s call this new number type, Nullable .
  2. Provide a function for “lifting” or wrapping an existing Number into a Nullable type (the idea of “wrapping” is that the content Number or value can be “unwrapped” without information loss)
  3. Provide a function for “lifting” or wrapping existing operators on Number into a versions that operates on Nullable . Such a resultant “lifted” operator might merely do the following:
    1. unwrap provided Nullable operands and apply its contained Number operator on them then “lift” the resulting Number result into a Nullable
    2. detect a DivByZero operand or exception during evaluation and by pass further evaluation, producing a DivByZero value as the result to assert that ( 1 + Null = Null ). However, what actions to take depends on the programmer. In general, these wrapper functions are where a lot of the functionality of Monads are written. The monadic state information is maintained within the wrapper type itself from where the wrapped functions inspect and, per functional programming immutability approach, construct a new monadic value. In the case of Nullable , such a monadic state information would describe whether DivByZero or an actual Number exists.

So, a Monad is an expanded type together with a function that “wraps” the original type into this expanded version and another function that wraps the original operator(s) so they can handle this new expanded type. (Monads may have been a motivation for generics or type-parameters.)

It turns out that instead of merely smoothing out the handling of DivByZero (or Infinity if you will), the Monad treatment is broadly applicable to situations that can benefit from type expansion to simplify their coding. In fact, this applicability seems to be wide.

For example, the IO Monad is a type that represents the universe, literally. The intent is to recognize that the values returned by the prototypical HelloWorld program is not completely described by the result type of ssortingng and its value “Hello World!”. In fact, such a result also includes modifications to hardware and memory states of devices such as the console. For instance, after execution the console is now displaying additional text, the cursor is on a new line, and so forth. The IO Monad is merely an explicit recognition of such external effects or side effects, if you will.

Why bother?

Monads allow for ssortingctly stateless algorithms to be devised and documenting state-full ones. State-full machines are complex. For example, a machine with only 10 bits may be in 2^10 possible states. Eliminating superfluous complexity is the ideal of functional languages.

Variables hold state. Eliminating “variables” should simply stuff. Purely functional programs don’t handle variables, only values (despite usage of the term ‘variable’ in the Haskell documentation) and instead use labels or symbols or names for such values, as needed. Consequently, the closest thing to a variable in a purely functional language is the parameters received by a function as they accept new values on each invocation. (A label refers to a value whereas a variable refers to the place where a value is held. Consequently, you can modify the content of a variable but a label is the content itself. Ultimate it is better to be given an apple than a bag with an apple possibly in it.)

The absence of variables is why purely functional languages use recursion instead of loops to iterate. The act of incrementing a counter involves the use of a variable that becomes incremented and all the uncertainty with how it gets updated, when it gets tested, what value it should be and when, and then the complexity when you have multiple threads potentially accessing that same variable.

Nevertheless, So what?

Without the presence of state, a function must become a declaration or a definition of it’s results, as oppose to a masortingculation of some underlying state towards a result. Essentially, the functional expression of incFun(x) = x + 1 is simpler than the imperative expression of incImp(x) = x.add(1); return x; Here, incFun does not modify x but creates a new value. incFun may even be replaced by its definition within expressions as in 1 + incFun(x) becoming 1 + (x + 1) . On the other hand, incImp modifies the state of x . Whatever such modification means for x can be unclear and ultimately can be impossible to determine without executing the program in addition to any concurrency issues.

Such complexity gets cognitively expensive over time (2^N). In contrast, the operator, + , cannot modify x but must instead construct a new value whose result is limited to and fully determined by the values x and 1 and the definition of + . In particular, the 2^N complexity explosion is avoided. Additionally, to emphasize concurrency, incImp , unlike incFun , cannot be invoked concurrently without precautions around the sharing of the parameter since it becomes modified by each invocation.

Why call it a Monad?

A monad is characterized by a mathematical structure called a Monoid from Algebraic group theory. With that said, all it means is that a Monoid has the following three properties:

  1. has a binary operator, * , such that x * y = z for x, y, and z belonging to some type S . For example 1 ÷ 2 = 0.5 where 1, 2, and 0.5 are all of type Number . Fermé
  2. has an identity element, i , associated with the binary operator that does nothing such that (i * x) = (x * i) = x . For example the numeric operator, +, and the number, 0, in 4 + 0 = 0 + 4 = 4. Identity
  3. the order of evaluation of “segments” is irrelevant: (x * y) * z = x * (y * z) . For example the numeric operator, +, in (3 + 4) + 12 = 3 + (4 + 12) = 19 . Note, however, that the sequencing of terms must not change. Associativity

Property three (Associativity) allows expressions of arbitrary lengths to be evaluated by delineating them into segments and evaluating each segment independently such as in parallel. For example, x1*x2*...*xN may be segmented into (x1..xJ) * (xJ+1...xM) * (xM+1...xN) . The separate result, x0J * xJM * xMN , may then be collected and further evaluated similarly. Support for segmentation like this is a key technique ensuring correct concurrency and dissortingbuted evaluation as used by Google’s dissortingbuted search algorithms (a la map/reduce).

Property two (Identity), allows for greater ease in constructing expressions in various ways though it may not be entirely obvious; however, in the same way that zero was not obviously necessary to early counting systems it is useful as a concept of empty as in to wrap an empty value. Note that in the type, Nullable , Null is not an empty value but rather DivByZero . Specifically, nn + DivByZero = DivByZero whereas nn + 0 = 0 + nn = nn , hence 0 remains the identity under + , where nn is any Nullable .

Finally, there is a reason we don`t use Roman Numerals anymore…no expanded accommodation for zero or fractions, irrational numbers, negative numbers, imaginary numbers,…yeah, it seems our number system can be considered a monad.

Monads are to control flow what abstract data types are to data.

In other words, many developers are comfortable with the idea of Sets, Lists, Dictionaries (or Hashes, or Maps), and Trees. Within those data types there are many special cases (for instance InsertionOrderPreservingIdentityHashMap).

However, when confronted with program “flow” many developers haven’t been exposed to many more constructs than if, switch/case, do, while, goto (grr), and (maybe) closures.

So, a monad is simply a control flow construct. A better phrase to replace monad would be ‘control type’.

As such, a monad has slots for control logic, or statements, or functions – the equivalent in data structures would be to say that some data structures allow you to add data, and remove it.

For example, the “if” monad:

 if( clause ) then block 

at its simplest has two slots – a clause, and a block. The if monad is usually built to evaluate the result of the clause, and if not false, evaluate the block. Many developers are not introduced to monads when they learn ‘if’, and it just isn’t necessary to understand monads to write effective logic.

Monads can become more complicated, in the same way that data structures can become more complicated, but there are many broad categories of monad that may have similar semantics, but differing implementations and syntax.

Of course, in the same way that data structures may be iterated over, or traversed, monads may be evaluated.

Comstackrs may or may not have support for user-defined monads. Haskell certainly does. Ioke has some similar capabilities, although the term monad is not used in the language.

My favorite Monad tutorial:

http://www.haskell.org/haskellwiki/All_About_Monads

(out of 170,000 hits on a Google search for “monad tutorial”!)

@Stu: The point of monads is to allow you to add (usually) sequential semantics to otherwise pure code; you can even compose monads (using Monad Transformers) and get more interesting and complicated combined semantics, like parsing with error handling, shared state, and logging, for example. All of this is possible in pure code, monads just allow you to abstract it away and reuse it in modular libraries (always good in programming), as well as providing convenient syntax to make it look imperative.

Haskell already has operator overloading[1]: it uses type classes much the way one might use interfaces in Java or C# but Haskell just happens to also allow non-alphanumeric tokens like + && and > as infix identifiers. It’s only operator overloading in your way of looking at it if you mean “overloading the semicolon” [2]. It sounds like black magic and asking for trouble to “overload the semicolon” (picture enterprising Perl hackers getting wind of this idea) but the point is that without monads there is no semicolon, since purely functional code does not require or allow explicit sequencing.

This all sounds much more complicated than it needs to. sigfpe’s article is pretty cool but uses Haskell to explain it, which sort of fails to break the chicken and egg problem of understanding Haskell to grok Monads and understanding Monads to grok Haskell.

[1] This is a separate issue from monads but monads use Haskell’s operator overloading feature.

[2] This is also an oversimplification since the operator for chaining monadic actions is >>= (pronounced “bind”) but there is syntactic sugar (“do”) that lets you use braces and semicolons and/or indentation and newlines.

I’ve been thinking of Monads in a different way, lately. I’ve been thinking of them as abstracting out execution order in a mathematical way, which makes new kinds of polymorphism possible.

If you’re using an imperative language, and you write some expressions in order, the code ALWAYS runs exactly in that order.

And in the simple case, when you use a monad, it feels the same — you define a list of expressions that happen in order. Except that, depending on which monad you use, your code might run in order (like in IO monad), in parallel over several items at once (like in the List monad), it might halt partway through (like in the Maybe monad), it might pause partway through to be resumed later (like in a Resumption monad), it might rewind and start from the beginning (like in a Transaction monad), or it might rewind partway to try other options (like in a Logic monad).

And because monads are polymorphic, it’s possible to run the same code in different monads, depending on your needs.

Plus, in some cases, it’s possible to combine monads together (with monad transformers) to get multiple features at the same time.

I am still new to monads, but I thought I would share a link I found that felt really good to read (WITH PICTURES!!): http://www.matusiak.eu/numerodix/blog/2012/3/11/monads-for-the-layman/ (no affiliation)

Basically, the warm and fuzzy concept that I got from the article was the concept that monads are basically adapters that allow disparate functions to work in a composable fashion, ie be able to ssortingng up multiple functions and mix and match them without worrying about inconsistent return types and such. So the BIND function is in charge of keeping apples with apples and oranges with oranges when we’re trying to make these adapters. And the LIFT function is in charge of taking “lower level” functions and “upgrading” them to work with BIND functions and be composable as well.

I hope I got it right, and more importantly, hope that the article has a valid view on monads. If nothing else, this article helped whet my appetite for learning more about monads.

In addition to the excellent answers above, let me offer you a link to the following article (by Pasortingck Thomson) which explains monads by relating the concept to the JavaScript library jQuery (and its way of using “method chaining” to manipulate the DOM): jQuery is a Monad

The jQuery documentation itself doesn’t refer to the term “monad” but talks about the “builder pattern” which is probably more familiar. This doesn’t change the fact that you have a proper monad there maybe without even realizing it.

Monads Are Not Metaphors , but a practically useful abstraction emerging from a common pattern, as Daniel Spiewak explains.

A monad is a way of combining computations together that share a common context. It is like building a network of pipes. When constructing the network, there is no data flowing through it. But when I have finished piecing all the bits together with ‘bind’ and ‘return’ then I invoke something like runMyMonad monad data and the data flows through the pipes.

The two things that helped me best when learning about there were:

Chapter 8, “Functional Parsers,” from Graham Hutton’s book Programming in Haskell . This doesn’t mention monads at all, actually, but if you can work through chapter and really understand everything in it, particularly how a sequence of bind operations is evaluated, you’ll understand the internals of monads. Expect this to take several sortinges.

The tutorial All About Monads . This gives several good examples of their use, and I have to say that the analogy in Appendex I worked for me.

Monoid appears to be something that ensures that all operations defined on a Monoid and a supported type will always return a supported type inside the Monoid. Eg, Any number + Any number = A number, no errors.

Whereas division accepts two fractionals, and returns a fractional, which defined division by zero as Infinity in haskell somewhy(which happens to be a fractional somewhy)…

In any case, it appears Monads are just a way to ensure that your chain of operations behaves in a predictable way, and a function that claims to be Num -> Num, composed with another function of Num->Num called with x does not say, fire the missiles.

On the other hand, if we have a function which does fire the missiles, we can compose it with other functions which also fire the missiles, because our intent is clear — we want to fire the missiles — but it won’t try printing “Hello World” for some odd reason.

In Haskell, main is of type IO (), or IO [()], the distiction is strange and I will not discuss it but here’s what I think happens:

If I have main, I want it to do a chain of actions, the reason I run the program is to produce an effect — usually though IO. Thus I can chain IO operations together in main in order to — do IO, nothing else.

If I try to do something which does not “return IO”, the program will complain that the chain does not flow, or basically “How does this relate to what we are trying to do — an IO action”, it appears to force the programmer to keep their train of thought, without straying off and thinking about firing the missiles, while creating algorithms for sorting — which does not flow.

Basically, Monads appear to be a tip to the comstackr that “hey, you know this function that returns a number here, it doesn’t actually always work, it can sometimes produce a Number, and sometimes Nothing at all, just keep this in mind”. Knowing this, if you try to assert a monadic action, the monadic action may act as a comstack time exception saying “hey, this isn’t actually a number, this CAN be a number, but you can’t assume this, do something to ensure that the flow is acceptable.” which prevents unpredictable program behavior — to a fair extent.

It appears monads are not about purity, nor control, but about maintaining an identity of a category on which all behavior is predictable and defined, or does not comstack. You cannot do nothing when you are expected to do something, and you cannot do something if you are expected to do nothing (visible).

The biggest reason I could think of for Monads is — go look at Procedural/OOP code, and you will notice that you do not know where the program starts, nor ends, all you see is a lot of jumping and a lot of math,magic,and missiles. You will not be able to maintain it, and if you can, you will spend quite a lot of time wrapping your mind around the whole program before you can understand any part of it, because modularity in this context is based on interdependant “sections” of code, where code is optimized to be as related as possible for promise of efficiency/inter-relation. Monads are very concrete, and well defined by definition, and ensure that the flow of program is possible to analyze, and isolate parts which are hard to analyze — as they themselves are monads. A monad appears to be a “comprehensible unit which is predictable upon its full understanding” — If you understand “Maybe” monad, there’s no possible way it will do anything except be “Maybe”, which appears sortingvial, but in most non monadic code, a simple function “helloworld” can fire the missiles, do nothing, or destroy the universe or even distort time — we have no idea nor have any guarantees that IT IS WHAT IT IS. A monad GUARANTEES that IT IS WHAT IT IS. which is very powerful.

All things in “real world” appear to be monads, in the sense that it is bound by definite observable laws preventing confusion. This does not mean we have to mimic all the operations of this object to create classes, instead we can simply say “a square is a square”, nothing but a square, not even a rectangle nor a circle, and “a square has area of the length of one of it’s existing dimensions multiplied by itself. No matter what square you have, if it’s a square in 2D space, it’s area absolutely cannot be anything but its length squared, it’s almost sortingvial to prove. This is very powerful because we do not need to make assertions to make sure that our world is the way it is, we just use implications of reality to prevent our programs from falling off track.

Im pretty much guaranteed to be wrong but I think this could help somebody out there, so hopefully it helps somebody.

In the context of Scala you will find the following to be the simplest definition. Basically flatMap (or bind) is ‘associative’ and there exists an identity.

 trait M[+A] { def flatMap[B](f: A => M[B]): M[B] // AKA bind // Pseudo Meta Code def isValidMonad: Boolean = { // for every parameter the following holds def isAssociativeOn[X, Y, Z](x: M[X], f: X => M[Y], g: Y => M[Z]): Boolean = x.flatMap(f).flatMap(g) == x.flatMap(f(_).flatMap(g)) // for every parameter X and x, there exists an id // such that the following holds def isAnIdentity[X](x: M[X], id: X => M[X]): Boolean = x.flatMap(id) == x } } 

Par exemple

 // These could be any functions val f: Int => Option[Ssortingng] = number => if (number == 7) Some("hello") else None val g: Ssortingng => Option[Double] = ssortingng => Some(3.14) // Observe these are identical. Since Option is a Monad // they will always be identical no matter what the functions are scala> Some(7).flatMap(f).flatMap(g) res211: Option[Double] = Some(3.14) scala> Some(7).flatMap(f(_).flatMap(g)) res212: Option[Double] = Some(3.14) // As Option is a Monad, there exists an identity: val id: Int => Option[Int] = x => Some(x) // Observe these are identical scala> Some(7).flatMap(id) res213: Option[Int] = Some(7) scala> Some(7) res214: Some[Int] = Some(7) 

NOTE Ssortingctly speaking the definition of a Monad in functional programming is not the same as the definition of a Monad in Category Theory , which is defined in turns of map and flatten . Though they are kind of equivalent under certain mappings. This presentations is very good: http://www.slideshare.net/samthemonad/monad-presentation-scala-as-a-category

In practice, monad is a custom implementation of function composition operator that takes care of side effects and incompatible input and return values (for chaining).

This answer begins with a motivating example, works through the example, derives an example of a monad, and formally defines “monad”.

Consider these three functions in pseudocode:

 f() :=  g() :=  wrap(x) :=  

f takes an ordered pair of the form and returns an ordered pair. It leaves the first item untouched and appends "called f. " to the second item. Same with g .

You can compose these functions and get your original value, along with a ssortingng that shows which order the functions were called in:

  f(g(wrap(x))) = f(g()) = f() =  

You dislike the fact that f and g are responsible for appending their own log messages to the previous logging information. (Just imagine for the sake of argument that instead of appending ssortingngs, f and g must perform complicated logic on the second item of the pair. It would be a pain to repeat that complicated logic in two — or more — different functions.)

You prefer to write simpler functions:

 f(x) :=  g(x) :=  wrap(x) :=  

But look at what happens when you compose them:

  f(g(wrap(x))) = f(g()) = f(<, "called g. ">) = <<, "called g. ">, "called f. "> 

The problem is that passing a pair into a function does not give you what you want. But what if you could feed a pair into a function:

  feed(f, feed(g, wrap(x))) = feed(f, feed(g, )) = feed(f, ) =  

Read feed(f, m) as “feed m into f “. To feed a pair into a function f is to pass x into f , get out of f , and return .

 feed(f, ) := let  = f(x) in  

Notice what happens when you do three things with your functions:

First: if you wrap a value and then feed the resulting pair into a function:

  feed(f, wrap(x)) = feed(f, ) = let  = f(x) in  = let  =  in  =  =  = f(x) 

That is the same as passing the value into the function.

Second: if you feed a pair into wrap :

  feed(wrap, ) = let  = wrap(x) in  = let  =  in  =  =  

That does not change the pair.

Third: if you define a function that takes x and feeds g(x) into f :

 h(x) := feed(f, g(x)) 

and feed a pair into it:

  feed(h, ) = let  = h(x) in  = let  = feed(f, g(x)) in  = let  = feed(f, ) in  = let  = let  = f(x) in  in  = let  = let  =  in  in  = let  =  in  =  = feed(f, ) = feed(f, feed(g, )) 

That is the same as feeding the pair into g and feeding the resulting pair into f .

You have most of a monad. Now you just need to know about the data types in your program.

What type of value is ? Well, that depends on what type of value x is. If x is of type t , then your pair is a value of type “pair of t and ssortingng”. Call that type M t .

M is a type constructor: M alone does not refer to a type, but M _ refers to a type once you fill in the blank with a type. An M int is a pair of an int and a ssortingng. An M ssortingng is a pair of a ssortingng and a ssortingng. Etc.

Congratulations, you have created a monad!

Formally, your monad is the tuple .

A monad is a tuple where:

  • M is a type constructor.
  • feed takes a (function that takes a t and returns an M u ) and an M t and returns an M u .
  • wrap takes a v and returns an M v .

t , u , and v are any three types that may or may not be the same. A monad satisfies the three properties you proved for your specific monad:

  • Feeding a wrapped t into a function is the same as passing the unwrapped t into the function.

    Formally: feed(f, wrap(x)) = f(x)

  • Feeding an M t into wrap does nothing to the M t .

    Formally: feed(wrap, m) = m

  • Feeding an M t (call it m ) into a function that

    • passes the t into g
    • gets an M u (call it n ) from g
    • feeds n into f

    is the same as

    • feeding m into g
    • getting n from g
    • feeding n into f

    Formally: feed(h, m) = feed(f, feed(g, m)) where h(x) := feed(f, g(x))

Typically, feed is called bind (AKA >>= in Haskell) and wrap is called return .

If I’ve understood correctly, IEnumerable is derived from monads. I wonder if that might be an interesting angle of approach for those of us from the C# world?

For what it’s worth, here are some links to tutorials that helped me (and no, I still haven’t understood what monads are).

In the Coursera “Principles of Reactive Programming” training – Erik Meier describes them as:

 "Monads are return types that guide you through the happy path." -Erik Meijer 

What the world needs is another monad blog post, but I think this is useful in identifying existing monads in the wild.

  • monads are fractals

Sierpinski triangle

The above is a fractal called Sierpinski sortingangle, the only fractal I can remember to draw. Fractals are self-similar structure like the above sortingangle, in which the parts are similar to the whole (in this case exactly half the scale as parent sortingangle).

Monads are fractals. Given a monadic data structure, its values can be composed to form another value of the data structure. This is why it’s useful to programming, and this is why it occurrs in many situations.

http://code.google.com/p/monad-tutorial/ is a work in progress to address exactly this question.

I will try to explain Monad in the context of Haskell.

In functional programming, function composition is important. It allows our program to consist of small, easy-to-read functions.

Let’s say we have two functions: g :: Int -> Ssortingng and f :: Ssortingng -> Bool .

We can do (f . g) x , which is just the same as f (gx) , where x is an Int value.

When doing composition/applying the result of one function to another, having the types match up is important. In the above case, the type of the result returned by g must be the same as the type accepted by f .

But sometimes values are in contexts, and this makes it a bit less easy to line up types. (Having values in contexts is very useful. For example, the Maybe Int type represents an Int value that may not be there, the IO Ssortingng type represents a Ssortingng value that is there as a result of performing some side effects.)

Let’s say we now have g1 :: Int -> Maybe Ssortingng and f1 :: Ssortingng -> Maybe Bool . g1 and f1 are very similar to g and f respectively.

We can’t do (f1 . g1) x or f1 (g1 x) , where x is an Int value. The type of the result returned by g1 is not what f1 expects.

We could compose f and g with the . operator, but now we can’t compose f1 and g1 with . . The problem is that we can’t straightforwardly pass a value in a context to a function that expects a value that is not in a context.

Wouldn’t it be nice if we introduce an operator to compose g1 and f1 , such that we can write (f1 OPERATOR g1) x ? g1 returns a value in a context. The value will be taken out of context and applied to f1 . And yes, we have such an operator. It’s <=< .

We also have the >>= operator that does for us the exact same thing, though in a slightly different syntax.

We write: g1 x >>= f1 . g1 x is a Maybe Int value. The >>= operator helps take that Int value out of the "perhaps-not-there" context, and apply it to f1 . The result of f1 , which is a Maybe Bool , will be the result of the entire >>= operation.

And finally, why is Monad useful? Because Monad is the type class that defines the >>= operator, very much the same as the Eq type class that defines the == and /= operators.

To conclude, the Monad type class defines the >>= operator that allows us to pass values in a context (we call these monadic values) to functions that don't expect values in a context. The context will be taken care of.

If there is one thing to remember here, it is that Monad s allow function composition that involves values in contexts .

tl;dr

 {-# LANGUAGE InstanceSigs #-} newtype Id t = Id t instance Monad Id where return :: t -> Id t return = Id (=<<) :: (a -> Id b) -> Id a -> Id b f =<< (Id x) = fx 

Prologue

The application operator $ of functions

 forall a b. a -> b 

is canonically defined

 ($) :: (a -> b) -> a -> b f $ x = fx infixr 0 $ 

in terms of Haskell-primitive function application fx ( infixl 10 ). Composition . is defined in terms of $ as

 (.) :: (b -> c) -> (a -> b) -> (a -> c) f . g = \ x -> f $ gx infixr 9 . 

and satisfies the equivalences forall fg h.

  f . id = f :: c -> d Right identity id . g = g :: b -> c Left identity (f . g) . h = f . (g . h) :: a -> d Associativity 

. is associative, and id is its right and left identity.

The Kleisli sortingple

In programming, a monad is functor type constructor with an instance of the monad type class. There are several equivalent variants of definition and implementation, each carrying slightly different intuitions about the monad abstraction.

A functor is a type constructor f of kind * -> * with an instance of the functor type class.

 {-# LANGUAGE KindSignatures #-} class Functor (f :: * -> *) where map :: (a -> b) -> (fa -> fb) 

In addition to following statically enforced type protocol, instances of the functor type class must obey the algebraic functor laws forall f g.

  map id = id :: ft -> ft Identity map f . map g = map (f . g) :: fa -> fc Composition / short cut fusion 

Functor computations have the type

 forall f t. Functor f => ft 

A computation cr consists in results r within context c .

Unary monadic functions or Kleisli arrows have the type

 forall ma b. Functor m => a -> mb 

Kleisi arrows are functions that take one argument a and return a monadic computation mb .

Monads are canonically defined in terms of the Kleisli sortingple forall m. Functor m =>

 (m, return, (=<<)) 

implemented as the type class

 class Functor m => Monad m where return :: t -> mt (=<<) :: (a -> mb) -> ma -> mb infixr 1 =<< 

The Kleisli identity return is a Kleisli arrow that promotes a value t into monadic context m . Extension or Kleisli application =<< applies a Kleisli arrow a -> mb to results of a computation ma .

Kleisli composition <=< is defined in terms of extension as

 (<=<) :: Monad m => (b -> mc) -> (a -> mb) -> (a -> mc) f <=< g = \ x -> f =<< gx infixr 1 <=< 

<=< composes two Kleisli arrows, applying the left arrow to results of the right arrow's application.

Instances of the monad type class must obey the monad laws , most elegantly stated in terms of Kleisli composition: forall fg h.

  return <=< g = g :: b -> mc Left identity f <=< return = f :: c -> md Right identity (f <=< g) <=< h = f <=< (g <=< h) :: a -> md Associativity 

<=< is associative, and return is its right and left identity.

Identité

The identity type

 type Id t = t 

is the identity function on types

 Id :: * -> * 

Interpreted as a functor,

  return :: t -> Id t = id :: t -> t (=<<) :: (a -> Id b) -> Id a -> Id b = ($) :: (a -> b) -> a -> b (<=<) :: (b -> Id c) -> (a -> Id b) -> (a -> Id c) = (.) :: (b -> c) -> (a -> b) -> (a -> c) 

In canonical Haskell, the identity monad is defined

 newtype Id t = Id t instance Functor Id where map :: (a -> b) -> Id a -> Id b map f (Id x) = Id (fx) instance Monad Id where return :: t -> Id t return = Id (=<<) :: (a -> Id b) -> Id a -> Id b f =<< (Id x) = fx 

Option

An option type

 data Maybe t = Nothing | Just t 

encodes computation Maybe t that may not yield a result t , computation that may “fail”. The option monad is defined

 instance Functor Maybe where map :: (a -> b) -> (Maybe a -> Maybe b) map f (Just x) = Just (fx) map _ Nothing = Nothing instance Monad Maybe where return :: t -> Maybe t return = Just (=<<) :: (a -> Maybe b) -> Maybe a -> Maybe b f =<< (Just x) = fx _ =<< Nothing = Nothing 

a -> Maybe b is applied only if Maybe a yields a result.

 newtype Nat = Nat Int 

The natural numbers can be encoded as those integers greater than or equal to zero.

 toNat :: Int -> Maybe Nat toNat i | i >= 0 = Just (Nat i) | otherwise = Nothing 

The natural numbers are not closed under subtraction.

 (-?) :: Nat -> Nat -> Maybe Nat (Nat n) -? (Nat m) = toNat (n - m) infixl 6 -? 

The option monad covers a basic form of exception handling.

 (-? 20) <=< toNat :: Int -> Maybe Nat 

liste

The list monad, over the list type

 data [] t = [] | t : [t] infixr 5 : 

and its additive monoid operation “append”

 (++) :: [t] -> [t] -> [t] (x : xs) ++ ys = x : xs ++ ys [] ++ ys = ys infixr 5 ++ 

encodes nonlinear computation [t] yielding a natural amount 0, 1, ... of results t .

 instance Functor [] where map :: (a -> b) -> ([a] -> [b]) map f (x : xs) = fx : map f xs map _ [] = [] instance Monad [] where return :: t -> [t] return = (: []) (=<<) :: (a -> [b]) -> [a] -> [b] f =<< (x : xs) = fx ++ f =<< xs _ =<< [] = [] 

Extension concatenates ++ all result lists [b] from applications fx of a Kleisli arrow a -> [b] to elements of [a] into a single result list [b] .

Let the proper divisors of a positive integer n be

 divisors :: Integral t => t -> [t] divisors n = filter (`divides` n) [2 .. n - 1] divides :: Integral t => t -> t -> Bool (`divides` n) = (== 0) . (n `rem`) 

puis

 forall n. let f = f <=< divisors in fn = [] 

In defining the monad type class, instead of extension =<< , the Haskell standard uses its flip, the bind operator >>= .

 class Applicative m => Monad m where (>>=) :: forall a b. ma -> (a -> mb) -> mb (>>) :: forall a b. ma -> mb -> mb m >> k = m >>= \ _ -> k {-# INLINE (>>) #-} return :: a -> ma return = pure fail :: Ssortingng -> ma fail s = errorWithoutStackTrace s 

For simplicitys sake, this explanation uses the type class hierarchy

 class Functor f class Functor m => Monad m 

In Haskell, the current standard hierarchy is

 class Functor f class Functor p => Applicative p class Applicative m => Monad m 

because not only is every monad a functor, but every applicative is a functor and every monad an applicative, too.

Using the list monad, the imperative pseudocode

 for a in (1, ..., 10) for b in (1, ..., 10) p <- a * b if even(p) yield p 

roughly translates to the do block

 do a <- [1 .. 10] b <- [1 .. 10] let p = a * b guard (even p) return p 

the equivalent monad comprehension

 [p | a <- [1 .. 10], b <- [1 .. 10], let p = a * b, even p] 

and the expression

 [1 .. 10] >>= (\ a -> [1 .. 10] >>= (\ b -> let p = a * b in guard (even p) >> return p ) ) 

Do notation and monad comprehensions are syntactic sugar for nested bind expressions. The bind operator is used for local name binding of monadic results.

 let x = v in e = (\ x -> e) $ v = v & (\ x -> e) do r <- m; c = (\ r -> c) =<< m = m >>= (\ r -> c) 

 (&) :: a -> (a -> b) -> b (&) = flip ($) infixl 0 & 

The guard function is defined

 guard :: Additive m => Bool -> m () guard True = return () guard False = fail 

where the unit type or “empty tuple”

 data () = () 

Additive monads that support choice and failure can be abstracted over using a type class

 class Monad m => Additive m where fail :: mt (<|>) :: mt -> mt -> mt infixl 3 <|> instance Additive Maybe where fail = Nothing Nothing <|> m = m m <|> _ = m instance Additive [] where fail = [] (<|>) = (++) 

where fail and <|> form a monoid forall kl m.

  fail <|> l = l k <|> fail = k (k <|> l) <|> m = k <|> (l <|> m) 

and fail is the absorbing/annihilating zero element of additive monads

 _ =<< fail = fail 

If in

 guard (even p) >> return p 

even p is true, then the guard produces [()] , and, by the definition of >> , the local constant function

 \ _ -> return p 

is applied to the result () . If false, then the guard produces the list monad's fail [] , which yields no result for a Kleisli arrow to be applied >> to.

Etat

Infamously, monads are used to encode stateful computation.

A state processor is a function

 forall st t. st -> (t, st) 

that transitions a state st and yields a result t . The state st can be anything. Nothing, flag, count, array, handle, machine, world.

The type of state processors is usually called

 type State st t = st -> (t, st) 

The state processor monad is the kinded * -> * functor State st . Kleisli arrows of the state processor monad are functions

 forall st a b. a -> (State st) b 

In canonical Haskell, the lazy version of the state processor monad is defined

 newtype State st t = State { stateProc :: st -> (t, st) } instance Functor (State st) where map :: (a -> b) -> ((State st) a -> (State st) b) map f (State p) = State $ \ s0 -> let (x, s1) = p s0 in (fx, s1) instance Monad (State st) where return :: t -> (State st) t return x = State $ \ s -> (x, s) (=<<) :: (a -> (State st) b) -> (State st) a -> (State st) b f =<< (State p) = State $ \ s0 -> let (x, s1) = p s0 in stateProc (fx) s1 

A state processor is run by supplying an initial state:

 run :: State st t -> st -> (t, st) run = stateProc eval :: State st t -> st -> t eval = fst . run exec :: State st t -> st -> st exec = snd . run 

State access is provided by primitives get and put , methods of abstraction over stateful monads:

 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} class Monad m => Stateful m st | m -> st where get :: m st put :: st -> m () 

m -> st declares a functional dependency of the state type st on the monad m ; that a State t , for example, will determine the state type to be t uniquely.

 instance Stateful (State st) st where get :: State st st get = State $ \ s -> (s, s) put :: st -> State st () put s = State $ \ _ -> ((), s) 

with the unit type used analogously to void in C.

 modify :: Stateful m st => (st -> st) -> m () modify f = do s <- get put (fs) gets :: Stateful m st => (st -> t) -> mt gets f = do s <- get return (fs) 

gets is often used with record field accessors.

The state monad equivalent of the variable threading

 let s0 = 34 s1 = (+ 1) s0 n = (* 12) s1 s2 = (+ 7) s1 in (show n, s2) 

where s0 :: Int , is the equally referentially transparent, but infinitely more elegant and practical

 (flip run) 34 (do modify (+ 1) n <- gets (* 12) modify (+ 7) return (show n) ) 

modify (+ 1) is a computation of type State Int () , except for its effect equivalent to return () .

 (flip run) 34 (modify (+ 1) >> gets (* 12) >>= (\ n -> modify (+ 7) >> return (show n) ) ) 

The monad law of associativity can be written in terms of >>= forall mf g.

 (m >>= f) >>= g = m >>= (\ x -> fx >>= g) 

ou

 do { do { do { r1 <- do { x <- m; r0 <- m; r0 <- m; = do { = r1 <- f r0; f r0 r1 <- fx; g r1 }; g r1 } g r1 } } } 

Like in expression-oriented programming (eg Rust), the last statement of a block represents its yield. The bind operator is sometimes called a “programmable semicolon”.

Iteration control structure primitives from structured imperative programming are emulated monadically

 for :: Monad m => (a -> mb) -> [a] -> m () for f = foldr ((>>) . f) (return ()) while :: Monad m => m Bool -> mt -> m () while cm = do b <- c if b then m >> while cm else return () forever :: Monad m => mt forever m = m >> forever m 

Input/Output

 data World 

The I/O world state processor monad is a reconciliation of pure Haskell and the real world, of functional denotative and imperative operational semantics. A close analogue of the actual ssortingct implementation:

 type IO t = World -> (t, World) 

Interaction is facilitated by impure primitives

 getChar :: IO Char putChar :: Char -> IO () readFile :: FilePath -> IO Ssortingng writeFile :: FilePath -> Ssortingng -> IO () hSetBuffering :: Handle -> BufferMode -> IO () hTell :: Handle -> IO Integer . . . . . . 

The impurity of code that uses IO primitives is permanently protocolized by the type system. Because purity is awesome, what happens in IO , stays in IO .

 unsafePerformIO :: IO t -> t 

Or, at least, should.

The type signature of a Haskell program

 main :: IO () main = putStrLn "Hello, World!" 

expands to

 World -> ((), World) 

A function that transforms a world.

Epilogue

The category whiches objects are Haskell types and whiches morphisms are functions between Haskell types is, “fast and loose”, the category Hask .

A functor T is a mapping from a category C to a category D ; for each object in C an object in D

 Tobj : Obj(C) -> Obj(D) f :: * -> * 

and for each morphism in C a morphism in D

 Tmor : HomC(X, Y) -> HomD(Tobj(X), Tobj(Y)) map :: (a -> b) -> (fa -> fb) 

where X , Y are objects in C . HomC(X, Y) is the homomorphism class of all morphisms X -> Y in C . The functor must preserve morphism identity and composition, the “structure” of C , in D .

  Tmor Tobj T(id) = id : T(X) -> T(X) Identity T(f) . T(g) = T(f . g) : T(X) -> T(Z) Composition 

The Kleisli category of a category C is given by a Kleisli sortingple

  

of an endofunctor

 T : C -> C 

( f ), an identity morphism eta ( return ), and an extension operator * ( =<< ).

Each Kleisli morphism in Hask

  f : X -> T(Y) f :: a -> mb 

by the extension operator

  (_)* : Hom(X, T(Y)) -> Hom(T(X), T(Y)) (=<<) :: (a -> mb) -> (ma -> mb) 

is given a morphism in Hask 's Kleisli category

  f* : T(X) -> T(Y) (f =<<) :: ma -> mb 

Composition in the Kleisli category .T is given in terms of extension

  f .T g = f* . g : X -> T(Z) f <=< g = (f =<<) . g :: a -> mc 

and satisfies the category axioms

  eta .T g = g : Y -> T(Z) Left identity return <=< g = g :: b -> mc f .T eta = f : Z -> T(U) Right identity f <=< return = f :: c -> md (f .T g) .T h = f .T (g .T h) : X -> T(U) Associativity (f <=< g) <=< h = f <=< (g <=< h) :: a -> md 

which, applying the equivalence transformations

  eta .T g = g eta* . g = g By definition of .T eta* . g = id . g forall f. id . f = f eta* = id forall fg h. f . h = g . h ==> f = g (f .T g) .T h = f .T (g .T h) (f* . g)* . h = f* . (g* . h) By definition of .T (f* . g)* . h = f* . g* . h . is associative (f* . g)* = f* . g* forall fg h. f . h = g . h ==> f = g 

in terms of extension are canonically given

  eta* = id : T(X) -> T(X) Left identity (return =<<) = id :: mt -> mt f* . eta = f : Z -> T(U) Right identity (f =<<) . return = f :: c -> md (f* . g)* = f* . g* : T(X) -> T(Z) Associativity (((f =<<) . g) =<<) = (f =<<) . (g =<<) :: ma -> mc 

Monads can also be defined in terms not of Kleislian extension, but a natural transformation mu , in programming called join . A monad is defined in terms of mu as a sortingple over a category C , of an endofunctor

  T : C -> C f :: * -> * 

and two natural tranformations

  eta : Id -> T return :: t -> ft mu : T . T -> T join :: f (ft) -> ft 

satisfying the equivalences

  mu . T(mu) = mu . mu : T . T . T -> T . T Associativity join . map join = join . join :: f (f (ft)) -> ft mu . T(eta) = mu . eta = id : T -> T Identity join . map return = join . return = id :: ft -> ft 

The monad type class is then defined

 class Functor m => Monad m where return :: t -> mt join :: m (mt) -> mt 

The canonical mu implementation of the option monad:

 instance Monad Maybe where return = Just join (Just m) = m join Nothing = Nothing 

The concat function

 concat :: [[a]] -> [a] concat (x : xs) = x ++ concat xs concat [] = [] 

is the join of the list monad.

 instance Monad [] where return :: t -> [t] return = (: []) (=<<) :: (a -> [b]) -> ([a] -> [b]) (f =<<) = concat . map f 

Implementations of join can be translated from extension form using the equivalence

  mu = id* : T . T -> T join = (id =<<) :: m (mt) -> mt 

The reverse translation from mu to extension form is given by

  f* = mu . T(f) : T(X) -> T(Y) (f =<<) = join . map f :: ma -> mb 

  • Philip Wadler: Monads for functional programming

  • Simon L Peyton Jones, Philip Wadler: Imperative functional programming

  • Jonathan MD Hill, Keith Clarke: An introduction to category theory, category theory monads, and their relationship to functional programming ´

  • Kleisli category

  • Eugenio Moggi: Notions of computation and monads

  • What a monad is not

But why should a theory so abstract be of any use for programming?

The answer is simple: as computer scientists, we value abstraction ! When we design the interface to a software component, we want it to reveal as little as possible about the implementation. We want to be able to replace the implementation with many alternatives, many other 'instances' of the same 'concept'. When we design a generic interface to many program libraries, it is even more important that the interface we choose have a variety of implementations. It is the generality of the monad concept which we value so highly, it is because category theory is so abstract that its concepts are so useful for programming.

It is hardly suprising, then, that the generalisation of monads that we present below also has a close connection to category theory. But we stress that our purpose is very practical: it is not to 'implement category theory', it is to find a more general way to structure combinator libraries. It is simply our good fortune that mathematicians have already done much of the work for us!

from Generalising Monads to Arrows by John Hughes

Explaining monads seems to be like explaining control-flow statements. Imagine that a non-programmer asks you to explain them?

You can give them an explanation involving the theory – Boolean Logic, register values, pointers, stacks, and frames. But that would be crazy.

You could explain them in terms of the syntax. Basically all control-flow statements in C have curly brackets, and you can distinguish the condition and the conditional code by where they are relative to the brackets. That may be even crazier.

Or you could also explain loops, if statements, routines, subroutines, and possibly co-routines.

Monads can replace a fairly large number of programming techniques. There’s a specific syntax in languages that support them, and some theories about them.

They are also a way for functional programmers to use imperative code without actually admitting it, but that’s not their only use.