¿Qué es una mónada?

Después de haber mirado brevemente a Haskell recientemente, ¿cuál sería una explicación breve, sucinta y práctica acerca de qué es una mónada en esencia?

He encontrado que la mayoría de las explicaciones que he encontrado son bastante inaccesibles y carecen de detalles prácticos.

Primero: el término mónada es un poco vacío si no eres un matemático. Un término alternativo es el generador de cálculos que es un poco más descriptivo de lo que realmente son útiles.

Usted pide ejemplos prácticos:

Ejemplo 1: comprensión de la lista :

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

Esta expresión devuelve los dobles de todos los números impares en el rango de 1 a 10. ¡Muy útil!

Resulta que esto es realmente solo azúcar sintáctica para algunas operaciones dentro de la lista de mónadas. La misma lista de comprensión se puede escribir como:

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

O incluso:

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

Ejemplo 2: Entrada / Salida :

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

Ambos ejemplos usan mónadas, constructores de computación AKA. El tema común es que la mónada encadena operaciones de alguna manera específica y útil. En la lista de comprensión, las operaciones están encadenadas de modo que si una operación devuelve una lista, se realizan las siguientes operaciones en cada elemento de la lista. La mónima IO, por otro lado, realiza las operaciones secuencialmente, pero pasa una "variable oculta" a lo largo, que representa "el estado del mundo", lo que nos permite escribir código de E / S de una manera puramente funcional.

Resulta que el patrón de operaciones de encadenamiento es bastante útil y se usa para muchas cosas diferentes en Haskell.

Otro ejemplo son las excepciones: al usar la mónada Error , las operaciones se encadenan de manera tal que se realizan de forma secuencial, excepto si se produce un error, en cuyo caso se abandona el rest de la cadena.

Tanto la syntax de comprensión de lista como la notación de do son azúcares sintácticos para operaciones de encadenamiento utilizando el operador >>= . Una mónada es básicamente solo un tipo que admite el operador >>= .

Ejemplo 3: un analizador

Este es un analizador muy simple que analiza una cadena entre comillas o un número:

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

Las operaciones char , digit , etc. son bastante simples. Ellos coinciden o no coinciden. La magia es la mónada que gestiona el flujo de control: las operaciones se realizan de forma secuencial hasta que falla una coincidencia, en cuyo caso la mónada retrocede a la última <|> e intenta la siguiente opción. De nuevo, una forma de encadenar operaciones con alguna semántica adicional y útil.

Ejemplo 4: Progtwigción asincrónica

Los ejemplos anteriores están en Haskell, pero resulta que F # también admite mónadas. Este ejemplo es robado de Don Syme :

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

Este método busca una página web. La línea de golpe es el uso de GetResponseAsync : realmente espera la respuesta en un hilo separado, mientras que el hilo principal regresa de la función. Las últimas tres líneas se ejecutan en el subproceso generado cuando se recibe la respuesta.

En la mayoría de los demás idiomas, debería crear explícitamente una función separada para las líneas que manejan la respuesta. La mónada async es capaz de "dividir" el bloque por sí misma y posponer la ejecución de la segunda mitad. (La syntax async {} indica que el flujo de control en el bloque está definido por la mónada async ).

Cómo trabajan ellos

