Por que os efeitos colaterais são modelados como mônadas em Haskell?

172

Alguém poderia dar algumas dicas sobre por que os cálculos impuros em Haskell são modelados como mônadas?

Quero dizer, a mônada é apenas uma interface com 4 operações, então qual foi o motivo para modelar os efeitos colaterais nela?

bodacydo
fonte
15
Mônadas apenas definem duas operações.
Dario
3
mas e o retorno e o fracasso? (além de (>>) e (>> =)) #
bodacydo 21/03
55
As duas operações são returne (>>=). x >> yé o mesmo que x >>= \\_ -> y(isto é, ignora o resultado do primeiro argumento). Nós não falamos sobre fail.
PORGES
2
@Porges Por que não falar sobre falha? É um pouco útil em ie Maybe, Parser, etc.
alternativa
16
@monadic: failestá na Monadclasse por causa de um acidente histórico; realmente pertence MonadPlus. Observe que sua definição padrão é insegura.
JB.

Respostas:

292

Suponha que uma função tenha efeitos colaterais. Se considerarmos todos os efeitos que ele produz como parâmetros de entrada e saída, a função é pura para o mundo exterior.

Então, para uma função impura

f' :: Int -> Int

nós adicionamos o RealWorld à consideração

f :: Int -> RealWorld -> (Int, RealWorld)
-- input some states of the whole world,
-- modify the whole world because of the side effects,
-- then return the new world.

então fé puro novamente. Definimos um tipo de dados parametrizado type IO a = RealWorld -> (a, RealWorld), portanto, não precisamos digitar o RealWorld tantas vezes e podemos escrever

f :: Int -> IO Int

Para o programador, lidar com um RealWorld diretamente é muito perigoso - em particular, se um programador colocar um valor do tipo RealWorld em suas mãos, ele poderá tentar copiá- lo, o que é basicamente impossível. (Pense em tentar copiar todo o sistema de arquivos, por exemplo. Onde você o colocaria?) Portanto, nossa definição de IO também engloba os estados do mundo inteiro.

Composição das funções "impuras"

Essas funções impuras são inúteis se não pudermos colocá-las juntas. Considerar

getLine     :: IO String            ~            RealWorld -> (String, RealWorld)
getContents :: String -> IO String  ~  String -> RealWorld -> (String, RealWorld)
putStrLn    :: String -> IO ()      ~  String -> RealWorld -> ((),     RealWorld)

Nos queremos

  • obtenha um nome de arquivo do console,
  • leia esse arquivo e
  • imprima o conteúdo desse arquivo no console.

Como faríamos se pudéssemos acessar os estados do mundo real?

printFile :: RealWorld -> ((), RealWorld)
printFile world0 = let (filename, world1) = getLine world0
                       (contents, world2) = (getContents filename) world1 
                   in  (putStrLn contents) world2 -- results in ((), world3)

Vemos um padrão aqui. As funções são chamadas assim:

...
(<result-of-f>, worldY) = f               worldX
(<result-of-g>, worldZ) = g <result-of-f> worldY
...

Assim, poderíamos definir um operador ~~~para vinculá-los:

(~~~) :: (IO b) -> (b -> IO c) -> IO c

(~~~) ::      (RealWorld -> (b,   RealWorld))
      ->                    (b -> RealWorld -> (c, RealWorld))
      ->      (RealWorld                    -> (c, RealWorld))
(f ~~~ g) worldX = let (resF, worldY) = f worldX
                   in g resF worldY

então poderíamos simplesmente escrever

printFile = getLine ~~~ getContents ~~~ putStrLn

sem tocar o mundo real.

"Impurificação"

Agora, suponha que também desejemos tornar o conteúdo do arquivo em maiúsculas. Maiúsculas é uma função pura

upperCase :: String -> String

Mas para entrar no mundo real, é preciso retornar um IO String. É fácil levantar essa função:

impureUpperCase :: String -> RealWorld -> (String, RealWorld)
impureUpperCase str world = (upperCase str, world)

Isso pode ser generalizado:

impurify :: a -> IO a

