O que é uma mônada?

Tendo olhado brevemente para Haskell recentemente, o que seria uma explicação breve, sucinta e prática sobre o que uma mônada é essencialmente?

Eu encontrei a maioria das explicações que eu encontrei para ser bastante inacessível e sem detalhes práticos.

Primeiro: O termo mônada é um pouco vazio se você não é um matemático. Um termo alternativo é o construtor de computação, que é um pouco mais descritivo do que eles são realmente úteis.

Você pede exemplos práticos:

Exemplo 1: Compreensão da lista :

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

Esta expressão retorna as duplas de todos os números ímpares no intervalo de 1 a 10. Muito útil!

Acontece que este é realmente apenas açúcar sintático para algumas operações dentro da lista Mônada. A mesma compreensão da lista pode ser escrita como:

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

Ou até mesmo:

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

Exemplo 2: Entrada / Saída :

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

Ambos os exemplos usam monads, construtores de computação AKA. O tema comum é que a mônada encadeia as operações de alguma maneira específica e útil. Na compreensão da lista, as operações são encadeadas de forma que, se uma operação retornar uma lista, as operações a seguir serão executadas em todos os itens da lista. A mona IO, por outro lado, executa as operações sequencialmente, mas transmite uma "variável oculta", que representa "o estado do mundo", o que nos permite escrever código de E / S de maneira funcional pura.

Acontece que o padrão de operações de encadeamento é bastante útil e é usado para muitas coisas diferentes em Haskell.

Outro exemplo é exceções: Usando o Error monad, as operações são encadeadas de forma que sejam executadas sequencialmente, exceto se um erro for lançado, caso em que o restante da cadeia será abandonado.

Tanto a syntax de compreensão de lista como a notação de doação são açúcar sintático para operações de encadeamento usando o operador >>= . Uma mônada é basicamente apenas um tipo que suporta o operador >>= .

Exemplo 3: um analisador

Este é um analisador muito simples que analisa uma string entre aspas ou um número:

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

As operações char , digit , etc. são bem simples. Eles combinam ou não combinam. A mágica é a mônada que gerencia o stream de controle: As operações são realizadas sequencialmente até que uma correspondência falhe, caso em que a mônada volta ao último < |> e tenta a próxima opção. Novamente, uma maneira de encadear operações com alguma semântica adicional e útil.

Exemplo 4: programação assíncrona

Os exemplos acima estão em Haskell, mas também F # também suporta monads. Este exemplo é roubado 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 uma página da web. O punch line é o uso de GetResponseAsync - ele realmente aguarda a resposta em um thread separado, enquanto o thread principal retorna da function. As últimas três linhas são executadas no thread gerado quando a resposta foi recebida.

Na maioria das outras linguagens, você teria que criar explicitamente uma function separada para as linhas que lidam com a resposta. A mônada async é capaz de "dividir" o bloco por conta própria e adiar a execução da segunda metade. (A syntax async {} indica que o stream de controle no bloco é definido pela mônada async .)

Como eles trabalham

