Mônada (programação funcional) - Monad (functional programming)

Na programação funcional , uma mônada é uma abstração que permite estruturar programas genericamente . As linguagens de suporte podem usar mônadas para abstrair o código clichê necessário para a lógica do programa. As mônadas conseguem isso fornecendo seu próprio tipo de dados (um tipo específico para cada tipo de mônada), que representa uma forma específica de computação , junto com dois procedimentos :

• Um para envolver valores de qualquer tipo básico dentro da mônada (produzindo um valor monádico );
• Outro para compor funções que geram valores monádicos (chamadas funções monádicas ).

Isso permite que as mônadas simplifiquem uma ampla gama de problemas, como lidar com valores indefinidos potenciais (com a Maybemônada) ou manter os valores em uma lista bem formada e flexível (usando a Listmônada). Com uma mônada, um programador pode transformar uma sequência complicada de funções em um pipeline sucinto que abstrai o gerenciamento de dados auxiliares, o fluxo de controle ou os efeitos colaterais .

Tanto o conceito de mônada quanto o termo vêm originalmente da teoria das categorias , onde uma mônada é definida como um functor com estrutura adicional. Pesquisas iniciadas no final da década de 1980 e início da década de 1990 estabeleceram que as mônadas poderiam trazer problemas de ciência da computação aparentemente díspares sob um modelo funcional unificado. A teoria das categorias também fornece alguns requisitos formais, conhecidos como leis de mônada , que devem ser satisfeitos por qualquer mônada e podem ser usados ​​para verificar o código monádico.

Visto que as mônadas tornam a semântica explícita para um tipo de computação, elas também podem ser usadas para implementar recursos de linguagem convenientes. Algumas linguagens, como Haskell , até oferecem definições predefinidas em suas bibliotecas principais para a estrutura geral da mônada e instâncias comuns.

Visão geral

"Para uma mônada m, um valor de tipo m arepresenta ter acesso a um valor de tipo adentro do contexto da mônada." —CA McCann

Uma mônada pode ser criada definindo um construtor de tipo M e duas operações: return(também chamada de unidade ), que recebe um valor de tipo ae o envolve em um valor monádico de tipo m a, usando o construtor de tipo; e bind(normalmente representado como >>=), que recebe uma função fsobre o tipo ae pode transformar valores monádicos que se m aaplicam fao valor não embalado a. (Uma construção alternativa, mas equivalente, usando a join função em vez do bindoperador pode ser encontrada na seção posterior § Derivação de functores .)

Com esses elementos, o programador compõe uma sequência de chamadas de função (um "pipeline") com vários operadores de vinculação encadeados em uma expressão. Cada chamada de função transforma seu valor de tipo simples de entrada e o operador de vinculação lida com o valor monádico retornado, que é alimentado na próxima etapa na sequência.

Entre cada par de chamadas de função compostas, o operador de ligação >>=pode injetar no valor monádico m aalgumas informações adicionais que não estão acessíveis dentro da função fe passá-las ao longo do pipeline. Ele também pode exercer um controle mais preciso do fluxo de execução, por exemplo, chamando a função apenas sob algumas condições ou executando as chamadas de função em uma ordem específica.

Um exemplo: talvez

Para motivar a programação com mônadas, aqui está um exemplo rápido de pseudocódigo. Valores ou operações indefinidos são um problema particular para o qual um software robusto deve se preparar e lidar com elegância.

O primeiro passo em direção a esse objetivo pode ser criar um tipo de opção que marcará um valor como tendo um valor de algum tipo T( Tpode ser de qualquer tipo) ou sem nenhum valor. O novo tipo será chamado Maybe Te os valores desse tipo podem conter um valor do tipo Tou ser o valor vazio Nothing. Um valor Xdo tipo Tque é definido, mas usado no contexto de Maybeserá chamado Just X. Isso é feito para evitar confusão, diferenciando entre os casos em que uma variável carrega um valor definido e aqueles em que não carrega.

data Maybe T  =  Just T or Nothing

Maybe Tpode ser entendido como um tipo de "encapsulamento", agrupando o tipo Tem um novo tipo com tratamento de exceção embutido, embora não contenha nenhuma informação sobre a causa de uma exceção.

No código a seguir, as variáveis ​​prefixadas com mtêm o tipo Maybe Tpara algum tipo T. Por exemplo, se uma variável mxcontém um valor, é Just x, onde a variável xtem o tipo T. λx → ...é uma função anônima com o parâmetro xcujo tipo é inferido e ∘é o operador de composição da função .

Outra melhoria seria se uma função pudesse gerenciar exceções verificadas simples com um Maybetipo, causando curto-circuito e retornando Nothingquando uma etapa falha, mas retornando o valor correto sem comentários se um cálculo for bem-sucedido.

Uma função de adição add, que faz exatamente isso ao adicionar dois Maybevalores mxe my, pode ser definida assim:

 add : (Maybe Number, Maybe Number) → Maybe Number
 add(mx,my) = ...
     if mx is Nothing then
         ... Nothing
     else if my is Nothing then
         ... Nothing
     else
         ... Just (x + y)
     end if

Escrever funções que processam Maybevalores caso a caso pode ser entediante, e só se tornará mais tedioso à medida que mais funções forem definidas. Uma operação para encadear etapas juntas é uma maneira de aliviar isso e, com um operador infixo como x >>= y, pode até representar intuitivamente a alimentação do resultado (possivelmente indefinido) de cada etapa para a próxima. Como cada resultado é tecnicamente inserido em outra função , no entanto, o operador tomará uma função como parâmetro. Como addjá especifica o tipo de seu valor de saída, não deve doer manter o operador flexível e aceitar funções que geram diferentes tipos de sua entrada:

 >>= : (Maybe T, T → Maybe U) → Maybe U
 (mx >>= f) = ...
     if mx is (Just x) then
         ... f(x)    -- evaluate f(x) and return (possibly undefined) output
     else
         ... Nothing -- pass through an undefined input
     end if

