Distinção entre typeclasses MonadPlus, Alternative e Monoid?

83

As typeclasses Haskell da biblioteca padrão MonadPlus, Alternativee Monoidcada uma fornece dois métodos com essencialmente a mesma semântica:

  • Um valor vazio: mzero, empty, ou mempty.
  • Um operador a -> a -> aque une valores na typeclass juntos: mplus, <|>ou mappend.

Todos os três especificam essas leis às quais as instâncias devem obedecer:

mempty `mappend` x = x
x `mappend` mempty = x

Assim, parece que as três typeclasses estão fornecendo os mesmos métodos.

( Alternativetambém fornece somee many, mas suas definições padrão geralmente são suficientes e, portanto, não são muito importantes em termos desta questão.)

Então, minha pergunta é: por que essas três classes extremamente semelhantes? Existe alguma diferença real entre eles, além de suas diferentes restrições de superclasse?

00dani
fonte
Esta é uma boa pergunta. Em particular, Applicativee MonadPlusparecem ser exatamente os mesmos (restrições da superclasse do módulo).
Peter,
1
Há também ArrowZeroe ArrowPluspara flechas. Minha aposta: tornar as assinaturas de tipo mais limpas (o que torna as diferentes restrições de superclasse a verdadeira diferença).
Cat Plus Plus
2
@CatPlusPlus: bem, ArrowZeroe ArrowPluster tipo * -> * -> *, o que significa que você pode passá-los para o tipo de seta uma vez para uma função que precisa usá-los para uma infinidade de tipos, para usar um, Monoidvocê teria que exigir uma instância de Monoidpara cada particular instanciação, e você não tem garantia de que foram tratadas de maneira semelhante, as instâncias podem não estar relacionadas!
Edward KMETT

Respostas:

120

MonadPluse Monoidservem a diferentes propósitos.

A Monoidé parametrizado sobre um tipo de tipo *.

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m

e, portanto, pode ser instanciado para quase qualquer tipo para o qual haja um operador óbvio que seja associativo e que tenha uma unidade.

No entanto, MonadPlusnão especifica apenas que você tem uma estrutura monoidal, mas também que essa estrutura está relacionada a como Monadfunciona, e que essa estrutura não se preocupa com o valor contido na mônada, isso é (em parte) indicado pelo fato isso MonadPlusleva um argumento do tipo * -> *.

class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a

Além das leis monoidais, temos dois conjuntos potenciais de leis que podemos aplicar MonadPlus. Infelizmente, a comunidade discorda quanto ao que deveriam ser.

Pelo menos sabemos

mzero >>= k = mzero

mas há duas outras extensões concorrentes, a lei de distribuição de esquerda (sic)

mplus a b >>= k = mplus (a >>= k) (b >>= k)

e a esquerda pega a lei

mplus (return a) b = return a

Portanto, qualquer instância de MonadPlusdeve satisfazer uma ou ambas as leis adicionais.

Então sobre o quê Alternative?

Applicativefoi definido depois Monad, e logicamente pertence como uma superclasse de Monad, mas em grande parte devido às diferentes pressões sobre os designers em Haskell 98, ainda Functornão era uma superclasse de Monadaté 2015. Agora finalmente temos Applicativecomo uma superclasse de Monadem GHC (se não ainda em um padrão de idioma.)

Efetivamente, Alternativeé para o Applicativeque MonadPlusé Monad.

Para estes nós obteríamos

empty <*> m = empty

analogamente ao que temos com MonadPluse existem propriedades distributivas e de captura semelhantes, pelo menos uma das quais você deve satisfazer.

Infelizmente, mesmo a empty <*> m = emptylei é uma afirmação muito forte. Não vale para Backwards , por exemplo!

Quando olhamos para MonadPlus, a lei vazia >> = f = vazia é quase imposta a nós. A construção vazia não pode ter nenhum 'a's nela para chamar a função de fqualquer maneira.

No entanto, como nãoApplicative é uma superclasse de e não é uma superclasse de , acabamos definindo ambas as instâncias separadamente.MonadAlternativeMonadPlus

Além disso, mesmo se Applicativefosse uma superclasse de Monad, você acabaria precisando da MonadPlusclasse de qualquer maneira, porque mesmo se nós obedecêssemos

empty <*> m = empty

isso não é estritamente suficiente para provar que

empty >>= f = empty

Portanto, afirmar que algo é a MonadPlusé mais forte do que afirmar que é Alternative.

Agora, por convenção, o MonadPluse Alternativepara um determinado tipo devem concordar, mas o Monoidpode ser completamente diferente.

Por exemplo, o MonadPluse Alternativepara Maybefazem a coisa óbvia:

instance MonadPlus Maybe where
    mzero = Nothing
    mplus (Just a) _  = Just a
    mplus _        mb = mb

mas a Monoidinstância eleva um semigrupo em a Monoid. Infelizmente, porque não existia uma Semigroupclasse na época em Haskell 98, ele faz isso solicitando a Monoid, mas não usando sua unidade. ಠ_ಠ

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    mappend (Just a) (Just b) = Just (mappend a b)
    mappend Nothing x = x
    mappend x Nothing = x
    mappend Nothing Nothing = Nothing

TL; DR MonadPlus é uma afirmação mais forte do que Alternative, que por sua vez é uma afirmação mais forte do que Monoid, e embora as instâncias MonadPluse Alternativepara um tipo devam estar relacionadas, Monoidpode ser (e às vezes é) algo completamente diferente.

Edward KMETT
fonte
2
Excelente resposta, embora a última definição pareça estar errada, ela não satisfaz mempty `mappend` x ≡ x.
Vitus de
2
Ótima resposta. Alguém sabe de um tipo (comumente usado), que tem diferentes MonadPlus e Alternativeimplementações?
Peter,
7
@EdwardKmett: Esta resposta parece implicar que pode haver um Monadque é um, Alternativemas não um MonadPlus. Eu fiz uma pergunta sobre como encontrar um exemplo específico disso; se você conhece algum, adoraria ver.
Antal Spector-Zabusky
2
Você pode explicar a lei de captura esquerda para monadplus? Aparentemente, foi violado por []; deve [] realmente ignorar seu segundo argumento se o primeiro não estiver vazio?
ben w
4
A distribuição à esquerda de @benw é sem dúvida a lei mais sensata, mas não se aplica em alguns casos. A captura esquerda é uma lei alternativa que essas outras instâncias tendem a apoiar, mas que não é suportada pela maioria das outras. Conseqüentemente, nós realmente temos 2 conjuntos de leis amplamente não relacionados sendo implementados por instâncias diferentes, então MonadPlusduas classes estão realmente disfarçadas como uma porque a maioria das pessoas não se importa.
Edward KMETT