impurify :: a -> RealWorld -> (a, RealWorld)
impurify a world = (a, world)

para que impureUpperCase = impurify . upperCasepossamos escrever

printUpperCaseFile = 
    getLine ~~~ getContents ~~~ (impurify . upperCase) ~~~ putStrLn

(Nota: Normalmente nós escrevemos getLine ~~~ getContents ~~~ (putStrLn . upperCase))

Estávamos trabalhando com mônadas o tempo todo

Agora vamos ver o que fizemos:

  1. Definimos um operador (~~~) :: IO b -> (b -> IO c) -> IO cque une duas funções impuras
  2. Definimos uma função impurify :: a -> IO aque converte um valor puro em impuro.

Agora fazemos a identificação (>>=) = (~~~)e return = impurify, e vê? Temos uma mônada.


Nota técnica

Para garantir que seja realmente uma mônada, ainda existem alguns axiomas que precisam ser verificados também:

  1. return a >>= f = f a

     impurify a                =  (\world -> (a, world))
    (impurify a ~~~ f) worldX  =  let (resF, worldY) = (\world -> (a, world )) worldX 
                                  in f resF worldY
                               =  let (resF, worldY) =            (a, worldX)       
                                  in f resF worldY
                               =  f a worldX
  2. f >>= return = f

    (f ~~~ impurify) worldX  =  let (resF, worldY) = f worldX 
                                in impurify resF worldY
                             =  let (resF, worldY) = f worldX      
                                in (resF, worldY)
                             =  f worldX
  3. f >>= (\x -> g x >>= h) = (f >>= g) >>= h

    Esquerda como exercício.

kennytm
fonte
5
+1, mas quero observar que isso abrange especificamente o caso de E / S. blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html é bastante semelhante, mas generaliza RealWorldem ... bem, você verá.
ephemient 22/03
4
Observe que essa explicação não pode realmente se aplicar à de Haskell IO, porque a última suporta interação, simultaneidade e não-determinismo. Veja minha resposta a esta pergunta para mais alguns indicadores.
Conal
2
O @Conal GHC na verdade implementa IOdessa maneira, mas RealWorldna verdade não representa o mundo real, é apenas um sinal para manter as operações em ordem (a "mágica" é que RealWorldé o único tipo de exclusividade do GHC Haskell)
Jeremy List
2
@JeremyList Pelo que entendi, o GHC implementa IOpor meio de uma combinação dessa representação e magia não-padrão do compilador (uma reminiscência do famoso vírus C do Ken Thompson ). Para outros tipos, a verdade está no código-fonte, juntamente com a semântica usual de Haskell.
Conal
1
@Clonal Meu comentário foi devido a eu ter lido as partes relevantes do código fonte do GHC.
Lista Jeremy
43

Alguém poderia dar algumas dicas sobre por que os cálculos impuros em Haskell são modelados como mônadas?

Esta pergunta contém um mal-entendido generalizado. Impureza e Mônada são noções independentes. A impureza não é modelada pela Monad. Em vez disso, existem alguns tipos de dados, como, por exemplo IO, que representam computação imperativa. E para alguns desses tipos, uma pequena fração de sua interface corresponde ao padrão de interface chamado "Mônada". Além disso, não há explicação pura / funcional / denotativa conhecida de IO(e é improvável que exista uma, considerando o propósito do "binóculo do pecado"IO ), embora exista a história comumente contada sobre World -> (a, World)o significado de IO a. Essa história não pode descrever com sinceridade IO, porqueIOsuporta simultaneidade e não determinismo. A história nem funciona quando se trata de cálculos determinísticos que permitem a interação no meio da computação com o mundo.

Para mais explicações, veja esta resposta .

Edit : Ao reler a pergunta, não acho que minha resposta esteja no caminho certo. Os modelos de computação imperativa geralmente acabam sendo mônadas, exatamente como a pergunta dizia. O autor da pergunta pode realmente não supor que a monadness de qualquer forma permita a modelagem da computação imperativa.