Então, como pode uma mônada fazer todas essas coisas extravagantes de stream de controle? O que realmente acontece em um do-block (ou uma expressão de computação, como são chamados em F #), é que toda operação (basicamente toda linha) é envolvida em uma function anônima separada. Essas funções são então combinadas usando o operador bind (escrito >>= em Haskell). Como a operação de bind combina funções, ela pode executá-las como achar melhor: sequencialmente, várias vezes, ao contrário, descartar algumas, executar algumas em um thread separado quando tiver a sensação e assim por diante.

Por exemplo, esta é a versão expandida do código IO do exemplo 2:

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

Isso é mais feio, mas também é mais óbvio o que está realmente acontecendo. O operador >>= é o ingrediente mágico: ele pega um valor (no lado esquerdo) e combina-o com uma function (no lado direito), para produzir um novo valor. Este novo valor é então obtido pelo próximo operador >>= e novamente combinado com uma function para produzir um novo valor. >>= pode ser visto como um mini-avaliador.

Note que >>= está sobrecarregado para diferentes tipos, então cada mônada tem sua própria implementação de >>= . (Todas as operações na cadeia têm que ser do mesmo tipo de mônada, caso contrário, o operador >>= não funcionará.)

A implementação mais simples possível de >>= apenas pega o valor à esquerda e aplica-o à function à direita e retorna o resultado, mas como dito anteriormente, o que torna todo o padrão útil é quando há algo extra acontecendo no implementação da monad de >>= .

Há alguma inteligência adicional em como os valores são passados ​​de uma operação para a próxima, mas isso requer uma explicação mais profunda do sistema do tipo Haskell.

Resumindo

Em termos de Haskell, uma mônada é um tipo parametrizado, que é uma instância da class de tipo Monad, que define >>= junto com alguns outros operadores. Em termos leigos, uma mônada é apenas um tipo para o qual a operação >>= é definida.

Em si >>= é apenas uma maneira complicada de encadear funções, mas com a presença da notação que oculta o "encanamento", as operações monádicas revelam-se uma abstração muito agradável e útil, útil em muitos lugares na linguagem e útil para criar suas próprias mini-linguagens no idioma.

Por que as mônadas são difíceis?

Para muitos alunos de Haskell, as mônadas são um obstáculo que atingem como uma parede de tijolos. Não é que as próprias monads sejam complexas, mas a implementação depende de muitos outros resources avançados do Haskell, como tipos parametrizados, classs de tipos e assim por diante. O problema é que o Haskell I / O é baseado em monads, e o I / O é provavelmente uma das primeiras coisas que você quer entender quando aprende um novo idioma - afinal, não é muito divertido criar programas que não produzem nada. saída. Não tenho solução imediata para esse problema de galinha e ovo, exceto tratar E / S como "mágica acontece aqui" até que você tenha experiência suficiente com outras partes da linguagem. Desculpa.

Excelente blog em monads: http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

Explicar “o que é uma mônada” é como dizer “o que é um número?” Nós usamos números o tempo todo. Mas imagine que você conheceu alguém que não sabia nada sobre números. Como diabos você explicaria quais são os números? E como você poderia começar a descrever por que isso poderia ser útil?

O que é uma mônada? A resposta curta: é uma maneira específica de encadear operações.

Em essência, você está escrevendo etapas de execução e vinculando-as com a “function bind”. (No Haskell, é chamado >>= .) Você pode escrever as chamadas para o operador de binding você mesmo, ou você pode usar o açúcar de syntax que faz o compilador inserir essas chamadas de function para você. Mas de qualquer forma, cada etapa é separada por uma chamada para essa function de binding.

Então a function bind é como um ponto-e-vírgula; separa as etapas de um processo. O trabalho da function bind é pegar a saída da etapa anterior e alimentá-la na próxima etapa.

Isso não parece muito difícil, certo? Mas há mais de um tipo de mônada. Por quê? Como?

Bem, a function bind pode apenas pegar o resultado de um passo e alimentá-lo para o próximo passo. Mas se isso é “tudo” que a mônada faz … isso na verdade não é muito útil. E isso é importante para entender: Toda mônada útil faz outra coisa além de ser apenas uma mônada. Toda mônada útil tem um “poder especial”, o que a torna única.

(Uma mônada que não faz nada de especial é chamada de “mônada da identidade”. Assim como a function da identidade, isso soa como uma coisa totalmente sem sentido, ainda que não seja … Mas essa é outra história.)

Basicamente, cada mônada tem sua própria implementação da function bind. E você pode escrever uma function de binding de tal forma que ela hoopy coisas entre as etapas de execução. Por exemplo:

  • Se cada etapa retornar um indicador de sucesso / falha, você poderá fazer com que a binding execute a próxima etapa apenas se a anterior tiver êxito. Desta forma, um passo em falha aborta toda a sequência “automaticamente”, sem qualquer teste condicional de você. (A Mônada do Fracasso )

  • Estendendo essa ideia, você pode implementar “exceções”. (The Monad Error ou Exception Monad .) Porque você está definindo-os você mesmo ao invés de ser um recurso de linguagem, você pode definir como eles funcionam. (Por exemplo, talvez você queira ignorar as duas primeiras exceções e apenas abortar quando uma terceira exceção for lançada.)

  • Você pode fazer com que cada etapa retorne vários resultados e fazer com que a function de binding faça um loop sobre eles, alimentando cada um deles na próxima etapa para você. Dessa forma, você não precisa continuar escrevendo loops por todo o lugar ao lidar com vários resultados. A function de binding “automaticamente” faz tudo isso para você. (The List Monad .)

  • Além de passar um “resultado” de um passo para o outro, você também pode fazer com que a function bind passe dados extras . Esses dados agora não aparecem no código-fonte, mas você ainda pode acessá-los de qualquer lugar, sem ter que passá-los manualmente para todas as funções. (The Reader Monad .)

  • Você pode fazer com que os “dados extras” possam ser substituídos. Isso permite que você simule atualizações destrutivas , sem fazer atualizações destrutivas. (A Mônada do Estado e sua prima, a escritora Monad .)

  • Porque você está apenas simulando atualizações destrutivas, você pode fazer trivialmente coisas que seriam impossíveis com atualizações destrutivas reais . Por exemplo, você pode desfazer a última atualização ou reverter para uma versão mais antiga .

  • Você pode fazer uma mônada onde os cálculos podem ser pausados , para que você possa pausar seu programa, entrar e mexer nos dados do estado interno e, em seguida, retomá-lo.

  • Você pode implementar “continuações” como uma mônada. Isso permite que você quebre a mente das pessoas!

Tudo isso e muito mais é possível com as mônadas. Claro, tudo isso também é perfeitamente possível sem as mônadas. É simplesmente mais fácil usar mônadas.

Na verdade, ao contrário do entendimento comum das Mônadas, elas não têm nada a ver com o estado. As mônadas são simplesmente uma maneira de envolver as coisas e fornecer methods para fazer operações no material embrulhado sem desdobrá-lo.

Por exemplo, você pode criar um tipo para envolver outro, em Haskell:

 data Wrapped a = Wrap a 

Para embrulhar coisas que definimos

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

Para executar operações sem desembrulhar, digamos que você tenha uma function f :: a -> b , então você pode fazer isso para levantar essa function para atuar em valores agrupados:

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

Isso é tudo o que há para entender. No entanto, verifica-se que há uma function mais geral para fazer esse levantamento , que é bind :

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

bind pode fazer um pouco mais que fmap , mas não vice-versa. Na verdade, o fmap pode ser definido apenas em termos de bind e return . Então, quando definimos uma mônada … você dá o seu tipo (aqui foi Wrapped a ) e então diz como suas operações de return e bind funcionam.

O legal é que esse é um padrão geral que aparece em todos os lugares, encapsulando o estado de forma pura é apenas um deles.

Para um bom artigo sobre como as mônadas podem ser usadas para introduzir dependencies funcionais e, assim, controlar a ordem de avaliação, como é usado na IO m de Haskell, confira IO Inside .

Quanto à compreensão de mônadas, não se preocupe muito com isso. Leia sobre o que você acha interessante e não se preocupe se você não entender imediatamente. Então apenas mergulhar em uma linguagem como Haskell é o caminho a percorrer. As mônadas são uma dessas coisas em que a compreensão escorre para o seu cérebro pela prática, um dia você percebe que as entende.

Mas você poderia ter inventado o Monads!

sigfpe diz:

Mas todos eles introduzem as mônadas como algo esotérico que precisa de explicação. Mas o que eu quero argumentar é que eles não são esotéricos. De fato, diante de vários problemas na functional programming, você teria sido levado, inexoravelmente, a certas soluções, todas exemplos de mônadas. Na verdade, espero que você invente-os agora, se ainda não o fez. É então um pequeno passo para perceber que todas essas soluções são, na verdade, a mesma solução disfarçada. E depois de ler isto, você pode estar em uma posição melhor para entender outros documentos sobre mônadas, porque você reconhecerá tudo que você vê como algo que você já inventou.

Muitos dos problemas que as mônadas tentam resolver estão relacionados à questão dos efeitos colaterais. Então vamos começar com eles. (Note que as mônadas permitem fazer mais do que lidar com efeitos colaterais, em particular muitos tipos de objects contêineres podem ser vistos como mônadas. Algumas das introduções a mônadas acham difícil conciliar esses dois usos diferentes de mônadas e se concentram em apenas um ou o outro.)

Em uma linguagem de programação imperativa, como C ++, as funções não se comportam como as funções da matemática. Por exemplo, suponha que tenhamos uma function C ++ que use um único argumento de ponto flutuante e retorne um resultado de ponto flutuante. Superficialmente, pode parecer um pouco com uma function matemática mapeando reais para reais, mas uma function C ++ pode fazer mais do que apenas retornar um número que depende de seus argumentos. Ele pode ler e gravar os valores das variables ​​globais, bem como gravar saída na canvas e receber input do usuário. Em uma linguagem funcional pura, no entanto, uma function só pode ler o que é fornecido a ela em seus argumentos e a única maneira de ter um efeito no mundo é através dos valores que ela retorna.

Uma monad é um tipo de dados que possui duas operações: >>= (aka bind ) e return ( unit aka). return recebe um valor arbitrário e cria uma instância da mônada com ele. >>= pega uma instância da mônada e mapeia uma function sobre ela. (Você já pode ver que uma mônada é um tipo estranho de dados, já que na maioria das linguagens de programação você não poderia escrever uma function que toma um valor arbitrário e cria um tipo a partir dela. As mônadas usam um tipo de polymorphism paramétrico .)

Na notação de Haskell, a interface da mônada é escrita

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

Essas operações devem obedecer a certas “leis”, mas isso não é muito importante: as “leis” apenas codificam a maneira pela qual as implementações sensatas das operações devem se comportar (basicamente, isso e return devem concordar sobre como os valores se transformam em instâncias monad e que >>= é associativo).

As mônadas não são apenas sobre estado e E / S: elas abstraem um padrão comum de computação que inclui trabalhar com estado, E / S, exceções e não-determinismo. Provavelmente, as mônadas mais simples de entender são listas e tipos de opções:

 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 

onde [] e : são os construtores da lista, ++ é o operador de concatenação e Just e Nothing são os construtores Maybe . Ambas as mônadas encapsulam padrões comuns e úteis de computação em seus respectivos tipos de dados (note que nenhum deles tem nada a ver com efeitos colaterais ou E / S).

Você realmente tem que brincar escrevendo algum código não-trivial de Haskell para apreciar o que são as mônadas e por que elas são úteis.

Você deve primeiro entender o que é um functor. Antes disso, entenda funções de ordem superior.

Uma function de ordem superior é simplesmente uma function que usa uma function como argumento.

Um funtor é qualquer construção de tipo T para a qual existe uma function de ordem superior, chamada de map , que transforma uma function do tipo a -> b (dados quaisquer dois tipos a e b ) em uma function T a -> T b . Esta function de map também deve obedecer às leis de identidade e composição, de modo que as seguintes expressões retornem verdadeiro para todos os q (notação de Haskell):

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

Por exemplo, um construtor de tipos chamado List é um functor se vier equipado com uma function do tipo (a -> b) -> List a -> List b que obedece às leis acima. A única implementação prática é óbvia. A function List a -> List b resultante itera sobre a lista dada, chamando a function (a -> b) para cada elemento e retorna a lista dos resultados.

Uma mônada é essencialmente apenas um functor T com dois methods extras, join , do tipo T (T a) -> T a , e unit (às vezes chamado de return , fork ou pure ) do tipo a -> T a . Para listas em Haskell:

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

Por que isso é útil? Porque você poderia, por exemplo, map uma lista com uma function que retorna uma lista. Join pega a lista de listas resultante e concatena-as. List é uma mônada porque isso é possível.

Você pode escrever uma function que map , depois joinjoin . Essa function é chamada de bind ou flatMap , ou (>>=) ou (=< <) . Isto é normalmente como uma instância monad é dada em Haskell.

Uma mônada tem que satisfazer certas leis, a saber, que a join deve ser associativa. Isto significa que se você tem um valor x do tipo [[[a]]] então join (join x) deve ser igual a join (map join x) . E pure deve ser uma identidade para join tal que join (pure x) == x .

[Disclaimer: Eu ainda estou tentando completar completamente as mônadas. O seguinte é apenas o que eu entendi até agora. Se estiver errado, espero que alguém bem informado me ligue no tapete.]

Arnar escreveu:

As mônadas são simplesmente uma maneira de envolver as coisas e fornecer methods para fazer operações no material embrulhado sem desdobrá-lo.

É precisamente isso. A ideia é assim:

  1. Você pega algum tipo de valor e o envolve com algumas informações adicionais. Assim como o valor é de um certo tipo (por exemplo, um inteiro ou uma string), as informações adicionais são de um certo tipo.

    Por exemplo, essa informação extra pode ser um Maybe ou um IO .

  2. Então você tem alguns operadores que permitem que você opere nos dados envolvidos enquanto transporta essas informações adicionais. Esses operadores usam as informações adicionais para decidir como alterar o comportamento da operação no valor empacotado.

    Por exemplo, um Maybe Int pode ser um Just Int ou Nothing . Agora, se você adicionar um Maybe Int a um Maybe Int , o operador verificará se ambos são Just Int ‘s internos e, em caso afirmativo, desembrulhará os Int s, passará o operador de adição, re-wrap o Int resultante em um novo Just Int (que é um válido Maybe Int ), e assim retornar um Maybe Int . Mas se um deles for um Nothing interno, este operador retornará imediatamente Nothing , que novamente é um válido Maybe Int . Dessa forma, você pode fingir que os seus ” Maybe Int são apenas números normais e realizar cálculos regulares neles. Se você obtivesse um Nothing , suas equações ainda produziriam o resultado correto – sem você ter que colocar cheques para Nothing todo lugar .

Mas o exemplo é o que acontece para o Maybe . Se a informação extra fosse um IO , então aquele operador especial definido para IO seria chamado, e poderia fazer algo totalmente diferente antes de realizar a adição. (OK, adicionar dois IO Int juntos é provavelmente sem sentido – ainda não tenho certeza.) (Além disso, se você prestou atenção ao exemplo de Maybe , você notou que “envolver um valor com material extra” nem sempre está correto). Mas é difícil ser exato, correto e preciso sem ser inescrutável.)

