Distinction between typeclasses MonadPlus, Alternative, and Monoid?

Solution 1:

MonadPlus and Monoid serve different purposes.

A Monoid is parameterized over a type of kind *.

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

and so it can be instantiated for almost any type for which there is an obvious operator that is associative and which has a unit.

However, MonadPlus not only specifies that you have a monoidal structure, but also that that structure is related to how the Monad works, and that that structure doesn't care about the value contained in the monad, this is (in part) indicated by the fact that MonadPlus takes an argument of kind * -> *.

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

In addition to the monoid laws, we have two potential sets of laws we can apply to MonadPlus. Sadly, the community disagrees as to what they should be.

At the least we know

mzero >>= k = mzero

but there are two other competing extensions, the left (sic) distribution law

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

and the left catch law

mplus (return a) b = return a

So any instance of MonadPlus should satisfy one or both of these additional laws.

So what about Alternative?

Applicative was defined after Monad, and logically belongs as a superclass of Monad, but largely due to the different pressures on the designers back in Haskell 98, even Functor wasn't a superclass of Monad until 2015. Now we finally have Applicative as a superclass of Monad in GHC (if not yet in a language standard.)

Effectively, Alternative is to Applicative what MonadPlus is to Monad.

For these we'd get

empty <*> m = empty

analogously to what we have with MonadPlus and there exist similar distributive and catch properties, at least one of which you should satisfy.

Unfortunately, even empty <*> m = empty law is too strong a claim. It doesn't hold for Backwards, for instance!

When we look at MonadPlus, the empty >>= f = empty law is nearly forced on us. The empty construction can't have any 'a's in it to call the function f with anyway.

However, since Applicative is not a superclass of Monad and Alternative is not a superclass of MonadPlus, we wind up defining both instances separately.

Moreover, even if Applicative was a superclass of Monad, you'd wind up needing the MonadPlus class anyway, because even if we did obey

empty <*> m = empty

that isn't strictly enough to prove that

empty >>= f = empty

So claiming that something is a MonadPlus is stronger than claiming it is Alternative.

Now, by convention, the MonadPlus and Alternative for a given type should agree, but the Monoid may be completely different.

For instance the MonadPlus and Alternative for Maybe do the obvious thing:

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

but the Monoid instance lifts a semigroup into a Monoid. Sadly because there did not exist a Semigroup class at the time in Haskell 98, it does so by requiring a Monoid, but not using its unit. ಠ_ಠ

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 is a stronger claim than Alternative, which in turn is a stronger claim than Monoid, and while the MonadPlus and Alternative instances for a type should be related, the Monoid may be (and sometimes is) something completely different.