Por que precisamos de mônadas?

Na minha humilde opinião, as respostas à famosa pergunta "O que é uma mônada?" , especialmente os mais votados, tente explicar o que é uma mônada sem explicar claramente por que as mônadas são realmente necessárias . Eles podem ser explicados como a solução para um problema?

Por que precisamos de mônadas?

1. Queremos programar apenas usando funções . ("programação funcional (FP)" afinal).

2. Então, nós temos um primeiro grande problema. Este é um programa:

   f(x) = 2 * x

   g(x,y) = x / y

   Como podemos dizer o que deve ser executado primeiro ? Como podemos formar uma sequência ordenada de funções (isto é, um programa ) usando não mais que funções ?

   Solução: compor funções . Se você quiser primeiro ge depois f, basta escrever f(g(x,y)). Desta forma, "o programa" é uma função bem: main = f(g(x,y)). OK mas ...

3. Mais problemas: algumas funções podem falhar (ou seja g(2,0), dividir por 0). Não temos "exceções" no FP (uma exceção não é uma função). Como resolvemos isso?

   Solução: Vamos permitir que as funções retornem dois tipos de coisas : em vez de ter g : Real,Real -> Real(função de dois reais em um real), vamos permitir g : Real,Real -> Real | Nothing(função de dois reais em (real ou nada)).

4. Mas as funções devem (para ser mais simples) retornar apenas uma coisa .

   Solução: vamos criar um novo tipo de dados a serem retornados, um " tipo de boxe " que encerra talvez um real ou seja simplesmente nada. Por isso, podemos ter g : Real,Real -> Maybe Real. OK mas ...

5. O que acontece agora f(g(x,y))? fnão está pronto para consumir a Maybe Real. E não queremos alterar todas as funções com as quais podemos nos conectar gpara consumir a Maybe Real.

   Solução: vamos ter uma função especial para "conectar" / "compor" / "vincular" funções . Dessa forma, podemos, nos bastidores, adaptar a saída de uma função para alimentar a seguinte.

   No nosso caso: g >>= f(conectar / compor gpara f). Queremos >>=obter ga produção, inspecioná-la e, no caso de Nothingsimplesmente não ligar fe retornar Nothing; ou, pelo contrário, extraia a caixa Reale alimente fcom ela. (Este algoritmo é apenas a implementação de >>=para o Maybetipo). Observe também que >>=deve ser escrito apenas uma vez por "tipo de boxe" (caixa diferente, algoritmo de adaptação diferente).

6. Surgem muitos outros problemas que podem ser resolvidos usando esse mesmo padrão: 1. Use uma "caixa" para codificar / armazenar diferentes significados / valores e tenha funções como gessa que retornam esses "valores em caixa". 2. Tenha um compositor / vinculador g >>= fpara ajudar a conectar ga saída fda entrada da entrada, para que não tenhamos que alterar nenhuma f.

7. Problemas notáveis ​​que podem ser resolvidos usando esta técnica são:

   • tendo um estado global que todas as funções na sequência de funções ("o programa") podem compartilhar: solução StateMonad.

   • Não gostamos de "funções impuras": funções que produzem resultados diferentes para a mesma entrada. Portanto, vamos marcar essas funções, fazendo com que elas retornem um valor marcado / em caixa: IOmônada.

Felicidade total!

A resposta é, claro, "Nós não" . Como em todas as abstrações, não é necessário.

Haskell não precisa de uma abstração de mônada. Não é necessário executar E / S em um idioma puro. O IOtipo cuida disso muito bem por si só. O Dessacarificação monadic existente de doblocos pode ser substituído com Dessacarificação a bindIO, returnIO, e failIOtal como definido no GHC.Basemódulo. (Não é um módulo documentado sobre hackage, então terei que apontar para sua fonte de documentação.) Portanto, não, não há necessidade da abstração de mônada.

Então, se não é necessário, por que existe? Porque foi descoberto que muitos padrões de computação formam estruturas monádicas. A abstração de uma estrutura permite escrever código que funciona em todas as instâncias dessa estrutura. Para ser mais conciso, reutilize o código.