Conal
fonte
1
@KennyTM: Mas RealWorldé, como dizem os médicos , "profundamente mágico". É um token que representa o que o sistema de tempo de execução está fazendo, na verdade não significa nada sobre o mundo real. Você não pode nem invocar um novo para fazer um "fio" sem fazer truques extras; a abordagem ingênua apenas criaria uma ação única e bloqueadora com muita ambiguidade sobre quando será executada.
CA McCann
4
Além disso, eu argumentaria que as mônadas são essencialmente imperativas por natureza. Se o functor representar alguma estrutura com valores incorporados, uma instância de mônada significa que você pode criar e nivelar novas camadas com base nesses valores. Portanto, seja qual for o significado que você atribuir a uma única camada do functor, uma mônada significa que você pode criar um número ilimitado de camadas com uma noção estrita de causalidade que vai de uma para a seguinte. Instâncias específicas podem não ter uma estrutura intrinsecamente imperativa, mas Monadem geral realmente possuem .
CA McCann
3
Por " Monadem geral", quero dizer aproximadamente forall m. Monad m => ..., isto é, trabalhar em uma instância arbitrária. As coisas que você pode fazer com uma mônada arbitrária são quase exatamente as mesmas que você pode fazer com IO: receber primitivas opacas (como argumentos de função ou de bibliotecas, respectivamente), construir no-ops com returnou transformar um valor de maneira irreversível usando (>>=). A essência da programação em uma mônada arbitrária está gerando uma lista de ações irrevogáveis: "faça X, depois faça Y, então ...". Parece bastante imperativo para mim!
CA McCann
2
Não, você ainda está perdendo meu ponto aqui. É claro que você não usaria essa mentalidade para nenhum desses tipos específicos, porque eles têm uma estrutura clara e significativa. Quando digo "mônadas arbitrárias", quero dizer "você não escolhe qual"; a perspectiva aqui é de dentro do quantificador, então pensar mem existencial pode ser mais útil. Além disso, minha "interpretação" é uma reformulação das leis; a lista de instruções "do X" é precisamente o monóide livre na estrutura desconhecida criada via (>>=); e as leis da mônada são apenas leis monóides sobre a composição do endofuncor.
CA McCann
3
Em suma, o maior limite inferior do que todas as mônadas juntas descrevem é uma marcha cega e sem sentido para o futuro. IOé um caso patológico precisamente porque oferece quase nada além desse mínimo. Em casos específicos, os tipos podem revelar mais estrutura e, portanto, ter significado real; mas, de outro modo, as propriedades essenciais de uma mônada - baseadas nas leis - são tão antitéticas quanto a desobstrução da denotação IO. Sem exportar construtores, enumerar exaustivamente ações primitivas ou algo semelhante, a situação é desesperadora.
CA McCann
13

Pelo que entendi, alguém chamado Eugenio Moggi notou pela primeira vez que uma construção matemática anteriormente obscura chamada "mônada" poderia ser usada para modelar efeitos colaterais em linguagens de computador e, portanto, especificar sua semântica usando o cálculo Lambda. Quando Haskell estava sendo desenvolvido, havia várias maneiras pelas quais os cálculos impuros eram modelados (consulte o artigo "camisa de cabelo" de Simon Peyton Jones para obter mais detalhes), mas quando Phil Wadler introduziu mônadas, rapidamente se tornou óbvio que essa era a resposta. E o resto é história.

Paul Johnson
fonte
3
Não é bem assim. Sabe-se que uma mônada pode modelar a interpretação por muito tempo (pelo menos desde "Topoi: Uma análise categórica da lógica). Por outro lado, não era possível expressar claramente os tipos de mônadas até que o tipo funcional fosse fortemente digitado. línguas veio ao redor, e depois Moggi colocar dois e dois juntos.
nomen
1
Talvez as mônadas pudessem ser mais fáceis de entender se elas fossem definidas em termos de quebra de mapa e desempacotamento, com retorno sendo sinônimo de quebra de linha.
aoeu256 6/08/19
9

Alguém poderia dar algumas dicas sobre por que os cálculos impuros em Haskell são modelados como mônadas?

Bem, porque Haskell é puro . Você precisa de um conceito matemático para distinguir entre cálculos impuros e puros no nível de tipo e modelar fluxos de programa respectivamente.

Isso significa que você precisará terminar com algum tipo IO aque modele uma computação não pura. Então você precisa conhecer maneiras de combinar esses cálculos que se aplicam na sequência ( >>=) e elevar um valor ( return) são os mais óbvios e básicos.

Com esses dois, você já definiu uma mônada (sem sequer pensar nisso);)

