haskell - Monoide vs MonadPlus

monads typeclass

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Por qué MonadPlus y no Monad + Monoid? 2 respuestas

Soy muy nuevo tanto en Monads como en Monoids y recientemente también aprendí sobre MonadPlus . Por lo que veo, MonadPlus y MonadPlus proporcionan un tipo con una operación binaria asociativa y una identidad. (Llamaría a esto un semigrupo en lenguaje matemático). Entonces, ¿cuál es la diferencia entre MonadPlus y MonadPlus ?

Answer 1

Debo enfatizar la muy importante diferencia: a diferencia de Monoid, y a diferencia de lo que dicen las otras respuestas, MonadPlus no proporciona un tipo con una operación binaria asociada y la identidad. Haskell Report, el único documento que puede reclamar el estado de la Norma, no especifica las leyes de MonadPlus y, por lo tanto, no requiere que mplus sea asociativa o mzero sea su unidad izquierda o derecha. Quizás los autores todavía estaban debatiendo las leyes: hay muy buenas razones para que mplus no sea asociativo. Por ejemplo, si mplus es asociativo pero no conmutativo, el cálculo de búsqueda no determinista representado por MonadPlus no puede estar completo (es decir, existen soluciones que no podemos encontrar). Como es bastante raro que mplus sea conmutativo, MonadPlus no puede representar ningún procedimiento completo de búsqueda no determinista, si insistimos en la asociatividad. Ha habido una discusión detallada de este mismo tema de las leyes de MonadPlus en Carolina del Sur: debe ser siempre asociativo

Answer 2

Si tenemos que sostiene MonadPlus m , dirías que m es una Monad , pero ma (el tipo resultante de aplicar a a la "función" m ) es un monoide.

Si definimos (similar a la definición de Data.Monoid , pero la utilizaremos más adelante)

class Semigroup a where (<>) :: a -> a -> a
class Semigroup a => Monoid a where zero :: a

entonces tiene

mzero :: MonadPlus m => m a
mplus :: MonadPlus m => m a -> m a -> m a

Con tipos bastante comparables y las leyes apropiadas.

-- left and right identity
mplus a mzero == a
mplus mzero a == a
-- associativity
(a `mplus` b) `mplus` c == a `mplus` (b `mplus` c)

Incluso podemos definir un Haskell Monoid si usamos -XFlexibleInstances

{-# LANGUAGE FlexibleInstances #-}
instance MonadPlus m => Semigroup (m a) where (<>) = mplus
instance MonadPlus m => Monoid (m a) where zero = mzero

aunque estos se superponen mal con las instancias en Data.Monoid , que probablemente es la razón por la que no es una instancia estándar.

Otro ejemplo de un monoide como este es la Alternative m => ma de Control.Applicative .

Answer 3

Un semigroup es una estructura equipada con una operación binaria asociativa. Un monoid es un semigrupo con un elemento de identidad para la operación binaria.

Mónadas y semigrupos

Cada mónada tiene que adherirse a las leyes de la mónada . Para nuestro caso, lo importante es la ley de asociatividad. Expresado usando >>= :

(m >>= f) >>= g ≡ m >>= (/x -> f x >>= g)

Ahora apliquemos esta ley para deducir la asociatividad para >> :: ma -> mb -> mb :

(m >> n) >> p ≡ (m >>= /_ -> n) >>= /_ -> p
≡ m >>= (/x -> (/_ -> n) x >>= /_ -> p)
≡ m >>= (/x -> n >>= /_ -> p)
≡ m >>= (/x -> n >> p)
≡ m >> (n >> p)

(donde elegimos x para que no aparezca en m , n o p ).

Si nos especializamos >> en el tipo ma -> ma -> ma (sustituyendo b por a ), vemos que para cualquier tipo a la operación >> forma un semigrupo en ma . Como es cierto para cualquier a , obtenemos una clase de semigrupos indexados por a . Sin embargo, no son monoides en general, no tenemos un elemento de identidad para >> .

MonadPlus y monoides

MonadPlus agrega dos operaciones más, mplus y mzero . MonadPlus leyes de MonadPlus establecen explícitamente que mplus y mzero deben formar un monoide en ma para un arbitrario a . Entonces, nuevamente, obtenemos una clase de monoides indexados por a .

Note la diferencia entre MonadPlus y MonadPlus : Monoid dice que algún tipo único cumple con las reglas monoidales, mientras que MonadPlus dice que para todo lo posible, el tipo ma satisface las leyes monoidales. Esta es una condición mucho más fuerte.

Entonces, una instancia de MonadPlus forma dos estructuras algebraicas diferentes: una clase de semigrupos con >> y una clase de monoides con mplus y mzero . (Esto no es algo poco frecuente, por ejemplo, el conjunto de números naturales mayores que cero {1,2,...} forma un semigrupo con + y un monoide con × y 1 ).