terça-feira, 28 de agosto de 2018

Você Poderia Ter Inventado Mônadas! [Dan Piponi]

Você Poderia Ter Inventado Mônadas! (E Talvez Já O Tenha)

Você Poderia Ter Inventado Mônadas! (E Talvez Já O Tenha)

1 INTRO

Se você ainda não sacou, isto é sobre mônadas como elas aparecem em linguagens de programação funcional pura como Haskell. Elas são fortemente relacionadas com as mônadas da teoria de categorias, mas não são exatamente as mesmas porque Haskell não garante as identidades satisfeitas pelas mônadas categóricas.

Escrever introduções sobre mônadas parecem ter-se tornado uma indústria. Existe uma introdução gentil, uma introdução para programadores Haskell com os dizeres "Não entre em pânico", uma introdução para o "programador Haskell em produção" e infindáveis outras que introduzem mônadas como tudo desde um funtor até um tipo de traje espacial. 1

Mas todas elas introduzem mônadas como algo esotérico que necessita de explicação. Mas o que quero argumentar é que elas não são esotéricas afinal. De fato, diante de muitos problemas na programação funcional você já foi levado, inexoravelmente, a certas soluções, todas elas exemplos de mônadas. De fato, eu espero conseguir que você invente-as agora se é que já não as inventou. Será então um pequeno passo notar que todas essas soluções são de fato 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 vê como algo que já inventou.

Muitos dos problemas que mônadas tentam resolver são relacionados com a questão dos efeitos colaterais. Então nós começaremos com eles. (Note que mônadas te permitem fazer mais que manipular efeitos colaterais, em particular muitos tipos de objetos-contêiner podem ser vistos como mônadas. Algumas das introduções a mônadas creem ser difícil reconciliar estes dois usos distintos das mônadas e concentram-se em apenas um ou outro.)

2 Efeitos Colaterais: Depurando Funções Puras

Numa linguagem imperativa como C++, funções não agem nada parecido com as funções da matemática. Por exemplo, suponha que tenhamos uma função C++ que toma um simples argumento em ponto flutuante e retorna um resultado em ponto flutuante. Superficialmente ela pode parecer uma pequena função matemática mapeando reais em reais, mas uma função C++ pode fazer mais que apenas retornar um número que depende de seus argumentos. Ela pode ler e escrever valores em variáveis globais bem como escrever saída para a tela e receber entrada do usuário. Numa linguagem funcional pura, porém, uma função só pode ler o que é suprido em seus argumentos e a única maneira pela qual ela pode ter um efeito no mundo é mediante o valor que retorna.

Então, considere este problema numa linguagem funcional pura: temos funções f e g que levam float s em float s, mas gostaríamos de modificar estas funções para que também emitam strings para fins de depuração. Em Haskell, f e g podem ter tipos dados por 

f,g :: Float -> Float

Como podemos modificar os tipos de f e g para admitirem efeitos colaterais? Bem, realmente não existe escolha afinal. Se gostaríamos de ter f' e g' produzindo strings bem como números de ponto flutuante como saída, então a única forma possível é que estas strings sejam retornadas junto aos números de ponto flutuante. Em outras palavras, precisamos que f' e g' sejam do tipo 

f',g' :: Float -> (Float,String)

Podemos desenhar isso diagramaticamente como 

  x
  |
+---+
| f'|
+---+
 |  \ 
 |   |
f x  "f was called."

Podemos pensar nelas como 'funções depuráveis'.

Mas suponha agora que gostaríamos de depurar a composição de duas funções desse tipo. Nós poderíamos simplesmente compor nossas funções originais, f e g, para formar f . g. Mas nossas funções depuráveis não são tão imediatadas de se lidar. Nós gostaríamos que as strings retornadas por f' e g' fossem concatenadas numa grande string de depuração ( a de f' após a de g' ). Mas não podemos simplesmente compor f' e g' porque o valor de retorno de g' não é do mesmo tipo que o argumento de f'. Nós poderíamos escrever código num estilo como esse: 

let (y,s) = g' x
    (z,t) = f' y in (z,s++t)

Eis a aparência diagramática disso: 

     x
     |
   +---+
   | g'|
   +---+
    |   \   
  +---+  | "g was called."
  | f'|  |
  +---+  |
   | \   |
   |  \  |
   |  +----+
   |  | ++ |
   |  +----+
   |     |
f (g x) "g was called.f was called."