Basicamente, “mônada” significa aproximadamente “padrão” . Mas em vez de um livro cheio de Patterns explicados informalmente e especificamente chamados, agora você tem uma construção de linguagem – syntax e tudo – que permite a você declarar novos padrões como coisas em seu programa . (A imprecisão aqui é que todos os padrões têm que seguir uma forma particular, então uma mônada não é tão genérica quanto um padrão. Mas eu acho que é o termo mais próximo que a maioria das pessoas conhece e compreende.)

E é por isso que as pessoas acham as mônadas tão confusas: porque são um conceito tão genérico. Perguntar o que faz de algo uma mônada é igualmente vaga a ponto de perguntar o que faz de algo um padrão.

Mas pense nas implicações de ter suporte sintático na linguagem para a idéia de um padrão: em vez de ter que ler o livro da Gangue dos Quatro e memorizar a construção de um padrão específico, você apenas escreve um código que implementa esse padrão em um agnóstico, maneira genérica uma vez e então você está feito! Você pode então reutilizar esse padrão, como Visitante ou Estratégia ou Fachada ou qualquer outra coisa, simplesmente decorando as operações em seu código com ele, sem ter que reimplementá-lo várias vezes!

É por isso que as pessoas que entendem as mônadas as acham tão úteis : não é um conceito de torre de marfim que os intelectuais se orgulham de entender (ok, isso também, é claro, de cabeça), mas na verdade torna o código mais simples.