Com o >>=disponível, addagora pode ser redefinido como algo muito mais compacto:

 add(mx,my)  =  mx >>= λx -> (my >>= λy -> Just (x + y))

Isso é mais conciso, mas um pouco de análise extra revela algo ainda mais poderoso. Por um lado, a única função que Justdesempenha addé marcar um valor subjacente como sendo também um Maybevalor. Para enfatizar como Just atua no valor subjacente ao envolvê-lo, ele também pode ser redefinido como uma função, chamada etapor enquanto:

 eta : T → Maybe T
 eta(x)  =  Just x

O retrato grande é que estas duas funções >>=e etaforam projetados para simplificar add, mas eles claramente não dependem das especificidades de addem qualquer forma, apenas o Maybetipo. Essas funções podem, de fato, se aplicar a quaisquer valores e funções do Maybetipo, independentemente dos tipos de valores subjacentes. Por exemplo, aqui está um operador NOT conciso da lógica trinária (de Kleene) que usa as mesmas funções para automatizar valores indefinidos também:

trinot : Maybe Boolean → Maybe Boolean
trinot(mp)  =  mp >>= λp -> (eta ∘ not) p

onde ∘denota a composição da função e a definição anterior é equivalente a:

trinot(mp)  =  mp >>= λp -> Just (not p)

Acontece que o Maybetipo, junto com >>=e eta, forma uma mônada. Embora outras mônadas incorporem processos lógicos diferentes e algumas possam ter propriedades extras, todas elas terão três componentes semelhantes (direta ou indiretamente) que seguem o esboço básico deste exemplo.

Definição

A definição mais comum para uma mônada em programação funcional, usada no exemplo acima, é na verdade baseada em um triplo de Kleisli em vez da definição padrão da teoria da categoria. As duas construções revelaram-se matematicamente equivalentes, portanto, qualquer uma das definições produzirá uma mônada válida. Dado qualquer tipo básico e bem definido T , U , uma mônada consiste em três partes:

• Um construtor de tipo M que constrói um tipo monádico MT
• Um conversor de tipo , geralmente chamado de unidade ou retorno , que incorpora um objeto x na mônada:
  unit : T → M T
• Um combinador , normalmente chamado de ligação (como na ligação de uma variável ) e representado por um operador infixo >>= ou um método chamado flatMap , que desembrulha uma variável monádica e a insere em uma função / expressão monádica, resultando em um novo valor monádico:
  (>>=) : (M T, T → M U) → M Uentão se mx : M Te f : T → M U, então (mx >>= f) : M U

No entanto, para se qualificar totalmente como uma mônada, essas três partes também devem respeitar algumas leis:

• unidade é uma identidade esquerda para vincular :
  unit(x) >>= f ↔ f(x)
• unidade também é uma identidade correta para vincular :
  ma >>= unit ↔ ma
• vincular é essencialmente associativo :
  ma >>= λx → (f(x) >>= g) ↔ (ma >>= f) >>= g

Algebricamente, isso significa que qualquer mônada dá origem a uma categoria (chamada de categoria Kleisli ) e a um monóide na categoria de functores (de valores a cálculos), com composição monádica como um operador binário e unidade como identidade.

Uso

O valor do padrão de mônada vai além de meramente condensar o código e fornecer um link para o raciocínio matemático. Qualquer que seja a linguagem ou paradigma de programação padrão que um desenvolvedor use, seguir o padrão monad traz muitos dos benefícios da programação puramente funcional . Ao reificar um tipo específico de computação, uma mônada não apenas encapsula os detalhes tediosos desse padrão computacional, mas o faz de forma declarativa , melhorando a clareza do código. Como os valores monádicos representam explicitamente não apenas valores computados, mas efeitos computados , uma expressão monádica pode ser substituída por seu valor em posições referencialmente transparentes , assim como as expressões puras podem ser, permitindo muitas técnicas e otimizações baseadas na reescrita .

Normalmente, os programadores usam bind para encadear funções monádicas em uma sequência, o que levou alguns a descrever as mônadas como "ponto-e-vírgulas programáveis", uma referência a quantas linguagens imperativas usam ponto-e-vírgula para separar instruções . No entanto, deve ser enfatizado que as mônadas não ordenam cálculos; mesmo em linguagens que os usam como recursos centrais, a composição de funções mais simples pode organizar etapas dentro de um programa. A utilidade geral de uma mônada reside em simplificar a estrutura de um programa e melhorar a separação de interesses por meio da abstração.

A estrutura da mônada também pode ser vista como uma variação exclusivamente matemática e de tempo de compilação no padrão do decorador . Algumas mônadas podem transmitir dados extras que são inacessíveis às funções e algumas até exercem um controle mais preciso sobre a execução, por exemplo, apenas chamando uma função sob certas condições. Como eles permitem que os programadores de aplicativos implementem a lógica de domínio enquanto descarregam o código clichê em módulos pré-desenvolvidos, as mônadas podem até ser consideradas uma ferramenta para a programação orientada a aspectos .

Outro uso digno de nota para as mônadas é o isolamento de efeitos colaterais, como entrada / saída ou estado mutável , em código puramente funcional. Mesmo linguagens puramente funcionais ainda podem implementar esses cálculos "impuros" sem mônadas, por meio de uma mistura intrincada de composição de função e estilo de passagem de continuação (CPS) em particular. Com as mônadas, porém, muito desse andaime pode ser abstraído, essencialmente pegando cada padrão recorrente no código CPS e agrupando-o em uma mônada distinta.

Se uma linguagem não oferece suporte a mônadas por padrão, ainda é possível implementar o padrão, geralmente sem muita dificuldade. Quando traduzida da teoria das categorias para termos de programação, a estrutura da mônada é um conceito genérico e pode ser definida diretamente em qualquer linguagem que suporte um recurso equivalente para polimorfismo limitado . A capacidade de um conceito de permanecer agnóstico sobre os detalhes operacionais enquanto trabalha com os tipos subjacentes é poderosa, mas os recursos exclusivos e o comportamento rigoroso das mônadas os diferenciam de outros conceitos.

Formulários