Isso é uma trabalheira toda vez que se precisa compor duas funções depuráveis, e se tivermos que implementar esse tipo de serviço de baixo nível 2 ao longo de todo o código, seria um porre. O que precisamos é definir uma função de ordem superior para realizar este serviço para nós. Como o problema é que a saída de g' não pode ser simplesmente inserida na entrada de f', precisamos 'melhorar' f'. Então introduziremos uma função `bind` para fazer isso. Em outras palavras, queremos 

bind f' :: (Float,String) -> (Float,String)

que implique em 

bind :: (Float -> (Float,String)) -> ((Float,String) -> (Float,String))

`bind` deve servir a dois propósitos:

  1. aplicar f' na parte correta de g' x, e
  2. concatenar a string retirnada por g' com a string retornada por f'.

Exercício 1

Escreva a função bind.

Solução 

bind f' (gx,gs) = let (fx,fs) = f' gx in (fx,gs++fs)

Dado um par de funções depuráveis, f' e g', agora podemos compô-las juntas para fazer uma nova função depurável bind f' . g'. Escreva essa composição como f' * g' . Mesmo que a saída de g' seja incompatível com a entrada de f', nós ainda temos uma maneira fácil de concatenar suas operações. E isto sugere outra questão: existe uma função depurável 'identidade'? A função identidade ordinária tem as seguintes propriedades: f . id = f e id . f = f. Assim, estamos procurando uma função depurável, chamemo-la unidade (unit), tal que unit * f = f * unit = f. Obviamente esperamos que ela produza a string de depuração vazia e em outros casos aja como a identidade.

Exercício 2

Defina a unidade.

Solução 

unit x = (x,"")

A unidade nos permite 'elevar' qualquer função em uma depurável. De fato, defina 

lift f x = (f x,"")

ou mais simplesmente lift f = unit . f. A versão elevada faz basicamente o mesmo da original e, bem razoavelmente, produz a string vazia como efeito colateral.

Exercício 3

Mostre que lift f * lift g = lift (f.g)

Em suma: as funções bind e unit nos permitem compor funções depuráveis de maneira direta, e compor funções ordinárias com funções depuráveis de uma maneira natural.

Acredite ou não, fazendo estes dois exercícios você já definiu sua primeira mônada. Neste ponto, provavelmente não está claro qual das estruturas que observamos é a mônada em si, ou com o que outras mônadas se parecem. Mas em vez de definir mônadas agora eu vou te deixar com mais alguns exercícios fáceis que te introduzirão a outras mônadas de tal maneira que você verá por si mesmo que esta é uma estrutura comum digna de um nome próprio. Também estou confiante que a maioria das pessoas, quando de frente com o problema original, eventualmente chegarão à função bind como uma forma de colar suas funções depuráveis. Então estou certo que você poderia ter inventado esta mônada mesmo que não notasse que era uma mônada.

3 Um Contêiner: Funções Multi-Valoradas

Considere as funções sqrt e cbrt que computam as raízes quadrada e cúbica, respectivamente, de um número real. Elas são funções comuns do tipo Float -> Float (apesar de que sqrt atirará uma exceção para argumentos negativos, algo que ignoraremos).

Agora considere uma versão dessas funções que trabalhe com números complexos. Cada complexo, além do zero, tem duas raízes quadradas. Da mesma forma, cada complexo não-nulo tem três raízes cúbicas. Então gostaríamos que sqrt' e cbrt' retornassem listas de valores. Em outras palavras, queremos 

sqrt',cbrt' :: Complex Float -> [Complex Float]

Vamos chamá-las de funções multi-valoradas.

Suponha que queremos determinar a raiz sexta de um número real. Nós podemos simplesmente concatenar as funções de raiz quadrada e raiz cúbica. Em outras palavras podemos definir sixthroot x = sqrt (cbrt x).

Mas como definimos uma função que encontra todas as raízes sextas de um número complexo usando sqrt' e cbrt'? Não podemos simplesmente concatenar estas funções. O que queremos é primeiro computar as raízes cúbicas de um número, e então encontrar as raízes quadradas de cada um destes números por vez, combinando os resultados em uma lista maior. O que precisamos é de uma função, vamos chamá-la bind, para compor estas funções, com declaração 

bind :: (Complex Double -> [Complex Double]) -> ([Complex Double] -> [Complex Double])