Entonces, ¿cómo puede una mónada hacer todas estas cosas elegantes de control de flujo? Lo que sucede realmente en un do-block (o una expresión de cálculo como se llaman en F #), es que cada operación (básicamente cada línea) se envuelve en una función anónima separada. Estas funciones se combinan utilizando el operador bind (deletreado >>= en Haskell). Dado que la operación de bind combina funciones, puede ejecutarlas como lo considere oportuno: secuencialmente, varias veces, al revés, descartar algunas, ejecutar algunas en una secuencia separada cuando se lo parezca y así sucesivamente.

Como ejemplo, esta es la versión expandida del código IO del ejemplo 2:

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

Esto es más feo, pero también es más obvio lo que está sucediendo realmente. El operador >>= es el ingrediente mágico: toma un valor (en el lado izquierdo) y lo combina con una función (en el lado derecho), para producir un nuevo valor. Este nuevo valor es luego tomado por el próximo operador >>= y nuevamente combinado con una función para producir un nuevo valor. >>= puede verse como un mini-evaluador.

Tenga en cuenta que >>= está sobrecargado para diferentes tipos, por lo que cada mónada tiene su propia implementación de >>= . (Todas las operaciones en la cadena tienen que ser del tipo de la misma mónada, de lo contrario, el operador >>= no funcionará).

La implementación más simple posible de >>= simplemente toma el valor de la izquierda y lo aplica a la función de la derecha y devuelve el resultado, pero como se dijo antes, lo que hace que todo el patrón sea útil es cuando hay algo extra en el proceso. la implementación de mónada de >>= .

Existe cierta habilidad adicional en la forma en que los valores pasan de una operación a la siguiente, pero esto requiere una explicación más profunda del sistema de tipo Haskell.

Resumiendo

En Haskell-terms, una mónada es un tipo parametrizado que es una instancia de la clase de tipo Monad, que define >>= junto con algunos otros operadores. En términos simples, una mónada es simplemente un tipo para el cual se define la operación >>= .

En sí mismo >>= es solo una forma engorrosa de encadenar funciones, pero con la presencia de la notación do que oculta la "fontanería", las operaciones monádicas resultan ser una abstracción muy útil y útil, útiles en muchos lugares del lenguaje y útil para crear sus propios mini-idiomas en el idioma.

¿Por qué las mónadas son duras?

Para muchos estudiantes Haskell, las mónadas son un obstáculo que golpean como una pared de ladrillos. No es que las mónadas en sí mismas sean complejas, sino que la implementación se basa en muchas otras características avanzadas de Haskell como tipos parametrizados, clases de tipos, etc. El problema es que Haskell I / O está basado en mónadas, y las E / S son probablemente una de las primeras cosas que quieres entender cuando aprendes un nuevo idioma. Después de todo, no es muy divertido crear progtwigs que no producen ningún salida. No tengo una solución inmediata para este problema de huevo y gallina, excepto tratar E / S como "la magia sucede aquí" hasta que tenga suficiente experiencia con otras partes del lenguaje. Lo siento.

Excelente blog sobre mónadas: http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

Explicar “qué es una mónada” es como decir “¿qué es un número?” Usamos números todo el tiempo. Pero imagina que conociste a alguien que no sabía nada sobre números. ¿Cómo demonios explicarías qué números son? ¿Y cómo comenzarías a describir por qué podría ser útil?

¿Qué es una mónada? La respuesta corta: es una forma específica de encadenar operaciones juntas.

Básicamente, está escribiendo pasos de ejecución y vinculándolos con la “función de enlace”. (En Haskell, se llama >>= .) Puede escribir las llamadas al operador de enlace usted mismo, o puede usar el azúcar de syntax que hace que el comstackdor inserte esas llamadas de función para usted. Pero de cualquier manera, cada paso está separado por una llamada a esta función de enlace.

Entonces la función de enlace es como un punto y coma; separa los pasos en un proceso. El trabajo de la función de enlace es tomar el resultado del paso anterior y alimentarlo en el próximo paso.

Eso no suena demasiado duro, ¿verdad? Pero hay más de un tipo de mónada. ¿Por qué? ¿Cómo?

Bueno, la función de enlace solo puede tomar el resultado de un paso y alimentarlo al próximo paso. Pero si eso es “todo”, la mónada lo hace … eso en realidad no es muy útil. Y eso es importante de entender: cada mónada útil hace algo más además de ser solo una mónada. Cada mónada útil tiene un “poder especial”, lo que la hace única.

(Una mónada que no hace nada especial se llama “mónada de identidad”. Más bien como la función de identidad, esto suena como una cosa totalmente sin sentido, pero resulta que no es … Pero esa es otra historia ™.)

Básicamente, cada mónada tiene su propia implementación de la función bind. Y puede escribir una función de vinculación de forma que no moleste entre los pasos de ejecución. Por ejemplo:

  • Si cada paso devuelve un indicador de éxito / falla, puede hacer que bind ejecute el siguiente paso solo si el anterior tuvo éxito. De esta forma, un paso fallido cancela la secuencia completa “automáticamente”, sin que usted realice ninguna prueba condicional. (La falla mónada )

  • Extendiendo esta idea, puede implementar “excepciones”. ( Monad de error o Monad de excepción ). Como los está definiendo usted mismo en lugar de ser una función de idioma, puede definir cómo funcionan. (Por ejemplo, quizás quieras ignorar las dos primeras excepciones y abortar solo cuando se lanza una tercera excepción).

  • Puede hacer que cada paso devuelva resultados múltiples , y hacer que la función de vinculación se repita sobre ellos, y alimentar a cada uno en el próximo paso para usted. De esta forma, no tiene que seguir escribiendo bucles por todos lados cuando se trata de resultados múltiples. La función de enlace “automáticamente” hace todo eso por usted. (La lista Mónada )

  • Además de pasar un “resultado” de un paso a otro, puede hacer que la función de enlace también pase datos adicionales . Esta información ahora no aparece en su código fuente, pero aún puede acceder a ella desde cualquier lugar, sin tener que pasarla manualmente a cada función. (The Reader Monad .)

  • Puede hacerlo para que los “datos adicionales” puedan ser reemplazados. Esto le permite simular actualizaciones destructivas , sin hacer realmente actualizaciones destructivas. (La Mónada del Estado y su primo el escritor Mónada ).

  • Debido a que solo estás simulando actualizaciones destructivas, puedes hacer trivialmente cosas que serían imposibles con actualizaciones destructivas reales . Por ejemplo, puede deshacer la última actualización o volver a una versión anterior .

  • Puede hacer una mónada donde los cálculos se pueden pausar , por lo que puede pausar su progtwig, acceder y modificar los datos de estado internos, y luego reanudarlo.

  • Puede implementar “continuaciones” como una mónada. ¡Esto te permite romper las mentes de las personas!

Todo esto y más es posible con mónadas. Por supuesto, todo esto también es perfectamente posible sin mónadas también. Simplemente es drásticamente más fácil usar mónadas.

En realidad, contrariamente a la comprensión común de las Mónadas, no tienen nada que ver con el estado. Las mónadas son simplemente una forma de envolver cosas y proporcionar métodos para realizar operaciones sobre las cosas envueltas sin desenvolverlas.

Por ejemplo, puede crear un tipo para ajustar otro, en Haskell:

 data Wrapped a = Wrap a 

Para envolver cosas definimos

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

Para realizar operaciones sin desenvolver, digamos que tiene una función f :: a -> b , puede hacer esto para levantar esa función y actuar sobre los valores envueltos:

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

Eso es todo lo que hay para entender. Sin embargo, resulta que hay una función más general para hacer este levantamiento , que es bind :

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

bind puede hacer un poco más que fmap , pero no al revés. En realidad, fmap se puede definir solo en términos de bind y return . Entonces, cuando se define una mónada … se da su tipo (aquí estaba Wrapped a ) y luego se dice cómo funcionan sus operaciones de return y bind .

Lo bueno es que esto resulta ser un patrón tan general que aparece por todos lados, encapsular el estado de una manera pura es solo uno de ellos.

Para un buen artículo sobre cómo las mónadas se pueden utilizar para introducir dependencias funcionales y, por lo tanto, controlar el orden de la evaluación, como se usa en la mónada IO de Haskell, consulte IO Inside .

En cuanto a la comprensión de las mónadas, no te preocupes demasiado por eso. Lea sobre ellos lo que le parezca interesante y no se preocupe si no comprende de inmediato. Entonces solo bucear en un idioma como Haskell es el camino a seguir. Las mónadas son una de estas cosas en las que la comprensión se cuela en tu cerebro mediante la práctica; un día, de repente te das cuenta de que las entiendes.

Pero, ¡podrías haber inventado Mónadas!

Sigfpe dice:

Pero todos estos introducen las mónadas como algo esotérico que necesita explicación. Pero lo que quiero decir es que no son esotéricos en absoluto. De hecho, frente a varios problemas en la progtwigción funcional, usted habría sido conducido, inexorablemente, a ciertas soluciones, todas las cuales son ejemplos de mónadas. De hecho, espero conseguirte que los inventes ahora si aún no lo hiciste. Es entonces un pequeño paso darse cuenta de que todas estas soluciones son, de hecho, la misma solución disfrazada. Y después de leer esto, es posible que esté en una mejor posición para comprender otros documentos sobre mónadas porque reconocerá todo lo que ve como algo que ya ha inventado.

Muchos de los problemas que las mónadas intentan resolver están relacionados con el tema de los efectos secundarios. Entonces comenzaremos con ellos. (Tenga en cuenta que las mónadas le permiten hacer algo más que manejar los efectos secundarios, en particular, muchos tipos de objetos contenedores pueden verse como mónadas. Algunas de las introducciones a las mónadas encuentran difícil conciliar estos dos usos diferentes de las mónadas y concentrarse en solo uno o el otro.)

En un lenguaje de progtwigción imperativo como C ++, las funciones no se comportan como las funciones de las matemáticas. Por ejemplo, supongamos que tenemos una función de C ++ que toma un único argumento de coma flotante y devuelve un resultado de punto flotante. Superficialmente, puede parecer un poco como una función matemática mapeando reales a reales, pero una función de C ++ puede hacer más que simplemente devolver un número que depende de sus argumentos. Puede leer y escribir los valores de variables globales, así como escribir resultados en la pantalla y recibir información del usuario. En un lenguaje funcional puro, sin embargo, una función solo puede leer lo que se le proporciona en sus argumentos y la única forma en que puede tener un efecto en el mundo es a través de los valores que devuelve.

Una mónada es un tipo de datos que tiene dos operaciones: >>= (aka bind ) y return (aka unit ). return toma un valor arbitrario y crea una instancia de la mónada con él. >>= toma una instancia de la mónada y mapea una función sobre ella. (Ya puede ver que una mónada es un tipo extraño de tipo de datos, ya que en la mayoría de los lenguajes de progtwigción no se puede escribir una función que tome un valor arbitrario y se cree un tipo.) Las mónadas usan un tipo de polymorphism paramétrico ).