As discussões de mônadas específicas normalmente se concentrarão na solução de um problema de implementação restrito, uma vez que uma determinada mônada representa uma forma computacional específica. Em algumas situações, porém, um aplicativo pode até atingir seus objetivos de alto nível usando mônadas apropriadas dentro de sua lógica central.

Aqui estão apenas alguns aplicativos que têm mônadas no centro de seus projetos:

• A biblioteca do analisador Parsec usa mônadas para combinar regras de análise mais simples em outras mais complexas e é particularmente útil para linguagens específicas de domínio menores .
• xmonad é um gerenciador de janelas lado a lado centrado na estrutura de dados do zíper , que pode ser tratada monadicamente como um caso específico de continuações delimitadas .
• LINQ by Microsoft fornece uma linguagem de consulta para o .NET Framework que é fortemente influenciada por conceitos de programação funcional, incluindo operadores principais para compor consultas monadicamente.
• ZipperFS é um sistema de arquivos experimental simples que também usa a estrutura do zipper principalmente para implementar seus recursos.
• A estrutura de extensões reativas fornece essencialmente uma interface (co) monádica para fluxos de dados que realiza o padrão do observador .

História

O termo "mônada" na programação, na verdade, remonta às linguagens de programação APL e J , que tendem a ser puramente funcionais. No entanto, nessas linguagens, "mônada" é apenas uma abreviação para uma função que recebe um parâmetro (uma função com dois parâmetros sendo uma "díade" e assim por diante).

O matemático Roger Godement foi o primeiro a formular o conceito de mônada (apelidando-o de "construção padrão") no final dos anos 1950, embora o termo "mônada" que veio a dominar tenha sido popularizado pelo teórico da categoria Saunders Mac Lane . A forma definida acima usando bind , entretanto, foi originalmente descrita em 1965 pelo matemático Heinrich Kleisli a fim de provar que qualquer mônada poderia ser caracterizada como uma adjunção entre dois functores (covariantes).

A partir da década de 1980, uma vaga noção do padrão de mônada começou a surgir na comunidade da ciência da computação. De acordo com o pesquisador de linguagem de programação Philip Wadler , o cientista da computação John C. Reynolds antecipou várias facetas disso na década de 1970 e início de 1980, quando discutiu o valor do estilo de passagem de continuação , a teoria das categorias como uma fonte rica de semântica formal e o tipo distinção entre valores e cálculos. A linguagem de pesquisa Opal , que foi ativamente projetada até 1990, também baseou efetivamente o I / O em um tipo monádico, mas a conexão não foi realizada na época.

O cientista da computação Eugenio Moggi foi o primeiro a vincular explicitamente a mônada da teoria das categorias à programação funcional, em um artigo de conferência em 1989, seguido por uma submissão de periódico mais refinado em 1991. Em trabalhos anteriores, vários cientistas da computação avançaram usando a teoria das categorias para fornecer semântica para o cálculo lambda . O principal insight de Moggi foi que um programa do mundo real não é apenas uma função de valores para outros valores, mas sim uma transformação que forma cálculos sobre esses valores. Quando formalizado em termos da teoria da categoria, isso leva à conclusão de que as mônadas são a estrutura para representar esses cálculos.

Vários outros popularizaram e desenvolveram essa ideia, incluindo Philip Wadler e Simon Peyton Jones , ambos envolvidos na especificação de Haskell. Em particular, Haskell usou um modelo problemático de "fluxo lento" até a v1.2 para reconciliar E / S com avaliação lenta , até mudar para uma interface monádica mais flexível. A comunidade Haskell aplicaria mônadas a muitos problemas de programação funcional e, na década de 2010, os pesquisadores que trabalharam com Haskell finalmente reconheceram que as mônadas são functores aplicativos ; e que tanto mônadas quanto flechas são monóides .

No início, a programação com mônadas estava amplamente confinada a Haskell e seus derivados, mas como a programação funcional influenciou outros paradigmas, muitas linguagens incorporaram um padrão de mônada (em espírito, se não no nome). As formulações agora existem em Scheme , Perl , Python , Racket , Clojure , Scala , F # , e também foram consideradas para um novo padrão de ML .

Análise

Um benefício do padrão de mônada é trazer a precisão matemática para influenciar a lógica do programa. Não apenas as leis de mônadas podem ser usadas para verificar a validade de uma instância, mas recursos de estruturas relacionadas (como functores) podem ser usados ​​por meio de subtipagem .

Verificando as leis da mônada

Voltando ao Maybeexemplo, seus componentes foram declarados como constituindo uma mônada, mas nenhuma prova foi fornecida de que ele satisfaz as leis da mônada.

Isso pode ser retificado conectando-se as especificações de Maybeem um lado das leis gerais e, em seguida, construindo algebricamente uma cadeia de igualdades para alcançar o outro lado:

Law 1:  eta(a) >>= f(x)  ⇔  (Just a) >>= f(x)  ⇔  f(a)

Law 2:  ma >>= eta(x)           ⇔  ma

        if ma is (Just a) then
            eta(a)              ⇔ Just a
        else                        or
            Nothing             ⇔ Nothing
        end if

Law 3:  (ma >>= f(x)) >>= g(y)                       ⇔  ma >>= (f(x) >>= g(y))

        if (ma >>= f(x)) is (Just b) then               if ma is (Just a) then
            g(ma >>= f(x))                                (f(x) >>= g(y)) a
        else                                            else
            Nothing                                         Nothing
        end if                                          end if

                ⇔  if ma is (Just a) and f(a) is (Just b) then      
                       (g ∘ f) a
                   else if ma is (Just a) and f(a) is Nothing then
                       Nothing
                   else
                       Nothing
                   end if

Derivação de functores

Embora mais raro na ciência da computação, pode-se usar a teoria das categorias diretamente, que define uma mônada como um functor com duas transformações naturais adicionais . Portanto, para começar, uma estrutura requer uma função de ordem superior (ou "funcional") chamada map para se qualificar como um functor:

Isso nem sempre é um grande problema, entretanto, especialmente quando uma mônada é derivada de um functor pré-existente, após o que a mônada herda o mapa automaticamente. (Por razões históricas, ele mapé chamado fmapem Haskell.)

A primeira transformação de uma mônada é na verdade a mesma unidade da tríplice de Kleisli, mas seguindo de perto a hierarquia de estruturas, a unidade caracteriza um functor aplicativo , uma estrutura intermediária entre uma mônada e um functor básico. No contexto do aplicativo, a unidade é algumas vezes referida como pura, mas ainda tem a mesma função. O que difere nessa construção é que a unidade da lei deve satisfazer; como o vínculo não está definido, a restrição é dada em termos de mapa em vez disso:

O salto final do functor aplicativo para a mônada vem com a segunda transformação, a função de junção (na teoria da categoria, esta é uma transformação natural geralmente chamada de μ ), que "nivela" os aplicativos aninhados da mônada:

Como função característica, a junção também deve satisfazer três variações nas leis da mônada:

Independentemente de um desenvolvedor definir uma mônada direta ou um triplo Kleisli, a estrutura subjacente será a mesma e as formas podem ser derivadas umas das outras facilmente:

Outro exemplo: List

A lista mônada demonstra naturalmente como derivar uma mônada de um functor mais simples pode ser útil. Em muitas linguagens, uma estrutura de lista vem pré-definida junto com alguns recursos básicos, portanto, um Listconstrutor de tipo e um operador de acréscimo (representado com ++para notação de infixo) são assumidos como já fornecidos aqui.

Incorporar um valor simples em uma lista também é trivial na maioria das linguagens:

unit(x)  =  [x]

A partir daqui, aplicar uma função iterativamente com uma compreensão de lista pode parecer uma escolha fácil para vincular e converter listas em uma mônada completa. A dificuldade com essa abordagem é que o bind espera funções monádicas, que, neste caso, produzirão as próprias listas; à medida que mais funções são aplicadas, camadas de listas aninhadas se acumulam, exigindo mais do que uma compreensão básica.

No entanto, um procedimento para aplicar qualquer função simples em toda a lista, em outras palavras , mapa , é direto:

(map φ) xlist  =  [ φ(x1), φ(x2), ..., φ(xn) ]

Agora, esses dois procedimentos já promovem Lista um functor aplicativo. Para se qualificar totalmente como uma mônada, apenas uma noção correta de junção para nivelar a estrutura repetida é necessária, mas para listas, isso significa apenas desembrulhar uma lista externa para anexar as internas que contêm valores:

join(xlistlist)  =  join([xlist1, xlist2, ..., xlistn])
                 =  xlist1 ++ xlist2 ++ ... ++ xlistn

A mônada resultante não é apenas uma lista, mas uma que se redimensiona e se condensa automaticamente conforme as funções são aplicadas. bind agora também pode ser derivado com apenas uma fórmula e usado para alimentar Listvalores por meio de um pipeline de funções monádicas:

A Listmônada pode simplificar muito o uso de funções de vários valores, como raízes complexas.

(xlist >>= f)  =  join ∘ (map f) xlist

Uma aplicação para essa lista monádica é a representação de computação não determinística . Listpode conter resultados para todos os caminhos de execução em um algoritmo e, em seguida, condensar-se em cada etapa para "esquecer" quais caminhos levaram a quais resultados (uma distinção às vezes importante de algoritmos determinísticos exaustivos). Outro benefício é que os cheques podem ser incorporados à mônada; caminhos específicos podem ser removidos de forma transparente em seu primeiro ponto de falha, sem a necessidade de reescrever funções no pipeline.

Uma segunda situação em que Listbrilha é a composição de funções de vários valores . Por exemplo, o n th raiz complexa de um número deve render n números complexos distintos, mas se outra m th raiz é então feita desses resultados, a final m • n valores deve ser idêntico para a saída do m • n th raiz . Listautomatiza completamente esse problema, condensando os resultados de cada etapa em uma lista simples e matematicamente correta.

Técnicas

As mônadas apresentam oportunidades para técnicas interessantes além de apenas organizar a lógica do programa. As mônadas podem estabelecer a base para recursos sintáticos úteis, enquanto sua natureza matemática de alto nível permite uma abstração significativa.

Açúcar sintático notação

Embora usar bind abertamente muitas vezes faça sentido, muitos programadores preferem uma sintaxe que imite declarações imperativas (chamada de notação de doação em Haskell, notação de desempenho em OCaml , expressões de computação em F # e para compreensão em Scala ). Este é apenas o açúcar sintático que disfarça um pipeline monádico como um bloco de código ; o compilador então traduzirá silenciosamente essas expressões em código funcional subjacente.

Traduzir a addfunção de Maybepara Haskell pode mostrar esse recurso em ação. Uma versão não monádica de addem Haskell se parece com isto:

add mx my =
    case mx of
        Nothing -> Nothing
        Just x  -> case my of
                       Nothing -> Nothing
                       Just y  -> Just (x + y)

Em Haskell monádico, returné o nome padrão para unidade , mais as expressões lambda devem ser tratadas explicitamente, mas mesmo com esses detalhes técnicos, a Maybemônada oferece uma definição mais limpa:

add mx my =
    mx >>= (\x ->
        my >>= (\y ->
            return (x + y)))

Com a notação do, porém, isso pode ser destilado ainda mais em uma sequência muito intuitiva:

add mx my = do
    x <- mx
    y <- my
    return (x + y)

Um segundo exemplo mostra como Maybepode ser usado em uma linguagem totalmente diferente: F #. Com expressões de computação, uma função de "divisão segura" que retorna Nonepara um operando indefinido ou divisão por zero pode ser escrita como:

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None

let secure_div = 
  maybe { 
    let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

No momento da construção, o compilador irá "desmarcar" internamente esta função em uma cadeia mais densa de chamadas de ligação :

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return(x / y))))

Para um último exemplo, até mesmo as próprias leis gerais de mônadas podem ser expressas em notação de doação:

do { x <- return v; f x }            ==  do { f v }
do { x <- m; return x }              ==  do { m }
do { y <- do { x <- m; f x }; g y }  ==  do { x <- m; y <- f x; g y }

Embora seja conveniente, um desenvolvedor deve sempre lembrar que esse estilo de bloco é puramente sintático e pode ser substituído por expressões externamente monádicas (ou mesmo CPS não monádicas). Usar bind para expressar o pipeline monádico ainda pode ser mais claro em muitos casos, e alguns defensores da programação funcional até argumentam que, uma vez que o estilo de bloco permite que os novatos carreguem hábitos da programação imperativa, ele deve ser evitado por padrão e usado apenas quando obviamente superior.

Interface geral

Cada mônada precisa de uma implementação específica que atenda às leis da mônada, mas outros aspectos, como a relação com outras estruturas ou idiomas padrão dentro de uma linguagem, são compartilhados por todas as mônadas. Como resultado, uma linguagem ou biblioteca pode fornecer uma Monadinterface geral com protótipos de funções , relações de subtipagem e outros fatos gerais. Além de fornecer uma vantagem para o desenvolvimento e garantir que uma nova mônada herde recursos de um supertipo (como functores), verificar o design de uma mônada em relação à interface adiciona outra camada de controle de qualidade.

Operadores

O código monádico muitas vezes pode ser simplificado ainda mais por meio do uso criterioso de operadores. O funcional do mapa pode ser especialmente útil, pois funciona em mais do que apenas funções monádicas ad-hoc; contanto que uma função monádica funcione de forma análoga a um operador predefinido, o mapa pode ser usado para " elevar " instantaneamente o operador mais simples a um operador monádico. Com esta técnica, a definição addda partir do Maybeexemplo poderia ser destilada em:

add(mx,my)  =  map (+)

O processo pode ser levado um passo adiante, definindo addnão apenas para Maybe, mas para toda a Monadinterface. Ao fazer isso, qualquer nova mônada que corresponda à interface da estrutura e implemente seu próprio mapa herdará imediatamente uma versão elevada de addtambém. A única mudança necessária na função é generalizar a assinatura de tipo:

add : (Monad Number, Monad Number)  →  Monad Number

Outro operador monádico que também é útil para análise é a composição monádica (representada >=>aqui como infixo ), que permite encadear funções monádicas em um estilo mais matemático:

(f >=> g) x  =  (f(x) → mb) >>= g(y = b)

Com este operador, as leis de mônadas podem ser escritas em termos de funções sozinhas, destacando a correspondência com a associatividade e a existência de uma identidade:

(unit >=> g)     ↔  g
(f >=> unit)     ↔  f
(f >=> g) >=> h  ↔  f >=> (g >=> h)

Variações

Em um nível matemático, algumas mônadas têm propriedades particularmente agradáveis ​​e se adaptam de maneira única a certos problemas.

Mônadas aditivas

Uma mônada aditiva é uma mônada dotada de um operador adicional fechado, associativo e binário mplus e um elemento de identidade sob mplus , denominado mzero . O Maybemônade pode ser considerado aditivo, com Nothingcomo mzero e uma variação na OU operador como mplus . Listtambém é uma mônada aditiva, com a lista vazia []atuando como mzero e o operador de concatenação ++como mplus .

Intuitivamente, mzero representa um invólucro monádico sem nenhum valor de um tipo subjacente, mas também é considerado um "zero" (em vez de um "um"), pois atua como um absorvedor de vínculo , retornando mzero sempre que vinculado a uma função monádica. Esta propriedade tem dois lados e bind também retornará mzero quando qualquer valor for vinculado a uma função zero monádica .

Em termos da teoria da categoria, uma mônada aditiva se qualifica uma vez como monóide sobre funções monádicas com bind (como todas as mônadas fazem), e novamente sobre valores monádicos via mplus .

Mônadas grátis

Às vezes, o esboço geral de uma mônada pode ser útil, mas nenhum padrão simples recomenda uma mônada ou outra. É aqui que entra uma mônada livre ; como um objeto livre na categoria das mônadas, pode representar a estrutura monádica sem quaisquer restrições específicas além das próprias leis da mônada. Assim como um monóide livre concatena elementos sem avaliação, uma mônada livre permite o encadeamento de cálculos com marcadores para satisfazer o sistema de tipos, mas de outra forma não impõe nenhuma semântica mais profunda.

Por exemplo, ao trabalhar inteiramente por meio dos marcadores Juste Nothing, a Maybemônada é de fato uma mônada livre. A Listmônada, por outro lado, não é uma mônada livre, pois traz fatos extras e específicos sobre listas (como apêndices ) em sua definição. Um último exemplo é uma mônada livre abstrata:

data Free f a
  = Pure a
  | Free (f (Free f a))

unit :: a -> Free f a
unit x = Pure x

bind :: Functor f => Free f a -> (a -> Free f b) -> Free f b
bind (Pure x) f = f x
bind (Free x) f = Free (fmap (\y -> bind y f) x)

Mônadas livres, no entanto, não estão restritas a uma lista vinculada como neste exemplo e podem ser construídas em torno de outras estruturas, como árvores .

Usar mônadas livres intencionalmente pode parecer impraticável no início, mas sua natureza formal é particularmente adequada para problemas sintáticos. Uma mônada livre pode ser usada para rastrear a sintaxe e o tipo, deixando a semântica para depois e, como resultado, encontrou uso em analisadores e interpretadores . Outros também os aplicaram a problemas operacionais mais dinâmicos, como fornecer iteratees em uma linguagem.

Comonads

Além de gerar mônadas com propriedades extras, para qualquer mônada, também se pode definir uma comônada . Conceitualmente, se as mônadas representam cálculos construídos a partir de valores subjacentes, então as comônadas podem ser vistas como reduções de volta aos valores. O código monádico, em certo sentido, não pode ser totalmente "desempacotado"; uma vez que um valor é encapsulado em uma mônada, ele permanece em quarentena junto com quaisquer efeitos colaterais (uma coisa boa na programação puramente funcional). Às vezes, porém, um problema é mais sobre consumir dados contextuais, que os comonads podem modelar explicitamente.