Além disso, monads fornecer abstrações muito gerais e poderosos , tantos tipos de fluxo de controle pode ser convenientemente generalizada em funções monádicas como sequence, liftMou sintaxe especial, tornando unpureness um caso não tão especial.

Veja mônadas em programação funcional e digitação de exclusividade (a única alternativa que conheço) para obter mais informações.

Dario
fonte
6

Como você diz, Monadé uma estrutura muito simples. Metade da resposta é: Monadé a estrutura mais simples que poderíamos dar às funções de efeito colateral e poder usá-las. Com Monado que podemos fazer duas coisas: podemos tratar um valor puro como um valor-efetuando lado ( return), e podemos aplicar uma função de efetuar um lado para um valor-efetuando lado para obter um novo valor-efetuando lado ( >>=). Perder a capacidade de fazer qualquer uma dessas coisas seria prejudicial, portanto nosso tipo de efeito colateral precisa ser "pelo menos" Monad, e acontece que Monadé suficiente para implementar tudo o que precisamos até agora.

A outra metade é: qual é a estrutura mais detalhada que poderíamos dar aos "possíveis efeitos colaterais"? Certamente, podemos pensar no espaço de todos os possíveis efeitos colaterais como um conjunto (a única operação que requer é associação). Podemos combinar dois efeitos colaterais, realizando-os um após o outro, e isso dará origem a um efeito colateral diferente (ou possivelmente o mesmo - se o primeiro for "computador desligado" e o segundo for "arquivo de gravação"), o resultado de compor estes é apenas "computador de desligamento").

Ok, então o que podemos dizer sobre esta operação? É associativo; isto é, se combinarmos três efeitos colaterais, não importa em que ordem faremos a combinação. Se o fizermos (gravar arquivo, depois ler o soquete) e desligar o computador, será o mesmo que gravar o arquivo (ler soquete e desligar computador). Mas não é comutativo: ("gravar arquivo" e "excluir arquivo") é um efeito colateral diferente de ("excluir arquivo" e "gravar arquivo"). E temos uma identidade: o efeito colateral especial "sem efeitos colaterais" funciona ("sem efeitos colaterais" e "excluir arquivo" é o mesmo efeito que apenas "excluir arquivo"). Nesse ponto, qualquer matemático está pensando em "Grupo!" Mas os grupos têm inversões, e não há como inverter um efeito colateral em geral; "excluir arquivo" é irreversível. Portanto, a estrutura que nos resta é a de um monóide, o que significa que nossas funções de efeito colateral devem ser mônadas.

Existe uma estrutura mais complexa? Certo! Poderíamos dividir os possíveis efeitos colaterais em efeitos do sistema de arquivos, efeitos da rede e muito mais, e poderíamos criar regras de composição mais elaboradas que preservassem esses detalhes. Mas, novamente, tudo se resume a: Monadé muito simples e, no entanto, poderoso o suficiente para expressar a maioria das propriedades com as quais nos preocupamos. (Em particular, associatividade e outros axiomas, vamos testar nossa aplicação em pedaços pequenos, com confiança de que os efeitos colaterais do aplicativo combinado serão os mesmos da combinação dos efeitos colaterais das peças).

lmm
fonte
4

Na verdade, é uma maneira bastante clara de pensar na E / S de maneira funcional.

Na maioria das linguagens de programação, você realiza operações de entrada / saída. Em Haskell, imagine escrever código não para executar as operações, mas para gerar uma lista das operações que você gostaria de fazer.

Mônadas são apenas uma sintaxe bonita para exatamente isso.