En la notación Haskell, la interfaz de la mónada está escrita

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

Se supone que estas operaciones obedecen a ciertas “leyes”, pero eso no es terriblemente importante: las “leyes” simplemente codifican la forma en que deben comportarse las implementaciones sensatas de las operaciones (básicamente, que >>= y el return deben estar de acuerdo sobre cómo se transforman los valores en instancias de mónada y que >>= es asociativo).

Las mónadas no son solo acerca del estado y la E / S: resumen un patrón común de computación que incluye trabajar con estado, E / S, excepciones y no determinismo. Probablemente las mónadas más simples de entender sean listas y tipos de opciones:

 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 

donde [] y : son los constructores de listas, ++ es el operador de concatenación, y Just y Nothing son los constructores Maybe . Ambas mónadas encapsulan patrones comunes y útiles de computación en sus respectivos tipos de datos (tenga en cuenta que ninguno de los dos tiene nada que ver con efectos secundarios o E / S).

Realmente tienes que jugar a escribir un código Haskell no trivial para apreciar de qué mónadas se trata y por qué son útiles.

Primero debes entender qué es un functor. Antes de eso, entiende las funciones de orden superior.

Una función de orden superior es simplemente una función que toma una función como argumento.

Un funtor es cualquier construcción de tipo T para la cual existe una función de orden superior, llamada map , que transforma una función de tipo a -> b (dados dos tipos a y b ) en una función T a -> T b . Esta función de map también debe obedecer las leyes de identidad y composición de manera que las siguientes expresiones devuelvan verdadero para todos los p y q (notación Haskell):

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

