Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Distinction between typeclasses MonadPlus, Alternative, and Monoid?

The standard-library Haskell typeclasses MonadPlus, Alternative, and Monoid each provide two methods with essentially the same semantics:

  • An empty value: mzero, empty, or mempty.
  • An operator a -> a -> a that joins values in the typeclass together: mplus, <|>, or mappend.

All three specify these laws to which instances should adhere:

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

Thus, it seems the three typeclasses are all providing the same methods.

(Alternative also provides some and many, but their default definitions are usually sufficient, and so they're not too important in terms of this question.)

So, my query is: why have these three extremely similar classes? Is there any real difference between them, besides their differing superclass constraints?

like image 789
00dani Avatar asked Apr 16 '12 01:04

00dani


1 Answers

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.

like image 168
Edward Kmett Avatar answered Sep 28 '22 18:09

Edward Kmett