Os candidatos compõem, as mônadas não

110

Os candidatos compõem, as mônadas não.

O que significa a afirmação acima? E quando um é preferível ao outro?

faltando faktor
fonte
5
De onde você tirou essa declaração? Pode ser útil ver algum contexto.
fuz
@FUZxxl: Eu ouvi isso repetidamente de muitas pessoas diferentes, recentemente do debasishg no Twitter.
missingfaktor
3
@stephen tetley: Observe que muitos desses Applicatives são, na verdade, uma família inteira de Monads, a saber, um para cada "forma" de estrutura possível. ZipListnão é a Monad, mas ZipLists de comprimento fixo são. Readeré um caso especial conveniente (ou geral?) em que o tamanho da "estrutura" é fixado como a cardinalidade do tipo de ambiente.
CA McCann de
3
@CAMcCann Todos esses aplicativos rápidos (truncados ou preenchidos) restringem-se a mônadas se você fixar a forma de uma forma que equivale a uma Readermônada até o isomorfismo. Depois de fixar a forma de um contêiner, ele codifica efetivamente uma função a partir de posições, como um memorando. Peter Hancock chama esses functores de "Naperian", pois eles obedecem às leis dos logaritmos.
pigworker
4
@stephen tetley: Outros exemplos incluem o aplicativo de monóide constante (que é uma composição de mônadas, mas não uma mônada) e o aplicativo de retardo de unidade (que é melhor não admitir junção).
pigworker

Respostas:

115

Se compararmos os tipos

(<*>) :: Applicative a => a (s -> t) -> a s -> a t
(>>=) :: Monad m =>       m s -> (s -> m t) -> m t

temos uma pista do que separa os dois conceitos. Isso (s -> m t)no tipo de (>>=)mostra que um valor em spode determinar o comportamento de um cálculo em m t. Mônadas permitem interferência entre as camadas de valor e computação. O (<*>)operador não permite essa interferência: os cálculos da função e do argumento não dependem de valores. Isso realmente incomoda. Comparar

miffy :: Monad m => m Bool -> m x -> m x -> m x
miffy mb mt mf = do
  b <- mb
  if b then mt else mf

que usa o resultado de algum efeito para decidir entre dois cálculos (por exemplo, lançar mísseis e assinar um armistício), enquanto

iffy :: Applicative a => a Bool -> a x -> a x -> a x
iffy ab at af = pure cond <*> ab <*> at <*> af where
  cond b t f = if b then t else f

que usa o valor de abpara escolher entre os valores de dois cálculos ate af, tendo realizado ambos, talvez com efeito trágico.

A versão monádica depende essencialmente do poder extra de (>>=)escolher um cálculo a partir de um valor, e isso pode ser importante. No entanto, apoiar esse poder torna as mônadas difíceis de compor. Se tentarmos construir 'double-bind'

(>>>>==) :: (Monad m, Monad n) => m (n s) -> (s -> m (n t)) -> m (n t)
mns >>>>== f = mns >>-{-m-} \ ns -> let nmnt = ns >>= (return . f) in ???

chegamos até aqui, mas agora nossas camadas estão todas misturadas. Temos um n (m (n t)), então precisamos nos livrar do exterior n. Como diz Alexandre C, podemos fazer isso se tivermos um adequado

swap :: n (m t) -> m (n t)

permutar o ninterior e joino outro n.

O mais fraco 'dupla aplicação' é muito mais fácil de definir

(<<**>>) :: (Applicative a, Applicative b) => a (b (s -> t)) -> a (b s) -> a (b t)
abf <<**>> abs = pure (<*>) <*> abf <*> abs

porque não há interferência entre as camadas.

Da mesma forma, é bom reconhecer quando você realmente precisa da potência extra de Monads e quando pode se safar com a estrutura de computação rígida que o Applicativesuporta.

Observe, a propósito, que embora compor mônadas seja difícil, pode ser mais do que você precisa. O tipo m (n v)indica computação com m-effects e, em seguida, computação com n-effects para um -value v, em que m-effects termina antes de n-effects iniciar (daí a necessidade de swap). Se você deseja apenas intercalar m-effects com n-effects, então composição talvez seja pedir demais!