Por ejemplo, un constructor de tipos llamado List es un funtor si viene equipado con una función de tipo (a -> b) -> List a -> List b que obedece a las leyes anteriores. La única implementación práctica es obvia. La función List a -> List b resultante itera sobre la lista dada, invocando la función (a -> b) para cada elemento y devuelve la lista de resultados.

Una mónada es esencialmente solo un functor T con dos métodos extra, join , de tipo T (T a) -> T a , y unit (a veces llamada return , fork o pure ) de tipo a -> T a . Para listas en Haskell:

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

¿Por qué es eso útil? Porque podría, por ejemplo, map una lista con una función que devuelve una lista. Join toma la lista resultante de listas y las concatena. List es una mónada porque esto es posible.

Puede escribir una función que se map , luego se join . Esta función se llama bind , o flatMap , o (>>=) , o (=<<) . Esta es normalmente la forma en que se da una instancia de mónada en Haskell.

Una mónada tiene que cumplir ciertas leyes, a saber, que la join debe ser asociativa. Esto significa que si tiene un valor x de tipo [[[a]]] entonces join (join x) debe ser igual a join (map join x) . Y pure debe ser una identidad para join tal que join (pure x) == x .

[Descargo de responsabilidad: todavía estoy tratando de asimilar completamente las mónadas. Lo siguiente es exactamente lo que he entendido hasta ahora. Si está mal, con suerte alguien con conocimiento me llamará por la alfombra.]