Nas linguagens funcionais, a ferramenta mais poderosa encontrada para a reutilização de código foi a composição de funções. O bom e velho (.) :: (b -> c) -> (a -> b) -> (a -> c)operador é extremamente poderoso. Torna fácil escrever pequenas funções e colá-las com uma sobrecarga sintática ou semântica mínima.

Mas há casos em que os tipos não funcionam muito bem. O que você faz quando tem foo :: (b -> Maybe c)e bar :: (a -> Maybe b)? foo . barnão verifica, porque be Maybe bnão é do mesmo tipo.

Mas ... está quase certo. Você só quer um pouco de margem de manobra. Você quer ser capaz de tratar Maybe bcomo se fosse basicamente b. No entanto, é uma má idéia tratá-los como do mesmo tipo. Isso é mais ou menos o mesmo que ponteiros nulos, que Tony Hoare chamou de erro de bilhão de dólares . Portanto, se você não puder tratá-los do mesmo tipo, talvez encontre uma maneira de estender o mecanismo de composição (.).

Nesse caso, é importante realmente examinar a teoria subjacente (.). Felizmente, alguém já fez isso por nós. Acontece que a combinação (.)e a idforma de um construto matemático conhecido como categoria . Mas existem outras maneiras de formar categorias. Uma categoria Kleisli, por exemplo, permite que os objetos que estão sendo compostos sejam aumentados um pouco. Uma categoria Kleisli para Maybeconsistiria em (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)e id :: a -> Maybe a. Ou seja, os objetos na categoria aumentam o (->)com a Maybe, assim (a -> b)se tornam (a -> Maybe b).

E de repente, estendemos o poder da composição a coisas nas quais a (.)operação tradicional não funciona. Esta é uma fonte de novo poder de abstração. As categorias Kleisli funcionam com mais tipos do que apenas Maybe. Eles trabalham com todos os tipos que podem montar uma categoria adequada, obedecendo às leis da categoria.

1. Identidade esquerda: id . f=f
2. Identidade correta: f . id=f
3. Associatividade: f . (g . h)=(f . g) . h

Desde que você possa provar que seu tipo obedece a essas três leis, você pode transformá-lo em uma categoria Kleisli. E qual é o problema disso? Bem, acontece que as mônadas são exatamente a mesma coisa que as categorias Kleisli. Monad's returné o mesmo que Kleisli id. Monad's (>>=)não é idêntico ao Kleisli (.), mas acaba por ser muito fácil escrever cada uma em termos da outra. E as leis de categoria são as mesmas que as leis de mônada, quando você as traduz pela diferença entre (>>=)e (.).

Então, por que passar por todo esse incômodo? Por que ter uma Monadabstração no idioma? Como mencionei acima, ele permite a reutilização de código. Ele ainda permite a reutilização de código em duas dimensões diferentes.

A primeira dimensão da reutilização de código vem diretamente da presença da abstração. Você pode escrever um código que funcione em todas as instâncias da abstração. Existe todo o pacote monad-loops que consiste em loops que funcionam com qualquer instância de Monad.

A segunda dimensão é indireta, mas decorre da existência de composição. Quando a composição é fácil, é natural escrever código em pequenos pedaços reutilizáveis. É da mesma maneira que ter o (.)operador para funções incentiva a escrita de funções pequenas e reutilizáveis.

Então, por que a abstração existe? Porque provou ser uma ferramenta que permite mais composição no código, resultando na criação de código reutilizável e incentivando a criação de código mais reutilizável. A reutilização de código é um dos santos grails da programação. A abstração da mônada existe porque nos move um pouco em direção ao Santo Graal.

Benjamin Pierce disse na TAPL

Um sistema de tipos pode ser considerado como calculando um tipo de aproximação estática aos comportamentos em tempo de execução dos termos em um programa.

É por isso que um idioma equipado com um poderoso sistema de tipos é estritamente mais expressivo do que um idioma mal digitado. Você pode pensar em mônadas da mesma maneira.

