¿Distinción entre las clases de tipos MonadPlus, Alternative y Monoid?

83

Las clases de tipos de Haskell de la biblioteca estándar MonadPlus, Alternativey Monoidcada una proporciona dos métodos con esencialmente la misma semántica:

  • Un valor vacío: mzero, emptyo mempty.
  • Un operador a -> a -> aque une los valores de la clase de tipos juntos: mplus, <|>o mappend.

Los tres especifican estas leyes a las que deben adherirse las instancias:

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

Por lo tanto, parece que las tres clases de tipos proporcionan los mismos métodos.

( Alternativetambién proporciona somey many, pero sus definiciones predeterminadas suelen ser suficientes, por lo que no son demasiado importantes en términos de esta pregunta).

Entonces, mi consulta es: ¿por qué estas tres clases extremadamente similares? ¿Existe alguna diferencia real entre ellos, además de sus diferentes restricciones de superclase?

00dani
fuente
Buena pregunta. En particular, Applicativey MonadPlusparecen ser exactamente iguales (restricciones de superclase de módulo).
Peter
1
También hay ArrowZeroy ArrowPluspara flechas. Mi apuesta: hacer que las firmas de tipos sean más limpias (lo que hace que las diferentes restricciones de superclase sean la diferencia real).
Cat Plus Plus
2
@CatPlusPlus: bueno, ArrowZeroy ArrowPlustener tipo * -> * -> *, lo que significa que puede pasarlos por el tipo de flecha una vez para una función que necesita usarlos para una multitud de tipos, para usar un Monoidtendría que requerir una instancia de Monoidpara cada particular instanciación, y no tendría garantía de que se manejaran de manera similar, ¡las instancias podrían no estar relacionadas!
Edward KMETT

Respuestas:

120

MonadPlusy Monoidsirven para diferentes propósitos.

A Monoidestá parametrizado sobre un tipo de género *.

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

y así se puede instanciar para casi cualquier tipo para el que existe un operador obvio que es asociativo y que tiene una unidad.

Sin embargo, MonadPlusno solo especifica que tienes una estructura monoidal, sino también que esa estructura está relacionada con cómo Monadfunciona, y que a esa estructura no le importa el valor contenido en la mónada, esto está (en parte) indicado por el hecho eso MonadPlusrequiere un argumento de tipo * -> *.

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

Además de las leyes de monoides, tenemos dos conjuntos de leyes potenciales a las que podemos aplicar MonadPlus. Lamentablemente, la comunidad no está de acuerdo con lo que deberían ser.

Al menos sabemos

mzero >>= k = mzero

pero hay otras dos extensiones en competencia, la ley de distribución izquierda (sic)

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

y la ley de captura de la izquierda

mplus (return a) b = return a

Por tanto, cualquier instancia de MonadPlusdebería satisfacer una o ambas de estas leyes adicionales.

¿Y qué pasa Alternative?

Applicativese definió después Monad, y lógicamente pertenece como una superclase de Monad, pero en gran parte debido a las diferentes presiones sobre los diseñadores en Haskell 98, ni siquiera Functorfue una superclase de Monadhasta 2015. Ahora finalmente tenemos Applicativecomo superclase de Monaden GHC (si no aún en un idioma estándar.)

Efectivamente, Alternativees a Applicativelo que MonadPluses Monad.

Por estos obtendríamos

empty <*> m = empty

de manera análoga a lo que tenemos con MonadPlusy existen propiedades distributivas y de captura similares, al menos una de las cuales debe satisfacer.

Desafortunadamente, incluso la empty <*> m = emptyley es una afirmación demasiado fuerte. ¡No es válido para Backwards , por ejemplo!

Cuando miramos a MonadPlus, la ley de vacío >> = f = vacío casi se nos impone. La construcción vacía no puede tener ninguna 'a' para llamar a la función fde todos modos.

Sin embargo, dado que Applicativees no una superclase de Monady Alternativees no una superclase de MonadPlus, terminamos definiendo ambos casos por separado.

Además, incluso si Applicativefuera una superclase de Monad, terminarías necesitando la MonadPlusclase de todos modos, porque incluso si obedeciéramos

empty <*> m = empty

eso no es estrictamente suficiente para demostrar que

empty >>= f = empty

Entonces, afirmar que algo es un MonadPluses más fuerte que afirmar que lo es Alternative.

Ahora, por convención, MonadPlusy Alternativepara un tipo dado deberían coincidir, pero Monoidpueden ser completamente diferentes.

Por ejemplo, el MonadPlusy Alternativepara Maybehacer lo obvio:

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

pero la Monoidinstancia eleva un semigrupo a un Monoid. Lamentablemente, debido a que no existía una Semigroupclase en ese momento en Haskell 98, lo hace solicitando a Monoid, pero sin usar su unidad. ಠ_ಠ

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 es un reclamo más fuerte que Alternative, que a su vez es un reclamo más fuerte que Monoid, y aunque las instancias MonadPlusy Alternativepara un tipo deben estar relacionadas, Monoidpuede ser (y a veces es) algo completamente diferente.

Edward KMETT
fuente
2
Excelente respuesta, sin embargo, la última definición parece estar equivocada, no satisface mempty `mappend` x ≡ x.
Vitus
2
Gran respuesta. ¿Alguien sabe de un tipo (de uso común) que tiene diferentes MonadPlus e Alternativeimplementaciones?
Peter
7
@EdwardKmett: Esta respuesta parece implicar que podría haber un Monadque es un Alternativepero no un MonadPlus. Hice una pregunta sobre cómo encontrar un ejemplo específico de esto; si conoces alguno, me encantaría verlo.
Antal Spector-Zabusky
2
¿Puede explicar la ley de captura a la izquierda para monadplus? Aparentemente es violada por []; ¿debería [] ignorar realmente su segundo argumento si el primero no está vacío?
ben w
4
La distribución izquierda de @benw es posiblemente la ley más sensata, pero no se cumple en algunos casos. la captura izquierda es una ley alternativa que esas otras instancias tienden a apoyar, pero que no son compatibles con la mayoría de las demás. En consecuencia, realmente tenemos 2 conjuntos de leyes en gran medida no relacionados que se implementan en diferentes instancias, por MonadPluslo que en realidad hay dos clases disfrazadas como una porque a la mayoría de las personas no les importa.
Edward KMETT