Arnar escribió:

Las mónadas son simplemente una forma de envolver cosas y proporcionar métodos para realizar operaciones sobre las cosas envueltas sin desenvolverlas.

Eso es precisamente eso. La idea es así:

  1. Tomas algún tipo de valor y lo envuelves con información adicional. Al igual que el valor es de cierto tipo (por ejemplo, un entero o una cadena), la información adicional es de cierto tipo.

    Por ejemplo, esa información adicional podría ser un Maybe o un IO .

  2. Luego tiene algunos operadores que le permiten operar con los datos envueltos mientras lleva esa información adicional. Estos operadores usan la información adicional para decidir cómo cambiar el comportamiento de la operación en el valor envuelto.

    Por ejemplo, un Maybe Int puede ser un Just Int o Nothing . Ahora, si agrega un Maybe Int a Maybe Int , el operador verificará si ambos están dentro de Just Int ., Y si es así, desenvolverá el Int , les pasará el operador de sum, volverá a envolver el Int resultante. en un nuevo Just Int (que es un Maybe Int válido), y así devolver un Maybe Int . Pero si uno de ellos era Nothing , este operador simplemente devolverá Nothing , que nuevamente es un Maybe Int válido. De esta manera, puede pretender que sus Maybe Int s son solo números normales y realizar operaciones matemáticas regulares sobre ellos. Si obtuvieras un Nothing , tus ecuaciones seguirán produciendo el resultado correcto, sin tener que tirar basura por Nothing todas partes .

Pero el ejemplo es exactamente lo que sucede para Maybe . Si la información adicional fuera un IO , se llamaría entonces a ese operador especial definido para IO , y podría hacer algo totalmente diferente antes de realizar la adición. (OK, agregar dos IO Int juntos probablemente sea absurdo, todavía no estoy seguro). (Además, si prestaste atención al ejemplo Maybe , habrás notado que “ajustar un valor con cosas adicionales” no siempre es correcto. Pero es difícil ser exacto, correcto y preciso sin ser inescrutable).

Básicamente, “mónada” aproximadamente significa “patrón” . Pero en lugar de un libro lleno de patrones informalmente explicados y específicamente denominados, ahora tiene una construcción de lenguaje (syntax y todo) que le permite declarar nuevos patrones como cosas en su progtwig . (La imprecisión aquí es que todos los patrones tienen que seguir una forma particular, por lo que una mónada no es tan genérica como un patrón. Pero creo que ese es el término más cercano que la mayoría de la gente conoce y entiende).

Y es por eso que las personas encuentran las mónadas tan confusas: porque son un concepto tan genérico. Preguntar qué hace que algo sea una mónada es igualmente vago que preguntar qué hace que algo sea un patrón.

Pero piense en las implicaciones de tener soporte sintáctico en el lenguaje para la idea de un patrón: en lugar de tener que leer el libro de la Banda de los Cuatro y memorizar la construcción de un patrón particular, usted simplemente escribe el código que implementa este patrón en un agnóstico, forma genérica una vez y luego has terminado! A continuación, puede reutilizar este patrón, como Visitor, Strategy o Faade o lo que sea, simplemente decorando las operaciones en su código con él, ¡sin tener que volver a implementarlo una y otra vez!