Eis um diagrama mostrando como é o processo. Nós queremos escrever cbrt' apenas uma vez mas ainda assim tê-lo aplicado a ambos os valores de sqrt'. 

       64
       |
    +------+
    + sqrt'+
    +------+
  +8 /    \ -8
+------+  +------+
| cbrt'|  | cbrt'|
+------+  +------+
 | | |      | | |
 2 . .     -2 . .

Exercício 4

Escreva uma implementação para bind.

Solução 

bind f x = concat (map f x)

Como escrevemos a função identidade na forma multi-valorada? A identidade retorna um argumento, então uma versão multi-valorada deve retornar uma lista de tamanho 1. Chamemos esta função unit.

Exercício 5

Defina unit.

Solução 

unit x = [x]

Novamente, defina f * g = bind f . g and lift f = unit . f. lift faz exatamente o que você poderia esperar. Ele transforma uma função ordinária em uma multi-valorada da maneira óbvia.

Exercício Seis

Mostre que f * unit = unit * f = f and lift f * lift g = lift (f.g)

Novamente dado o problema original, somos inexoravelmente levados a esta função bind.

Se você lidou com estes exercícios então você definiu sua segunda mônada. Você talvez esteja notando um padrão a se desenvolver. É curioso que estes dois problemas aparentemente tão diferentes tenham levado a construções similares.

4 Um Efeito Colateral Mais Complexo: Números Aleatórios

A função random em Haskell tem essa forma: 

random :: StdGen -> (a,StdGen)

A ideia é que para que se gere um número aleatório é necessário uma semente, e após ter gerado o número atualizar a semente com um novo valor. Em uma linguagem impura, a semente pode ser uma variável global, assim o usuário não precisa lidar diretamente com ela. Mas numa linguagem pura a semente precisa ser passada e recuperada explicitamente - e é isso que a assinatura de tipo de random descreve. Note que isto é similar ao caso da depuração acima porque estamos retornando dados extras usando um par. Mas desta vez estamos recebendo dados extras também.

Então uma função que é conceitualmente uma função randomizada a -> b pode ser escrita como uma função a -> b a -> StdGen -> (b,StdGen) onde StdGen é o tipo da semente.

Agora deveremos trabalhar como compor duas funções randomizadas, f e g. O primeiro elemento do par que f retorna precisa ser passado como uma entrada para g. Mas a semente passada de g também precisa ser passada para f. Enquanto isso o 'real' valor de retorno de g precisa ser passado como primeiro argumento de f. Assim nós podemos dar esta assinatura para bind: 

bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen))

Exercício 7

Implemente bind.

Solução 

bind f x seed = let (x',seed') = x seed in f x' seed'

Agora precisamos encontrar a função randomizada 'identidade'. Ela precisa ser do tipo 

unit :: a -> (StdGen -> (a,StdGen))

e deve deixar a semente intocada.

Exercício 8

Implemente unit.

Solução 

unit x g = (x,g)
# ou também
unit = (,)

Mais uma vez, defina f * g = bind f . g e lift f = unit . f . lift faz exatamente o que você poderia esperar - transforma uma função ordinária em uma randomizada que deixa a semente intocada.

Exercício 9

Mostre que f * unit = unit * f = f e lift f * lift g = lift (f.g).

5 Mônadas

Agora é hora de retornar e discernir a estrutura comum.

Defina 

type Debuggable a = (a,String)
type Multivalued a = [a]
type Randomised a = StdGen -> (a,StdGen)

Use a variável m para representar Debuggable, Multivalued ou Randomised. Em cada caso acabamos no mesmo problema. Nos é dada uma função a -> m b mas precisamos de alguma maneira aplicar esta função a um objeto do tipo m a em vez de um do tipo a. Em cada caso fazemos isso definindo uma função de nome bind com tipo (a -> m b) -> (m a -> m b) e introduzindo um tipo de função identidade unit :: a -> m a. Além disso, nós descobrimos que estas identidades valem: f * unit = unit * f = f e lift f * lift g = lift (f.g), onde * e lift foram definidas em termos de unit e bind.

Então agora eu posso revelar o que é uma mônada. A tripla de objetos (m,bind,unit) é a mônada, e para ser mônada deve satisfazer um punhado de leis como as que estivemos demonstrando. E eu penso que em cada um destes três casos você eventualmente viria com uma solução como bind, mesmo que possa não ter notado imediatamente que todos esses casos compartilham uma estrutura comum.