Como @Carl e ponto sigfpe , você pode equipar um tipo de dados com todas as operações que desejar, sem recorrer a mônadas, classes de tipo ou qualquer outra coisa abstrata. No entanto, as mônadas permitem não apenas escrever código reutilizável, mas também abstrair todos os detalhes redundantes.

Como exemplo, digamos que queremos filtrar uma lista. A maneira mais simples é usar a filterfunção filter (> 3) [1..10]:, que é igual a [4,5,6,7,8,9,10].

Uma versão um pouco mais complicada filter, que também passa um acumulador da esquerda para a direita, é

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

Para obter tudo iisso i <= 10, sum [1..i] > 4, sum [1..i] < 25, podemos escrever

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

o que é igual [3,4,5,6].

Ou podemos redefinir a nubfunção, que remove elementos duplicados de uma lista, em termos de filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

nub' [1,2,4,5,4,3,1,8,9,4]é igual [1,2,4,5,3,8,9]. Uma lista é passada como um acumulador aqui. O código funciona, porque é possível deixar a lista em mônada, para que todo o cálculo permaneça puro ( na verdade notElemnão é usado >>=, mas poderia). No entanto, não é possível sair com segurança da mônada de E / S (ou seja, você não pode executar uma ação de E / S e retornar um valor puro - o valor sempre será envolvido na mônada de E / S). Outro exemplo são matrizes mutáveis: depois de sair da mônada ST, onde uma matriz mutável fica ativa, você não pode mais atualizar a matriz em tempo constante. Então, precisamos de uma filtragem monádica do Control.Monadmódulo:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterMexecuta uma ação monádica para todos os elementos de uma lista, produzindo elementos, para os quais a ação monádica retorna True.

Um exemplo de filtragem com uma matriz:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

imprime [1,2,4,5,3,8,9]conforme o esperado.

E uma versão com a mônada IO, que pergunta quais elementos retornar:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

Por exemplo

return 1? -- output
True      -- input
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- output

E, como ilustração final, filterAccumpode ser definido em termos de filterM:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

com a StateTmônada, usada sob o capô, sendo apenas um tipo de dados comum.

Este exemplo ilustra que as mônadas não apenas permitem abstrair o contexto computacional e escrever código reutilizável limpo (devido à composibilidade das mônadas, como explica @Carl), mas também tratar tipos de dados definidos pelo usuário e primitivas incorporadas de maneira uniforme.

Eu não acho IO deva ser vista como uma mônada particularmente notável, mas certamente é uma das mais surpreendentes para iniciantes, por isso vou usá-la como explicação.

Ingenuamente construindo um sistema de IO para Haskell

O sistema IO mais simples concebível para uma linguagem puramente funcional (e de fato a que Haskell começou) é o seguinte:

main₀ :: String -> String
main₀ _ = "Hello World"

Com a preguiça, essa assinatura simples é suficiente para criar programas de terminal interativos - embora muito limitados. O mais frustrante é que só podemos produzir texto. E se adicionarmos mais possibilidades de produção interessantes?

data Output = TxtOutput String
            | Beep Frequency

main₁ :: String -> [Output]
main₁ _ = [ TxtOutput "Hello World"
          -- , Beep 440  -- for debugging
          ]

bonito, mas é claro que uma "saída alterativa" muito mais realista seria escrita em um arquivo . Mas, então, você também gostaria de ler alguns arquivos. Qualquer chance?

Bem, quando pegamos nosso main₁programa e simplesmente canalizamos um arquivo para o processo (usando recursos do sistema operacional), implementamos essencialmente a leitura de arquivos. Se pudéssemos desencadear essa leitura de arquivos na linguagem Haskell ...

readFile :: Filepath -> (String -> [Output]) -> [Output]

Isso usaria um "programa interativo" String->[Output] , alimentaria uma string obtida de um arquivo e produziria um programa não interativo que simplesmente executa o determinado.

