Mônadas em Scheme (comp.lang.functional)
Table of Contents
Erann Gat escreveu:
Minha questão é: é possível apresentar e/ou explicar o conceito de mônada em Scheme? E se não, por que não? É porque Scheme não tem sistema de tipos, e tipos são parte e parcela do que mônadas são? Ou a essência das mônadas pode ser divorciada da teoria dos tipos?
É possível, mas não é a coisa mais divertida do mundo. Mônadas surgem da teoria das categorias, que é um ramo inerentemente tipado da matemática, e existem ligações bem próximas entre teoria das categorias e cálculo lambda tipado. Claro, você pode fazer isso em Scheme, mas será algo mais difícil de entender, dado que você terá que manter mais do código na sua mente e menos no código-fonte.
Mas vou dar uma palhinha – eu tenho pensado em escrever o que sei a fim de solidificar, e você me deu uma boa desculpa :)
- Questão: O que é uma mônada?
- Resposta: Mônadas são um conceito de teoria das categorias, que programadores funcionais adaptaram para criar um padrão de implementação 1 para bibliotecas de combinadores.
- Q: Então elas são nada mais que um padrão de implementação para funções de
ordem superior?
- R: Sim, basicamente. Elas são uma das ideias unificadoras em semântica de linguagens de programação, mas para hackers é basicamente um padrão de implementação.
- Q: Então, qual é a sintonia, Kenneth?
- R: Um, OK. Qualquer mônada consiste de quatro coisas:
Um construtor de tipo
M
que envia um tipoa
para os tiposM[a]
.Estes tipos não devem ser pensados como os tipos de Scheme como
string?
ouprocedure?
; em vez disso pense nelas mais como os tipos que programadores Scheme usam para especificar os argumentos para as funções (e.g. "uma lista de inteiros"). [{1}] Você pode lera
como "o tipoa
" eM[a]
como "o tipo de computações do tipoa
".- Uma função
unit
que tem tipoa -> M[a]
. Isto é, toma um valor do tipoa
e o injeta no tipo monádico. Uma função
bind
do tipo(M[a], a -> M[b]) -> M[b]
.bind
é uma função que toma dois argumentos - o primeiro é um valor monádico do tipoM[a]
e o segundo é uma função que dado uma
retorna um valor monádico do tipoM[b]
.Há três leis algébricas que
bind
eunit
devem obedecer. Em Scheme, estas equivalências são(bind (unit x) f) == (f x) (bind M unit) == M (bind (bind M f) g) == (bind M (lambda (x) (bind (f x) g)))
- R: Um, OK. Qualquer mônada consiste de quatro coisas:
- Q: Me dá um exemplo?
R: Claro! Eis a mônada mais simples possível - a mônada identidade:
(define (unit x) x) (define (bind m f) (f m))
Vou deixar a verificação de que
bind
eunit
satisfazem as leis das mônadas como exercício.
- Q: Isto foi trivial demais para ser útil. Que tal um exemplo menos inútil?
R: Que exigente. Temos a opção da mônada
maybe
, que representa computações que podem ou retornar um valor ou falhar com um erro.(define fail (vector 'fail)) ; fail não é eq? a nenhuma outra coisa (define (unit x) x) (define (bind m f) (if (eq? m fail) fail (f m)))
Novamente, eu deixarei a verificação das leis das mônadas para você, leitor.
- Q: Poderia explicar por que eu iria querer usar isso?
R: Tudo bem. Suponha que você tenha três funções
foo, bar, baz
, cada uma delas recebendo um valor (comfail
fora do domínio), e ou retornam ou falham retornandofail
. Agora, suponha que você quer compor estas três funções, de forma que qualquer falha cause a falha da composição. Assim, você escreve(define (foo-bar-baz x) (let ((foo-val (foo x))) (if (eq? foo-val fail) fail (let ((bar-val (bar foo-val))) (if (eq? bar-val fail) fail (baz bar-val))))))
Então você olha para esse código e suspira, pois ele é feio e não casa o conceito simples que você tinha em mente:
(define (concept-of-foo-bar-baz x) (baz (bar (foo x))))
Mas, já que você é um programador funcional, você sabe que pode usar o poder das funções de ordem superior:
(define (compose* f x) (if (eq? x fail) fail (f x))) (define (foo-bar-baz x) (compose* baz (compose* bar (foo x))))
Bem melhor. Mas espera! A função
compose*
é precisamente a operaçãobind
da mônadamaybe
!
- Q: Muito bonito. Mas você adicionou
fail
a esta API de uma maneira bem ad-hoc. Você tem que fazer isso com todas as mônadas?- R: É claro, todas as mônadas precisam ter algumas operações específicas para
o que quer que seja que você esteja empregando a mônada. Mas no caso da
mônada
option
,fail
é uma instância de um padrão muito comum chamado "mônadas com zeros". Uma mônada com zero tem dois elementos extras em sua API:- Um valor
zero
, do tipoM[a]
. - Uma função
plus
do tipo(M[a], M[a]) -> M[a]
. plus
ezero
precisam obedecer as leis algébricas a seguir:(plus m zero) == (plus zero m) == m (bind m (lambda (x) zero)) == zero (bind zero f) == zero
Assim podemos escrever para a mônada
maybe
:(define zero (vector 'Fail)) ; basta renomear 'fail' para 'zero' (define (plus a b) (if (eq? a zero) b a))
O
plus
da mônadamaybe
deveria ser um padrão bastante familiar para o programador Scheme; é exatamente como a forma especialor
funciona, exceto que seu valorzero
é#f
. É por isso que é tão reconfortante usar APIs que retornam#fr
em caso de falha e retornem um valor útil caso contrário.
- Um valor
- R: É claro, todas as mônadas precisam ter algumas operações específicas para
o que quer que seja que você esteja empregando a mônada. Mas no caso da
mônada
- Q: Existe algum outro exemplo de mônada com zero? Não é seguro generalizar de
um exemplo.
R: Certamente. Listas formam uma mônada com zero também. Observe:
(define (unit x) (list x)) (define (bind m f) (apply concatenate (map f m))) (define zero '()) (define (plus a b) (append a b))
Verifique as leis das mônadas e do zero!
- Q: Opções e listas são legais, tudo bem. Mas que papo é esse que eu ouço sobre
usar mônadas para tratar estado de maneira pura?
R: Comecemos com um exemplo. Suponha que você quer escrever uma função que recebe uma árvore binária e então numere as folhas. Para fazer isso com estado imperativo, você pode fazer uma caminhada na árvore e incrementar um contador a cada folha:
(define state 0) (define (number-tree tree) (if (pair? tree) (let* ((left-subtree (number-tree (car tree))) (right-subtree (number-tree (cdr tree)))) (cons left-subtree right-subtree)) (let ((n state)) (set! state (+ state 1)) n)))
Isto funciona mas não nos permite renumerar duas árvores começando do mesmo número. Então, se tentarmos fazer isso puramente, precisaremos escrever nosso laço em "estilo de passagem de estado", e entremear um contador ao longo do programa.
(define (number-tree tree state) (if (pair? tree) (let-values ((lft state-1) (number-tree (car tree) state)) (let-values ((rgt state-2) (number-tree (cdr tree) state-1)) (values (cons lft rgt) state-2))) (values (+ state 1) (+ state 1))))
A aparência disso é bem desagradável, e seria muito ruim se acidentalmente usássemos o estado atualizado errado. Porém, podemos usar uma mônada para automatizar o trabalho pesado, e obter o benefício de ambas as abordagens.
;; O construtor de tipo M[a] = state -> (a, state) (define (unit x) (lambda (state) (values x state))) ;; tudo o que bind faz é entremear o state (estado) ;; ao longo de algumas chamadas (define (bind m-a f) (lambda (state) (let-values ((a state*) (m-a state)) ((f a) state*)))) ;; get toma um state e o retorna como valor (define (get state) (values state state)) ;; set toma um state, e retorna um valor monádico ;; que substitui o velho state pelo novo (define (set new-state) (lambda (state) (values #f new-state))) ;; run toma um valor monádico state, e então ;; o executa com um estado inicial para obter um estado atual (define (run m state) (m state))
Agora vou definir o programa de numeração da árvore usando uma mônada
state
. Para torná-lo legível, eu vou usar uma indentação bastante excêntrica:(define (number-tree tree) (if (pair? tree) (begin (bind (number-tree (car tree)) (lambda (left-subtree) (bind (number-tree (cdr tree)) (lambda (right-subtree) (unit (car left-subtree right-subtree))))))) (begin (bind get (lambda (n) (bind (set (+ n 1)) (lambda (dont-care) (unit n))))))))
Compare esta com a versão iterativa:
(define state 0) (define (number-tree tree) (if (pair? tree) (let* ((left-subtree (number-tree (car tree))) (right-subtree (number-tree (cdr tree)))) (cons left-subtree right-subtree)) (let ((n state)) (set! state (+ state 1)) n)))
Estamos usando
bind + lambda
para simular o uso delet*
. Existe uma correspondência um-para-um entre os códigos monádico e imperativo! Neste ponto, a indentação excêntrica do código monádico sugere que seria útil definir uma macro para simplificar as coisas. (Esta macro eu roubei de um artigo do Oleg.)(define-syntax do (syntax-rules (def) ((do (v <- expr) rest) (bind expr (lambda (v) rest))) ((do expr) expr) ((do expr expr) (bind (set expr) (lambda (dummy) expr))) ((do expr expr* ...) (do expr (do expr* ...)))))
Isto emula a notação
do
de Haskell, que podemos usar assim:(define (number-tree tree) (if (pair? tree) (do (left-subtree <- (number-tree (car tree))) (right-subtree <- (number-tree (cdr tree))) (unit (cons left-subtree right-subtree))) (do (n <- get) (set (+ n 1)) (unit n))))
Legal, né?
- Q: Mó legal. Então um compilador Haskell toma programas usando a mônada
state
puramente funcional e internamente otimiza para um programa usando mutação?- R: Exatamente.
- Q: O que mais as mônadas podem fazer?
- R: Você também pode transformar programas no estilo de passagem de
continuação em forma monádica. De fato, é um resultado significativo (devido
a Andrezj Filinski) que todos os programas interativos utilizando
call/cc
e estado podem ser traduzidos para o estilo monádico, e vice-versa. Assim, exceções, não-determinismo, co-rotinas, dentre outros, têm todos uma expressão monádica.
- R: Você também pode transformar programas no estilo de passagem de
continuação em forma monádica. De fato, é um resultado significativo (devido
a Andrezj Filinski) que todos os programas interativos utilizando
- Q: Por que as descrições Haskell de mônadas focam tão pesadamente nesta
conversa estranha de "classes de tipos"?
R: Classes de tipos são apenas sobrecarga com esteroides, e cada mônada neste artigo tem suas próprias operações
bind
eunit
. Assim, haskelleiros sobrecarregambind
eunit
(que eles chamam>>=
ereturn
) para cada mônada que escrevem, de tal forma que seus códigos monádicos comprometam-se o mínimo possível com a mônada específica. É apenas uma prática boa e sólida de engenharia de software.Isso seria difícil de fazer em LISP (e.g. com o CLOS), por causa da operação
unit
– você teria que selecionar a operaçãounit
apropriada baseada no tipo esperado dereturn
, e isso é algo que inerentemente precisa de um sistema de tipos estático para funcionar.
1 META
Autor | Neelakantan Krishnaswami |
Link | https://groups.google.com/forum/message/raw?msg=comp.lang.functional/BH6gxLnjoHQ/gXxlxkVV3i8J |
Arquivo | http://archive.is/tlnh0 |
Footnotes:
Não sei como traduzir design pattern…
Created: 2018-11-09 sex 06:13
Nenhum comentário:
Postar um comentário