Pois agora eu preciso fazer algum contato com a definição usual das mônadas Haskell. A primeira coisa é que eu troquei a definição de bind e a escrevi com o nome 'bind', ao passo que normalmente escrita como o operador >>=. Então bind f x normalmente é escrito como x >> f=. A segunda é que unit geralmente é chamada return. E em terceiro lugar, a fim de sobrescrever os nomes >>= e return, precisamos fazer uso de classes de tipo. Em Haskell, Debuggable é a mônada Writer, Multivalued é a mônada List e Randomised é a mônada State. Se você conferir as definições dessas,

você notará que, excetuando algum floreio sintático, elas são essencialmente as definições que você escreveu para os exercícios acima. A depuração usou a mônada Writer, as funções multi-valoradas usaram a mônada List, e o gerador de números aleatórios usou a mônada State. Você poderia ter inventado mônadas!

6 Sintaxe da Mônada

Não quero perder tempo demais nisso (e você pode saltar esta seção) porque existem muitas excelentes introduções por aí.

Você já viu como a função bind pode prover uma bela forma de unir funções para te livrar de escrever um bom tanto de código feio. Haskell vai um passo além, você nem precisa usar a função bind explicitamente, você pode fazer que o Haskell a insira automaticamente em seu código.

Vamos retornar ao exemplo original de depuração, exceto que agora usaremos as classes de tipo oficiais de Haskell. Onde anteriormente nós usamos um par como (a,s) agora usaremos Writer (a,s) do tipo Writer Char. E para recuperar o par de um destes objetos usamos a função runWriter. Suponha que desejamos incrementar, duplicar e então decrementar 7, a cada estágio registrando o que fizemos. Nós podemos escrever 

return 7
  >>= (\x -> Writer (x+1,"inc."))
  >>= (\x -> Writer (2*x,"double."))
  >>= (\x -> Writer (x-1,"dec."))

Se aplicarmos runWriter a isso obteremos (15,"inc.double.dec."). Mas ainda está bem feio. Em vez disso podemos usar a sintaxe do de Haskell. A ideia é que 

do x <- y
   mais-codigo-aqui

é automaticamente reescrito pelo compilador para 

y >>= (\x -> do
          mais-codigo-aqui)

Similarmente, 

do
  let x = y
      mais-codigo-aqui

é reescrito como 

(\x -> do
    mais-codigo-aqui) y

E 

do
  expression

é deixado somente como expression.

Podemos agora reescrever o código acima como: 

do
    let x = 7
    y <- Writer (x+1,"inc\n")
    z <- Writer (2*y,"double\n")
         Writer (z-1,"dec\n")

A notação é bastante sugestiva. Quando escrevemos y <- ... é como se fingíssemos que a expressão do lado direito é meramente x+1 e que o efeito colateral simplesmente cuida de si mesmo.

Outro exemplo. Escreva o exemplo da raiz sexta na forma inconveniente: 