Há um problema aqui: nós realmente não temos noção de quando o arquivo é lido. A [Output]lista com certeza dá uma boa ordem para as saídas , mas não recebemos uma ordem para quando as entradas serão feitas.

Solução: faça com que os eventos de entrada também sejam itens na lista de itens a serem feitos.

data IO₀ = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main₂ :: String -> [IO₀]
main₂ _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hello World"]
          ]

Ok, agora você pode encontrar um desequilíbrio: você pode ler um arquivo e tornar a saída dependente dele, mas não pode usar o conteúdo do arquivo para decidir, por exemplo, também ler outro arquivo. Solução óbvia: torne o resultado dos eventos de entrada também algo do tipo IO, não apenas Output. Isso com certeza inclui saída de texto simples, mas também permite a leitura de arquivos adicionais, etc.

data IO₁ = TxtOut String
         | TxtIn (String -> [IO₁])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO₁])
         | Beep Double

main₃ :: String -> [IO₁]
main₃ _ = [ TxtIn $ \_ ->
             [TxtOut "Hello World"]
          ]

Agora, na verdade, isso permite que você expresse qualquer operação de arquivo que você queira em um programa (embora talvez não tenha um bom desempenho), mas é um pouco complicado demais:

• main₃produz uma lista completa de ações. Por que simplesmente não usamos a assinatura :: IO₁, que tem isso como um caso especial?

• As listas não oferecem mais uma visão geral confiável do fluxo do programa: a maioria dos cálculos subseqüentes será apenas “anunciada” como resultado de alguma operação de entrada. Portanto, podemos também abandonar a estrutura da lista e simplesmente considerar um "e depois fazer" para cada operação de saída.

data IO₂ = TxtOut String IO₂
         | TxtIn (String -> IO₂)
         | Terminate

main₄ :: IO₂
main₄ = TxtIn $ \_ ->
         TxtOut "Hello World"
          Terminate

Não é tão ruim!

Então, o que tudo isso tem a ver com mônadas?

Na prática, você não gostaria de usar construtores simples para definir todos os seus programas. Seria necessário haver um bom par desses construtores fundamentais, mas para a maioria das coisas de nível superior, gostaríamos de escrever uma função com uma boa assinatura de alto nível. Acontece que a maioria delas seria bem semelhante: aceite algum tipo de valor digitado de forma significativa e produza uma ação de IO como resultado.

getTime :: (UTCTime -> IO₂) -> IO₂
randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂
findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

Há evidentemente um padrão aqui, e é melhor escrevê-lo como

type IO₃ a = (a -> IO₂) -> IO₂    -- If this reminds you of continuation-passing
                                  -- style, you're right.

getTime :: IO₃ UTCTime
randomRIO :: Random r => (r,r) -> IO₃ r
findFile :: RegEx -> IO₃ (Maybe FilePath)

Agora isso começa a parecer familiar, mas ainda estamos lidando apenas com funções simples disfarçadas sob o capô, e isso é arriscado: cada "ação de valor" tem a responsabilidade de realmente transmitir a ação resultante de qualquer função contida (senão o fluxo de controle de todo o programa é facilmente interrompido por uma ação mal comportada no meio). É melhor deixarmos esse requisito explícito. Bem, essas são as leis de mônada , embora eu não tenha certeza de que podemos realmente formulá-las sem os operadores de ligação / união padrão.

De qualquer forma, chegamos a uma formulação de E / S que possui uma instância de mônada adequada:

data IO₄ a = TxtOut String (IO₄ a)
           | TxtIn (String -> IO₄ a)
           | TerminateWith a

txtOut :: String -> IO₄ ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO₄ String
txtIn = TxtIn $ TerminateWith

instance Functor IO₄ where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO₄ where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO₄ where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

Obviamente, essa não é uma implementação eficiente de E / S, mas é, em princípio, utilizável.