Tecnicamente, uma comonada é o dual categórico de uma mônada, o que significa vagamente que terá os mesmos componentes necessários, apenas com a direção das assinaturas de tipo invertida . A partir da definição de mônada centrada em ligação , uma comônada consiste em:

• Um construtor de tipo W que marca o tipo de ordem superior WT
• A dupla da unidade , chamada counit aqui, extrai o valor subjacente do comonad:

counit(wa) : W T → T

• Uma reversão de ligação (também representada por =>>) que estende uma cadeia de funções de redução:

(wa =>> f) : (W U, W U → T) → W T

estender e contar também devem satisfazer os duais das leis da mônada:

counit ∘ ( (wa =>> f) → wb )  ↔  f(wa) → b
wa =>> counit  ↔  wa
wa ( (=>> f(wx = wa)) → wb (=>> g(wy = wb)) → wc )  ↔  ( wa (=>> f(wx = wa)) → wb ) (=>> g(wy = wb)) → wc

De forma análoga às mônadas, as comônadas também podem ser derivadas de functores usando um dual de junção :

• duplicate pega um valor já comum e o envolve em outra camada de estrutura comonádica:

duplicate(wa) : W T → W (W T)

Embora operações como extend sejam revertidas, no entanto, um comonad não inverte as funções nas quais ele atua e, conseqüentemente, comonads ainda são functores com map , não co-fun- cionadores . A definição alternativa com duplicado , contagem e mapa também deve respeitar suas próprias leis comuns:

((map duplicate) ∘ duplicate) wa  ↔  (duplicate ∘ duplicate) wa  ↔  wwwa
((map counit) ∘ duplicate)    wa  ↔  (counit ∘ duplicate)    wa  ↔  wa
((map map φ) ∘ duplicate)     wa  ↔  (duplicate ∘ (map φ))   wa  ↔  wwb

E como acontece com as mônadas, as duas formas podem ser convertidas automaticamente:

(map φ) wa    ↔  wa =>> (φ ∘ counit) wx
duplicate wa  ↔  wa =>> wx

wa =>> f(wx)  ↔  ((map f) ∘ duplicate) wa

Um exemplo simples é o comonad de Produto , que emite valores com base em um valor de entrada e dados de ambiente compartilhados. Na verdade, a Productcomônada é apenas o dual da Writermônada e efetivamente o mesmo que a Readermônada (ambos discutidos abaixo). Producte Readerdiferem apenas nas assinaturas de função que aceitam e como complementam essas funções envolvendo ou desembrulhando valores.

Um exemplo menos trivial é o comonad de Fluxo , que pode ser usado para representar fluxos de dados e anexar filtros aos sinais de entrada com extensão . Na verdade, embora não sejam tão populares quanto as mônadas, os pesquisadores descobriram que as comonadas são particularmente úteis para processamento de stream e modelagem de programação de fluxo de dados .

Devido às suas definições estritas, no entanto, não se pode simplesmente mover objetos para frente e para trás entre mônadas e comônadas. Como uma abstração ainda maior, as setas podem incluir ambas as estruturas, mas encontrar maneiras mais granulares de combinar código monádico e comonádico é uma área ativa de pesquisa.

Mais exemplos

Mônada de identidade

A mônada mais simples é a mônada de identidade , que apenas anota valores e funções simples para satisfazer as leis da mônada:

newtype Id T  =  T

unit(x)    =  x
(x >>= f)  =  f(x)

Identityna verdade, tem usos válidos, como fornecer um caso base para transformadores monad recursivos . Ele também pode ser usado para realizar atribuições básicas de variáveis ​​em um bloco de estilo imperativo.

Coleções

Qualquer coleção com um acréscimo adequado já é um monóide livre, mas não Listé a única coleção que também tem uma junção bem definida e se qualifica como uma mônada. Pode-se até mesmo sofrer mutação Listnessas outras coleções monádicas simplesmente impondo propriedades especiais ao apêndice :

Mônada IO (Haskell)

Como já mencionado, o código puro não deve ter efeitos colaterais não gerenciados, mas isso não impede que um programa descreva e gerencie explicitamente os efeitos. Essa ideia é central para a mônada IO de Haskell , onde um objeto do tipo IO apode ser visto como contendo o estado atual do mundo fora do programa e computando um valor do tipo a. Um cálculo que não calcula nenhum valor - isto é, um procedimento - tem o tipo IO (), "computando" o valor fictício (). Quando um programador associa um IOvalor a uma função, a função toma decisões com base nessa visão do mundo (entrada de usuários, arquivos, etc.) e, em seguida, produz um valor monádico refletindo o novo estado mundial (saída do programa).

Por exemplo, Haskell tem várias funções para atuar no sistema de arquivos mais amplo , incluindo uma que verifica se um arquivo existe e outra que exclui um arquivo. Seus dois tipos de assinaturas são:

doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

O primeiro está interessado em saber se um determinado arquivo realmente existe e, como resultado, produz um valor booleano dentro da IOmônada. A segunda função, por outro lado, está preocupada apenas em atuar no sistema de arquivos, de forma que o IOcontêiner de saída fique vazio.

IOnão se limita apenas a E / S de arquivo; ele ainda permite a E / S do usuário e, junto com o açúcar da sintaxe imperativa, pode imitar um típico "Hello, World!" programa :

main :: IO ()
main = do
  putStrLn "Hello, world!"
  putStrLn "What is your name, user?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

Desugar, isso se traduz no seguinte pipeline monádico ( >>em Haskell é apenas uma variante do bind para quando apenas os efeitos monádicos importam e o resultado subjacente pode ser descartado):

main :: IO ()
main =
  putStrLn "Hello, world!" >>
  putStrLn "What is your name, user?" >> 
  getLine >>= (\name ->
    putStrLn ("Nice to meet you, " ++ name ++ "!"))

Mônada de escritor (JavaScript)