trabalhador de porco
fonte
3
Para o exemplo duvidoso, você afirma que "usa o valor de ab para escolher entre os valores de dois cálculos at e af, tendo realizado ambos, talvez com um efeito trágico". A natureza preguiçosa de Haskell não protege você contra isso? Se eu tiver list = (\ btf -> if b then t else f): [] e, em seguida, execute a instrução: list <*> pure True <*> pure "hello" <*> pure (erro "bad"). ... recebo "olá" e o erro nunca ocorre. Este código não é tão seguro ou controlado como uma mônada, mas a postagem parece sugerir que os aplicativos causam uma avaliação rigorosa. No geral, ótimo post! Obrigado!
shj
7
Você ainda obtém os efeitos de ambos, mas puro (erro "ruim") não tem nenhum. Se, por outro lado, você tentar iffy (puro True) (puro "olá") (erro "ruim"), você obterá um erro que o miffy evita. Além disso, se você tentar algo como duvidoso (puro verdadeiro) (puro 0) [1,2], você obterá [0,0] em vez de [0]. Os aplicativos têm um certo rigor sobre eles, na medida em que constroem sequências fixas de cálculos, mas os valores resultantes desses cálculos ainda são combinados preguiçosamente, como você pode observar.
pigworker
É verdade que para qualquer mônada me nvocê sempre pode escrever um transformador de mônada mte operar n (m t)usando mt n t? Então você sempre pode compor mônadas, só é mais complicado, usando transformadores?
ron
4
Esses transformadores costumam existir, mas, pelo que eu sei, não há uma maneira canônica de gerá-los. Freqüentemente, há uma escolha genuína sobre como resolver os efeitos intercalados das diferentes mônadas, sendo o exemplo clássico as exceções e o estado. Uma exceção deve reverter o estado de mudança ou não? Ambas as escolhas têm seu lugar. Dito isso, há uma coisa de "mônada livre" que expressa "intercalação arbitrária". data Free f x = Ret x | Do (f (Free f x)), então data (:+:) f g x = Inl (f x) | Tnr (g x), e considere Free (m :+: n). Isso atrasa a escolha de como executar as intercalações.
pigworker de
@pigworker Sobre o debate preguiçoso / estrito. Eu acho que com aplicativos você não pode controlar o efeito de dentro do cálculo, mas a camada de efeito pode muito bem decidir não avaliar os valores posteriores. Para analisadores (aplicativos), isso significa que, se o analisador falhar antes, os analisadores subsequentes não serão avaliados / aplicados à entrada. Pois Maybeisso significa que um início Nothingsuprimirá a avaliação ade um posterior / subsequente Just a. Isso está correto?
ziggystar
75

Os candidatos compõem, as mônadas não.

Mônadas fazer compor, mas o resultado pode não ser uma mônada. Em contraste, a composição de dois aplicativos é necessariamente um aplicativo. Suspeito que a intenção da declaração original era que "A aplicatividade compõe, enquanto a monadilidade não". Reformulado, " Applicativeestá fechado na composição, e Monadnão está."

Conal
fonte
24
Além disso, quaisquer dois aplicativos compõem de maneira totalmente mecânica, enquanto a mônada formada pela composição de duas mônadas é específica dessa composição.
Apocalisp de
12
Além disso, as mônadas compõem de outras maneiras, o produto de duas mônadas é uma mônada, apenas os coprodutos precisam de algum tipo de lei distributiva.
Edward KMETT de
Com @Apocalisp, comentário incluído, esta é a melhor e mais concisa resposta.
Paul Draper
39

Se você tiver aplicativos A1e A2, o tipo data A3 a = A3 (A1 (A2 a))também será aplicativo (você pode escrever uma instância desse tipo de forma genérica).

Por outro lado, se você tiver mônadas M1e M2o tipo data M3 a = M3 (M1 (M2 a))não for necessariamente uma mônada (não há implementação genérica sensata para >>=ou joinpara a composição).

Um exemplo pode ser o tipo [Int -> a](aqui compomos um construtor de tipo []com (->) Int, ambos os quais são mônadas). Você pode escrever facilmente