Se você quiser saber por que as mônadas, ao contrário de outra coisa, acho que a resposta é que elas são a melhor maneira funcional de representar E / S em que as pessoas poderiam pensar quando estavam fazendo Haskell.

Noah Lavine
fonte
3

AFAIK, o motivo é poder incluir verificações de efeitos colaterais no sistema de tipos. Se você quiser saber mais, ouça os episódios da SE-Radio : Episódio 108: Simon Peyton Jones em Programação Funcional e Haskell Episódio 72: Erik Meijer no LINQ

Gabriel Ščerbák
fonte
2

Acima, há respostas muito boas e detalhadas com base teórica. Mas quero dar minha opinião sobre a mônada de IO. Eu não sou programador de haskell experiente, então pode ser que seja bastante ingênuo ou até errado. Mas eu me ajudei a lidar com a mônada de IO até certo ponto (observe que ela não se relaciona com outras mônadas).

Primeiro, quero dizer que esse exemplo com "mundo real" não é muito claro para mim, pois não podemos acessar seus estados anteriores (mundo real). Pode ser que não esteja relacionado a cálculos de mônada, mas é desejado no sentido de transparência referencial, que geralmente está presente no código haskell.

Então, queremos que nossa linguagem (haskell) seja pura. Mas precisamos de operações de entrada / saída, pois sem elas nosso programa não pode ser útil. E essas operações não podem ser puras por natureza. Portanto, a única maneira de lidar com isso é separar as operações impuras do restante do código.

Aqui mônada vem. Na verdade, não tenho certeza, que não possa existir outra construção com propriedades necessárias semelhantes, mas o ponto é que a mônada possui essas propriedades, para que possa ser usada (e usada com sucesso). A principal propriedade é que não podemos escapar dela. A interface de mônada não possui operações para se livrar da mônada em torno de nosso valor. Outras mônadas (não IO) fornecem essas operações e permitem a correspondência de padrões (por exemplo, Talvez), mas essas operações não estão na interface de mônada. Outra propriedade necessária é a capacidade de encadear operações.

Se pensarmos sobre o que precisamos em termos de sistema de tipos, chegamos ao fato de que precisamos digitar com construtor, que pode ser envolvido em qualquer vale. O construtor deve ser privado, pois proibimos escapar dele (ou seja, correspondência de padrões). Mas precisamos de função para colocar valor nesse construtor (aqui o retorno vem à mente). E precisamos do caminho para encadear operações. Se pensarmos por algum tempo, chegaremos ao fato de que a operação de encadeamento deve ter o tipo >> >> has. Então, chegamos a algo muito semelhante à mônada. Penso que, se agora analisarmos possíveis situações contraditórias com esse construto, chegaremos a mônada axiomas.

Observe que esse construto desenvolvido não tem nada em comum com a impureza. Ele possui apenas propriedades que desejávamos ter capacidade de lidar com operações impuras, como não escapar, encadear e uma maneira de entrar.

Agora, um conjunto de operações impuras é predefinido pelo idioma dentro dessa EI de mônada selecionada. Podemos combinar essas operações para criar novas operações impuras. E todas essas operações terão que ter E / S em seu tipo. Observe, no entanto, que a presença de E / S no tipo de alguma função não torna essa função impura. Mas, pelo que entendi, é uma má idéia escrever funções puras com IO em seu tipo, pois foi inicialmente nossa idéia separar funções puras e impuras.

Finalmente, quero dizer, que a mônada não transforma operações impuras em operações puras. Só permite separá-los efetivamente. (Repito, que é apenas o meu entendimento)

Dmitrii Semikin
fonte
1
Eles ajudam a digitar o seu programa, permitindo que você digite efeitos de verificação, e você pode definir suas próprias DSLs criando mônadas para restringir os efeitos que suas funções podem fazer, para que o compilador possa verificar seus erros de seqüenciamento.
aoeu256 6/08/19
Este comentário de aoeu256 é o "porquê" que está faltando em todas as explicações dadas até agora. (ou seja: mônadas não são para humanos, mas para compiladores)
João Otero