Depois de muito esforço, acho que finalmente entendi a mônada. Depois de reler minha longa crítica à esmagadora maioria das respostas votadas, vou oferecer essa explicação.

Há três perguntas que precisam ser respondidas para entender as mônadas:

  1. Por que você precisa de uma mônada?
  2. O que é uma mônada?
  3. Como uma mônada é implementada?

Como observei em meus comentários originais, muitas explicações de mônadas são pegas na questão número 3, sem antes, e antes de realmente abordar adequadamente a questão 2, ou a questão 1.

Por que você precisa de uma mônada?

Linguagens funcionais puras como Haskell são diferentes de linguagens imperativas como C, ou Java, em que um programa funcional puro não é necessariamente executado em uma ordem específica, um passo de cada vez. Um programa Haskell é mais parecido com uma function matemática, na qual você pode resolver a “equação” em qualquer número de pedidos em potencial. Isso confere uma série de benefícios, entre os quais é que elimina a possibilidade de certos tipos de bugs, particularmente aqueles relacionados a coisas como “estado”.

No entanto, existem certos problemas que não são tão fáceis de resolver com este estilo de programação. Algumas coisas, como a programação de console e o file i / o, precisam que as coisas aconteçam em uma ordem específica ou precisam manter o estado. Uma maneira de lidar com esse problema é criar um tipo de object que representa o estado de uma computação e uma série de funções que tomam um object de estado como input e retornam um novo object de estado modificado.

Então, vamos criar um valor hipotético de “estado”, que representa o estado de uma canvas de console. exatamente como esse valor é construído não é importante, mas digamos que é uma matriz de caracteres ascii de comprimento de byte que representa o que está atualmente visível na canvas e uma matriz que representa a última linha de input inserida pelo usuário, em pseudocódigo. Definimos algumas funções que levam o estado do console, modificam e retornam um novo estado do console.

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

Porque se importar?

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 . Fechadas
  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 classs 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 triggerste 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 classs, 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 } } 

Por exemplo

 // 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

    é o mesmo 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.

Identity

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 

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

então

 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) 

Onde

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

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) 

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 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!" 

expands to

 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.