Es por eso que las personas que entienden las mónadas las encuentran tan útiles : no es un concepto de torre de marfil que los esnobs intelectuales se enorgullezcan de comprender (OK, eso también, por supuesto, teehee), pero en realidad hace que el código sea más simple.

Después de mucho esfuerzo, creo que finalmente entiendo la mónada. Después de releer mi propia y larga crítica de la abrumadora respuesta más votado, ofreceré esta explicación.

Hay tres preguntas que deben ser respondidas para comprender las mónadas:

  1. ¿Por qué necesitas una mónada?
  2. ¿Qué es una mónada?
  3. ¿Cómo se implementa una mónada?

Como noté en mis comentarios originales, demasiadas explicaciones de mónadas quedan atrapadas en la pregunta número 3, sin, y antes de cubrir adecuadamente la pregunta 2 o la pregunta 1.

¿Por qué necesitas una mónada?

Los lenguajes funcionales puros como Haskell son diferentes de los lenguajes imperativos como C, o Java en eso, un progtwig funcional puro no necesariamente se ejecuta en un orden específico, un paso a la vez. Un progtwig Haskell es más parecido a una función matemática, en la cual puedes resolver la “ecuación” en cualquier cantidad de órdenes potenciales. Esto confiere una serie de beneficios, entre los que se encuentra que elimina la posibilidad de ciertos tipos de errores, particularmente aquellos relacionados con cosas como “estado”.

Sin embargo, hay ciertos problemas que no son tan fáciles de resolver con este estilo de progtwigción. Algunas cosas, como la progtwigción de la consola y el archivo de E / S, necesitan que las cosas sucedan en un orden particular o que necesiten mantener el estado. Una forma de resolver este problema es crear un tipo de objeto que represente el estado de un cálculo y una serie de funciones que toman un objeto de estado como entrada y devuelvan un nuevo objeto de estado modificado.

Así que creemos un valor hipotético de “estado”, que represente el estado de una pantalla de consola. exactamente cómo se construye este valor no es importante, pero digamos que es una matriz de caracteres ascii de bytes que representa lo que está actualmente visible en la pantalla, y una matriz que representa la última línea de entrada ingresada por el usuario, en pseudocódigo. Hemos definido algunas funciones que toman el estado de la consola, lo modifican y devuelven un nuevo estado de consola.

 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:

Comencemos con lo obvio. 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-trivial 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 restrictions on what they can do (see the definiton for details).
  2. Those restrictions, 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 branches 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 string 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.

¿Por qué molestarse?

Monads allow for strictly 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 matriculation 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 . Cerrado
  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 distributed evaluation as used by Google’s distributed 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.

Compilers 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 string 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 Patrick 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 tries.

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 compiler 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 compile 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 compile. 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 trivial, 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 trivial 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 } } 

P.ej

 // These could be any functions val f: Int => Option[String] = number => if (number == 7) Some("hello") else None val g: String => Option[Double] = string => 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 Strictly 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 string 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 strings, 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 string”. 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 string. An M string is a pair of a string and a string. 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

    es lo mismo que

    • 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 triangle, the only fractal I can remember to draw. Fractals are self-similar structure like the above triangle, in which the parts are similar to the whole (in this case exactly half the scale as parent triangle).

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 -> String and f :: String -> 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 String type represents a String value that is there as a result of performing some side effects.)

Let’s say we now have g1 :: Int -> Maybe String and f1 :: String -> 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 

Prólogo

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 triple

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 triple 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.

Identidad

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 

Opción

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 

Lista

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`) 

entonces

 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 :: String -> 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) 

dónde

 (&) :: 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 

Si en

 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.

Estado

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) 

o

 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 strict implementation:

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

Interaction is facilitated by impure primitives

 getChar :: IO Char putChar :: Char -> IO () readFile :: FilePath -> IO String writeFile :: FilePath -> String -> 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!" 

se expande a

 World -> ((), World) 

A function that transforms a world.

Epílogo

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 triple

  

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 triple 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.