return 64 
  >>= (\x -> sqrt' x) 
  >>= (\y -> cbrt' y)

Agora podemos reescrever isso da forma legível 

do
    let x = 64
    y <- sqrt' x
    z <- cbrt' y
         return z

Nós podemos escrever o que parece um código ordinário não multi-valorado e as funções bind implícitas que Haskell insere automaticamente o tornam multi-valorado.

Inventar esta sintaxe foi um trabalho de gênio. Talvez você pudesse tê-la inventado, mas eu tenho certeza que eu não teria. Mas este material extra é mero açúcar sintático em cima das mônadas. Eu ainda afirmo que você poderia ter inventado as mônadas subjacentes.

7 Entrada&Saída

Existe agora uma última coisa a ser observada antes de você estar completamente qualificado em monadicidade. Interação com o mundo exterior. Até agora tudo o que eu tenho dito pode aplicar-se a qualquer linguagem funcional pura. Mas agora considere linguagens funcionais puras preguiçosas. Em uma tal linguagem, você não tem ideia de que ordem as coisas serão evaluadas. Então se você tem uma função para imprimir a mensagem "Insira um número" e outra para inserir o número, você pode não ser capaz de garantir que a mensagem será impressa antes da entrada ser requerida! Volte ao exemplo da função randomizada. Note como a semente randomizada acaba costurada ao longo das suas funções de modo que ela pode ser usada cada vez que random é chamada, Existe um tipo de ordenamento acontecendo. Suponha que tenhamos x >> f >>= g=. Como g usa a semente retornada por f, sabemos com certeza que f gerará seu número aleatório antes de g. Isto mostra que, em princípio, mônadas podem ser usadas para ordenar computações.

Agora considere a implementação de random no compilador. Ela é tipicamente uma rotina C ou ASM ligada no executável Haskell final. Se esta rotina fosse modificada de forma a realizar E/S poderíamos garantir que a E/S em f foi realizada antes daquela em g. Isto é exatamente como E/S funciona em Haskell, nós realizamos toda a E/S numa mônada. Neste caso, uma função que conceitualmente é do tipo a -> b mas também tem um efeito colateral no mundo real é na realidade do tipo a -> IO b. O tipo IO é uma caixa-preta, não precisamos saber como ela é. (Talvez ema funcione como o exemplo random, talvez não.) Nós apenas precisamos saber que x >> f >>= g= executa a E/S em f antes de g.

8 Teoria das Categorias

Uma última coisa. Mônadas são originalmente desenvolvidas no contexto da teoria das categorias. Vou deixar esta conexão para outro dia.

Oh!… e eu devo mencionar… ainda não estou convencido de que eu poderia inventar Sequências Espectrais. Mas ainda estou trabalhando nisso graças a Tim Chow.

9 Apêndice: Um Exemplo de Código Completo Usando Números Aleatórios

Primeiro, eis o código correspondente às definições acima: 

import Random

bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen))
bind f x seed = let (x',seed') = x seed in f x' seed'
unit x g = (x,g)
lift f = unit . f

Então eis o que faremos: queremos construir um número aleatório de dois dígitos em três passos. Começando de 0, nós vamos:

  1. adicionar um inteiro aleatório de 0 a 9
  2. multiplicá-lo por 10
  3. adicionar outro inteiro aleatório de 0 a 9

Conceitualmente esta operação é uma composição similar a addDigit . (*10) . addDigit. Mas nós sabemos que precisamos costurar a semente aleatória ao longo desse código. Primeiro, repare a real definição de addDigit: 

addDigit n g = let (a,g') = random g in (n + a `mod` 10,g')

Isto retorna um par consistindo de n+digitoAleatorio e a nova semente. Note como isto também recebe a nova semente como argumento. Pode-se dizer que 'conceitualmente' esta função é addDigit n = let a = random in n + a `mod` 10 e numa linguagem estrita e impura adequada isto seria considerado um código válido.

Agora considere a operação de multiplicar por 10. Esta é uma operação ordinária que podemos 'melhorar' usando lift. Então obtemos 

shift = lift (*10)

Agora o ponto crucial. Não podemos simplesmente compor, mas em vez disso devemos usar bind para converter nossas funções em uma forma que podem ser compostas. Então o conceitual addDigit . (*10) . addDigit torna-se 

test :: Integer -> StdGen ->  (Integer,StdGen)
test = bind addDigit . bind shift . addDigit

Agora criamos a semente usando meu número favorito e rodamos o código: 

g = mkStdGen 666
main = print $ test 0 g

Note que eu decidi não usar a classe de tipos Monad nativa de forma que nada ficasse oculto e que tudo estivesse explícito.

Atualização: Agradeço pelos comentários! Eu fiz uma série de consertos e adicionei um apêndice com um exemplo de números aleatórios. A maioria dos fragmentos de código agora foi copiada para o texto final em código real, então deve haver apenas alguns erros de digitação. Desculpas por qualquer confusão causada!

Para uma abordagem diferente sobre mônadas, eu escrevi um, pouco sobre as flechas de Kleisi. E se você estiver interessado em empilhar mônadas para obter mais funcionalidades, você pode tentar isso.

10 META

Table 1: META
Autor Dan Piponi
Título Original You Could Have Invented Monads! (And Maybe You Already Have.)
Link Original http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Link Arquivado http://archive.is/Jox0z

Footnotes:

1

Existe até uma página na Haskell Wiki dedicada a isso!

2

Não conheço termo melhor para plumbing - "encanamento", no sentido de "serviço de encanador/pedreiro"…

Created: 2018-08-28 ter 09:42

Validate

By -

Nenhum comentário:

Postar um comentário

Assinar: Postar comentários (Atom)

Entendendo o Combinador Y [hishamhm]

Entendendo, Finalmente, o Combinador Y - Uma Abordagem de uma Perspectiva Amigável a Programadores Entendendo, Finalmente, o...