Outra situação comum é manter um arquivo de log ou relatar o progresso de um programa. Às vezes, um programador pode querer registrar dados técnicos ainda mais específicos para posterior criação de perfil ou depuração . A mônada do gravador pode lidar com essas tarefas gerando uma saída auxiliar que se acumula passo a passo.

Para mostrar como o padrão de mônada não está restrito a linguagens principalmente funcionais, este exemplo implementa uma Writermônada em JavaScript . Primeiro, um array (com caudas aninhadas) permite construir o Writertipo como uma lista encadeada . O valor de saída subjacente viverá na posição 0 da matriz, e a posição 1 conterá implicitamente uma cadeia de notas auxiliares:

const writer = value => [value, []];

Definir a unidade também é muito simples:

const unit = value => [value, []];

Apenas uma unidade é necessária para definir funções simples que geram Writerobjetos com notas de depuração:

const squared = x => [x * x, [`${x} was squared.`]];
const halved = x => [x / 2, [`${x} was halved.`]];

Uma mônada verdadeira ainda requer vinculação , mas para Writerisso equivale simplesmente a anexar a saída de uma função à lista vinculada da mônada:

const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};

As funções de amostra agora podem ser encadeadas usando bind , mas definir uma versão de composição monádica (chamada pipelogaqui) permite aplicar essas funções de forma ainda mais sucinta:

const pipelog = (writer, ...transforms) =>
    transforms.reduce(bind, writer);

O resultado final é uma separação clara de preocupações entre percorrer os cálculos e registrá-los para auditar mais tarde:

pipelog(unit(4), squared, halved);
// Resulting writer object = [8, ['4 was squared.', '16 was halved.']]

Mônada do meio ambiente

Uma mônada de ambiente (também chamada de mônada de leitor e mônada de função ) permite que um cálculo dependa de valores de um ambiente compartilhado. O construtor do tipo mônada mapeia um tipo T para funções do tipo E → T , onde E é o tipo de ambiente compartilhado. As funções da mônada são:

${\ displaystyle {\ begin {array} {ll} {\ text {return}} \ dois pontos & T \ rightarrow E \ rightarrow T = t \ mapsto e \ mapsto t \\ {\ text {bind}} \ dois pontos & (E \ rightarrow T) \ rightarrow (T \ rightarrow E \ rightarrow T ') \ rightarrow E \ rightarrow T' = r \ mapsto f \ mapsto e \ mapsto f \, (r \, e) \, e \ end {array} }}$

As seguintes operações monádicas são úteis:

${\ displaystyle {\ begin {array} {ll} {\ text {perguntar}} \ dois pontos & E \ rightarrow E = {\ text {id}} _ {E} \\ {\ text {local}} \ dois pontos & ( E \ rightarrow E) \ rightarrow (E \ rightarrow T) \ rightarrow E \ rightarrow T = f \ mapsto c \ mapsto e \ mapsto c \, (f \, e) \ end {array}}}$

A operação ask é usada para recuperar o contexto atual, enquanto local executa um cálculo em um subcontexto modificado. Como em uma mônada de estado, os cálculos na mônada de ambiente podem ser invocados simplesmente fornecendo um valor de ambiente e aplicando-o a uma instância da mônada.

Formalmente, um valor em uma mônada de ambiente é equivalente a uma função com um argumento anônimo adicional; return e bind são equivalentes aos combinadores K e S , respectivamente, no cálculo do combinador SKI .

Mônadas estaduais

Uma mônada de estado permite que um programador anexe informações de estado de qualquer tipo a um cálculo. Dado qualquer tipo de valor, o tipo correspondente na mônada de estado é uma função que aceita um estado e, em seguida, produz um novo estado (do tipo s ) junto com um valor de retorno (do tipo t ). Isso é semelhante a uma mônada de ambiente, exceto que também retorna um novo estado e, portanto, permite a modelagem de um ambiente mutável .

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

Observe que essa mônada recebe um parâmetro de tipo, o tipo das informações de estado. As operações da mônada são definidas da seguinte forma:

-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

As operações de estado úteis incluem:

get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state

Outra operação aplica uma mônada estadual a um determinado estado inicial:

runState :: State s a -> s -> (a, s)
runState t s = t s

Os blocos do em uma mônada de estado são sequências de operações que podem examinar e atualizar os dados de estado.

Informalmente, uma mônada de estado do tipo S mapeia o tipo de valores de retorno T em funções do tipo , onde S é o estado subjacente. As funções de retorno e vinculação são: ${\ displaystyle S \ rightarrow T \ times S}$

${\ displaystyle {\ begin {array} {ll} {\ text {return}} \ dois pontos & T \ rightarrow S \ rightarrow T \ times S = t \ mapsto s \ mapsto (t, s) \\ {\ text {bind }} \ dois pontos & (S \ rightarrow T \ times S) \ rightarrow (T \ rightarrow S \ rightarrow T '\ times S) \ rightarrow S \ rightarrow T' \ times S \ = m \ mapsto k \ mapsto s \ mapsto (k \ t \ s ') \ quad {\ text {onde}} \; (t, s') = m \, s \ end {array}}}$.

Do ponto de vista da teoria das categorias, uma mônada de estado é derivada da adjunção entre o functor produto e o functor exponencial, que existe em qualquer categoria cartesiana fechada por definição.

Mônada de continuação

Uma mônada de continuação com tipo de retorno R mapeia o tipo T em funções do tipo . É usado para modelar o estilo de passagem de continuação . As funções return e bind são as seguintes: ${\ displaystyle \ left (T \ rightarrow R \ right) \ rightarrow R}$

${\ displaystyle {\ begin {array} {ll} {\ text {return}} \ dois pontos & T \ rightarrow \ left (T \ rightarrow R \ right) \ rightarrow R = t \ mapsto f \ mapsto f \, t \\ {\ text {bind}} \ dois pontos & \ left (\ left (T \ rightarrow R \ right) \ rightarrow R \ right) \ rightarrow \ left (T \ rightarrow \ left (T '\ rightarrow R \ right) \ rightarrow R \ right) \ rightarrow \ left (T '\ rightarrow R \ right) \ rightarrow R = c \ mapsto f \ mapsto k \ mapsto c \, \ left (t \ mapsto f \, t \, k \ right) \ fim {array}}}$

A função call-with-current-continuation é definida da seguinte forma:

${\ displaystyle {\ text {call / cc}} \ dois pontos \ \ left (\ left (T \ rightarrow \ left (T '\ rightarrow R \ right) \ rightarrow R \ right) \ rightarrow \ left (T \ rightarrow R \ right) \ rightarrow R \ right) \ rightarrow \ left (T \ rightarrow R \ right) \ rightarrow R = f \ mapsto k \ mapsto \ left (f \ left (t \ mapsto x \ mapsto k \, t \ right ) \, k \ right)}$

Registro de programa

O código a seguir é pseudocódigo. Suponha que temos duas funções fooe bar, com tipos

foo : int -> int
bar : int -> int

Ou seja, ambas as funções recebem um inteiro e retornam outro inteiro. Em seguida, podemos aplicar as funções em sucessão, como:

foo (bar x)

Onde o resultado é o resultado de fooaplicado ao resultado de baraplicado a x.

Mas suponha que estejamos depurando nosso programa e gostaríamos de adicionar mensagens de registro a fooe bar. Então, mudamos os tipos assim:

foo : int -> int * string
bar : int -> int * string

Para que ambas as funções retornem uma tupla, com o resultado da aplicação como o inteiro, e uma mensagem de registro com informações sobre a função aplicada e todas as funções aplicadas anteriormente como a string.

Infelizmente, isso significa que não podemos mais compor fooe bar, como seu tipo de entrada intnão é compatível com seu tipo de saída int * string. E embora possamos novamente ganhar composibilidade modificando os tipos de cada função a ser int * string -> int * string, isso exigiria que adicionássemos código clichê a cada função para extrair o inteiro da tupla, o que se tornaria tedioso à medida que o número de tais funções aumentasse.

Em vez disso, vamos definir uma função auxiliar para abstrair esse boilerplate para nós:

bind : int * string -> (int -> int * string) -> int * string

bindrecebe um inteiro e uma tupla de string e, a seguir, uma função (como foo) que mapeia de um inteiro para um inteiro e uma tupla de string. Sua saída é um inteiro e uma tupla de string, que é o resultado da aplicação da função de entrada ao inteiro dentro do inteiro de entrada e da tupla de string. Dessa forma, só precisamos escrever código padrão para extrair o inteiro da tupla uma vez, em bind.

Agora, recuperamos alguma composibilidade. Por exemplo:

bind (bind (x,s) bar) foo

Onde (x,s)está um inteiro e uma tupla de string.

Para tornar os benefícios ainda mais claros, vamos definir um operador infixo como um apelido para bind:

(>>=) : int * string -> (int -> int * string) -> int * string

Então t >>= fé o mesmo que bind t f.

Então, o exemplo acima se torna:

((x,s) >>= bar) >>= foo

Finalmente, seria bom não ter que escrever (x, "")toda vez que desejarmos criar uma mensagem de log vazia, onde ""está a string vazia. Então, vamos definir uma nova função:

return : int -> int * string

Que envolve xa tupla descrita acima.

Agora temos um bom pipeline para registrar mensagens:

((return x) >>= bar) >>= foo

Isso nos permite registrar mais facilmente os efeitos de bare fooem x.

int * stringé análogo a um valor monádico . binde returnsão análogos às funções correspondentes do mesmo nome. Na verdade, int * string, bind, e returnformar uma mônada.

Veja também

Alternativas para modelagem de cálculos:

• Os sistemas de efeitos são uma maneira diferente de descrever os efeitos colaterais como tipos
• Os tipos de exclusividade são uma terceira abordagem para lidar com os efeitos colaterais em linguagens funcionais

Conceitos de design relacionados:

• A programação orientada a aspectos enfatiza a separação do código de contabilidade auxiliar para melhorar a modularidade e a simplicidade
• Inversão de controle é o princípio abstrato de chamar funções específicas de uma estrutura abrangente
• As classes de tipo são um recurso de linguagem específico usado para implementar mônadas e outras estruturas em Haskell
• O padrão decorator é uma forma mais concreta e ad-hoc de obter benefícios semelhantes na programação orientada a objetos

Generalizações de mônadas:

• Os functores aplicativos generalizam a partir de mônadas, mantendo apenas a unidade e as leis relacionadas ao mapa
• As setas usam uma estrutura adicional para trazer funções simples e mônadas em uma única interface
• Transformadores de mônadas atuam em mônadas distintas para combiná-las de maneira modular

Notas

Referências

links externos

Referências HaskellWiki:

• " All About Monads " (originalmente por Jeff Newbern) - Uma discussão abrangente de todas as mônadas comuns e como elas funcionam em Haskell; inclui a analogia da "linha de montagem mecanizada".
• " Typeclassopedia " (originalmente por Brent Yorgey) - Uma exposição detalhada de como as principais typeclasses em Haskell, incluindo mônadas, se inter-relacionam.

Tutoriais:

• " A Fistful of Monads " (do livro didático Haskell online Learn You a Haskell for Great Good! - Um capítulo que apresenta as mônadas do ponto de partida do functor e typeclasses do functor aplicativo, incluindo exemplos.
• " For a Few Monads More " - Um segundo capítulo explicando mais detalhes e exemplos, incluindo uma Probabilitymônada para cadeias de Markov .
• " Functores, aplicativos e mônadas em imagens (por Aditya Bhargava) - Um tutorial rápido, bem-humorado e visual sobre mônadas.

Casos interessantes:

• " Canais de UNIX como mônadas de IO " (por Oleg Kiselyov) - Um pequeno ensaio que explica como os canos de Unix são efetivamente monádicos.
• Pro Scala: Padrões de Design Monadic para a Web (por Gregory Meredith) - Um manuscrito completo não publicado sobre como melhorar muitas facetas do desenvolvimento da web em Scala com mônadas.