app :: [Int -> (a -> b)] -> [Int -> a] -> [Int -> b]
app f x = (<*>) <$> f <*> x

E isso se generaliza para qualquer aplicativo:

app :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)

Mas não há uma definição sensata de

join :: [Int -> [Int -> a]] -> [Int -> a]

Se você não está convencido disso, considere esta expressão:

join [\x -> replicate x (const ())]

O comprimento da lista retornada deve ser definido em pedra antes que um inteiro seja fornecido, mas o comprimento correto dela depende do inteiro fornecido. Portanto, nenhuma joinfunção correta pode existir para este tipo.

Rotsor
fonte
1
... então evite mônadas quando uma função serve?
andrew cooke de
2
@andrew, se você quis dizer functor, então sim, functores são mais simples e devem ser usados ​​quando suficientes. Observe que nem sempre é. Por exemplo, IOsem um Monadseria muito difícil de programar. :)
Rotsor
17

Infelizmente, nosso objetivo real, a composição de mônadas, é bem mais difícil. .. De fato, podemos realmente provar que, em certo sentido, não há como construir uma função de junção com o tipo acima usando apenas as operações das duas mônadas (veja o apêndice para um esboço da prova). Segue-se que a única maneira pela qual podemos esperar formar uma composição é se houver algumas construções adicionais ligando os dois componentes.

Compondo mônadas, http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf

Landei
fonte
4
Tl; dr para leitores impacientes: você pode compor mônadas se (f?) Puder fornecer uma transformação naturalswap : N M a -> M N a
Alexandre C.
@Alexandre C .: Apenas "se", eu suspeito. Nem todos os transformadores de mônadas são descritos pela composição do functor direto. Por exemplo, ContT r m anão é m (Cont r a)nem Cont r (m a), e StateT s m aé aproximadamente Reader s (m (Writer s a)).
CA McCann de
@CA McCann: Não consigo ir de (M mônada, N mônada, MN mônada, NM mônada) para (existe troca: MN -> NM natural). Então vamos ficar com o "se" por enquanto (talvez a resposta esteja no jornal, devo confessar que pesquisei rapidamente)
Alexandre C.
1
@Alexandre C .: Apenas especificar que as composições são mônadas pode não ser suficiente - você também precisa de alguma forma de relacionar as duas partes com o todo. A existência de swapimplica que a composição permite que os dois "cooperem" de alguma forma. Além disso, observe que sequenceé um caso especial de "troca" para algumas mônadas. Então é flip, na verdade.
CA McCann de
7
Para escrever swap :: N (M x) -> M (N x), parece-me que você pode usar returns(adequadamente fmapped) para inserir um Mna frente e um Natrás, partindo de e N (M x) -> M (N (M (N x))), em seguida, usar o joindo composto para obter o seu M (N x).
Pigworker
7

A solução de lei distributiva l: MN -> NM é suficiente

para garantir a monadicidade do NM. Para ver isso você precisa de uma unidade e um mult. Vou me concentrar no mult (a unidade é unit_N unitM)

NMNM - l -> NNMM - mult_N mult_M -> NM

Isso não garante que o MN seja uma mônada.

A observação crucial, no entanto, entra em jogo quando você tem soluções de direito distributivo

l1 : ML -> LM
l2 : NL -> LN
l3 : NM -> MN

assim, LM, LN e MN são mônadas. A questão que surge é se LMN é uma mônada (seja por

(MN) L -> L (MN) ou por N (LM) -> (LM) N

Temos estrutura suficiente para fazer esses mapas. No entanto, como Eugenia Cheng observa , precisamos de uma condição hexagonal (que equivale a uma apresentação da equação de Yang-Baxter) para garantir a monadicidade de qualquer construção. Na verdade, com a condição hexagonal, as duas mônadas diferentes coincidem.

user278559
fonte
9
Esta é provavelmente uma ótima resposta, mas passou voando pela minha cabeça.
Dan Burton
1
Isso porque, usando o termo Applicative e haskell tag, esta é uma pergunta sobre haskell, mas com uma resposta em uma notação diferente.
codeshot