Mônadas são apenas uma estrutura conveniente para resolver uma classe de problemas recorrentes. Primeiro, as mônadas devem ser functores (isto é, devem suportar o mapeamento sem olhar para os elementos (ou seu tipo)), também devem trazer uma operação de ligação (ou encadeamento) e uma maneira de criar um valor monádico a partir de um tipo de elemento ( return). Finalmente, binde returndeve satisfazer duas equações (identidades esquerda e direita), também chamadas leis da mônada. (Como alternativa, pode-se definir mônadas como tendo em flattening operationvez de vinculadas.)

A mônada da lista é comumente usada para lidar com o não determinismo. A operação de ligação seleciona um elemento da lista (intuitivamente todos eles em mundos paralelos ), permite que o programador faça alguma computação com eles e depois combina os resultados em todos os mundos em uma única lista (concatenando ou achatando uma lista aninhada ) Aqui está como se definiria uma função de permutação na estrutura monádica de Haskell:

perm [e] = [[e]]
perm l = do (leader, index) <- zip l [0 :: Int ..]
            let shortened = take index l ++ drop (index + 1) l
            trailer <- perm shortened
            return (leader : trailer)

Aqui está um exemplo de sessão de repl :

*Main> perm "a"
["a"]
*Main> perm "ab"
["ab","ba"]
*Main> perm ""
[]
*Main> perm "abc"
["abc","acb","bac","bca","cab","cba"]

Deve-se notar que a mônada da lista não é de forma alguma um efeito colateral da computação. Uma estrutura matemática sendo uma mônada (ou seja, em conformidade com as interfaces e leis acima mencionadas) não implica efeitos colaterais, embora os fenômenos com efeito colateral geralmente se encaixem bem na estrutura monádica.

Mônadas servem basicamente para compor funções juntas em uma cadeia. Período.

Agora, a maneira como eles compõem difere das mônadas existentes, resultando em comportamentos diferentes (por exemplo, para simular um estado mutável na mônada de estado).

A confusão sobre as mônadas é que, sendo tão geral, ou seja, um mecanismo para compor funções, elas podem ser usadas para muitas coisas, levando as pessoas a acreditar que as mônadas são sobre estado, IO etc., quando se trata apenas de "funções de composição" "

Agora, uma coisa interessante sobre as mônadas é que o resultado da composição é sempre do tipo "M a", ou seja, um valor dentro de um envelope marcado com "M". Esse recurso é realmente bom para implementar, por exemplo, uma clara separação entre código puro e impuro: declare todas as ações impuras como funções do tipo "IO a" e não forneça função, ao definir a mônada de IO, para remover o " a "valor de dentro do" IO a ". O resultado é que nenhuma função pode ser pura e, ao mesmo tempo, extrair um valor de um "IO a", porque não há como obter esse valor enquanto permanece puro (a função deve estar dentro da mônada "IO" para usar esse valor). (NOTA: bem, nada é perfeito, portanto, a "camisa de força IO" pode ser quebrada usando "unsafePerformIO: IO a -> a"

Você precisa de mônadas se tiver um construtor de tipo e funções que retornem valores dessa família de tipos . Eventualmente, você gostaria de combinar esse tipo de função . Estes são os três elementos principais para responder ao porquê .

Deixe-me elaborar. Você tem Int, Stringe Realfunções do tipo Int -> String, String -> Reale assim por diante. Você pode combinar essas funções facilmente, terminando com Int -> Real. A vida é boa.

Então, um dia, você precisará criar uma nova família de tipos . Pode ser porque você precisa considerar a possibilidade de não retornar valor ( Maybe), retornar um erro ( Either), vários resultados ( List) e assim por diante.

Observe que Maybeé um construtor de tipos. É preciso um tipo, como Inte retorna um novo tipo Maybe Int. Primeira coisa a lembrar, nenhum tipo de construtor, nenhuma mônada.

Obviamente, você deseja usar seu construtor de tipos em seu código e logo termina com funções como Int -> Maybe Stringe String -> Maybe Float. Agora, você não pode combinar facilmente suas funções. A vida não é mais boa.

E é aqui que as mônadas vêm em socorro. Eles permitem combinar esse tipo de função novamente. Você só precisa alterar a composição . para > == .