Haskell/MonadPlus
In our studies so far, we saw that the Maybe and list monads both represent the number of results a computation can have. That is, you use Maybe when you want to indicate that a computation can fail somehow (i.e. it can have 0 results or 1 result), and you use the list monad when you want to indicate a computation could have many valid answers ranging from 0 results to many results.
Given two computations in one of these monads, it might be interesting to amalgamate all valid solutions into a single result. For example, within the list Monad, we can concatenate two lists of valid solutions.
Definition[edit]
MonadPlus
defines two methods. mzero
is the monadic value standing for zero results; while mplus
is a binary function which combines two computations.
class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a > m a > m a
Here are the two instance declarations for Maybe
and the list monad:
instance MonadPlus [] where
mzero = []
mplus = (++)
instance MonadPlus Maybe where
mzero = Nothing
Nothing `mplus` Nothing = Nothing  0 solutions + 0 solutions = 0 solutions
Just x `mplus` Nothing = Just x  1 solution + 0 solutions = 1 solution
Nothing `mplus` Just x = Just x  0 solutions + 1 solution = 1 solution
Just x `mplus` Just y = Just x  1 solution + 1 solution = 2 solutions,
 but Maybe can only have up to one solution,
 so we disregard the second one.
Also, if you import Control.Monad.Error, then (Either e)
becomes an instance:
instance (Error e) => MonadPlus (Either e) where
mzero = Left noMsg
Left _ `mplus` n = n
Right x `mplus` _ = Right x
Like Maybe
, (Either e)
represents computations that can fail. Unlike Maybe
, (Either e)
allows the failing computations to include an error "message" (which is usually a String). Typically, Left s
means a failed computation carrying an error message s
, and Right x
means a successful computation with result x
.
Example: parallel parsing[edit]
Traditional input parsing involves functions which consume an input one character at a time. That is, a parsing function takes an input string and chops off (i.e. 'consumes') characters from the front if they satisfy certain criteria. For example, you could write a function which consumes one uppercase character. If the characters on the front of the string don't satisfy the given criteria, the parser has failed; so such functions are candidates for Maybe.
Let's use mplus
to run two parsers in parallel. That is, we use the result of the first one if it succeeds, and otherwise, we use the result of the second. If both fail, then our whole parser returns Nothing
.
In the example below, we consume a digit in the input and return the digit that was parsed.
digit :: Int > String > Maybe Int
digit i s  i > 9  i < 0 = Nothing
 otherwise = do
let (c:_) = s
if [c] == show i then Just i else Nothing
Our guards assure that the Int
we are checking for is a single digit. Otherwise, we are just checking that the first character of our String matches the digit we are checking for. If it passes, we return the digit wrapped in a Just
. The doblock assures that any failed pattern match will result in returning Nothing
.
We can use our digit
function with mplus
to parse Strings of binary digits:
binChar :: String > Maybe Int
binChar s = digit 0 s `mplus` digit 1 s
Parser libraries often make use of MonadPlus
in this way. If you are curious, check the (+++)
operator in Text.ParserCombinators.ReadP, or (<>)
in Text.ParserCombinators.Parsec.Prim.
The MonadPlus laws[edit]
Instances of MonadPlus are required to fulfill several rules, just as instances of Monad are required to fulfill the three monad laws. Unfortunately, the MonadPlus laws aren't fully agreed on. The most common approach says that mzero and mplus form a monoid. By that, we mean:
 mzero is a neutral element
mzero `mplus` m = m
m `mplus` mzero = m
 mplus is associative
 (but not all instances obey this law because it makes some infinite structures impossible)
m `mplus` (n `mplus` o) = (m `mplus` n) `mplus` o
There is nothing fancy about "forming a monoid": in the above, "neutral element" and "associative" here is just like how addition of integer numbers is said to be associative and to have zero as neutral element. In fact, this analogy is the source of the names mzero
and mplus
.
The Haddock documentation for Control.Monad quotes additional laws:
mzero >>= f = mzero
m >> mzero = mzero
And the HaskellWiki page cites another (with controversy):
(m `mplus` n) >>= k = (m >>= k) `mplus` (n >>= k)
There are even more sets of laws available. Sometimes monads like IO are used as a MonadPlus. Consult All About Monads and the Haskell Wiki page on MonadPlus for more information about such issues.
Useful functions[edit]
Beyond the basic mplus
and mzero
, there are two other generalpurpose functions involving MonadPlus
:
msum[edit]
A common task when working with MonadPlus: take a list of monadic values, e.g. [Maybe a]
or [[a]]
, and fold it down with mplus
. The function msum
fulfills this role:
msum :: MonadPlus m => [m a] > m a
msum = foldr mplus mzero
In a sense, msum
generalizes the listspecific concat
operation. Indeed, the two are equivalent when working on lists. For Maybe, msum
finds the first Just x
in the list and returns Nothing
if there aren't any.
guard[edit]
When discussing the list monad we noted how similar it was to list comprehensions, but we didn't discuss how to mirror list comprehension filtering. The guard
function allows us to do exactly that.
Consider the following comprehension which retrieves all pythagorean triples (i.e. trios of integer numbers which work as the lengths of the sides for a right triangle). First we'll examine the bruteforce approach. We'll use a boolean condition for filtering; namely, Pythagoras' theorem:
pythags = [ (x, y, z)  z < [1..], x < [1..z], y < [x..z], x^2 + y^2 == z^2 ]
The translation of the comprehension above to the list monad is:
pythags = do
z < [1..]
x < [1..z]
y < [x..z]
guard (x^2 + y^2 == z^2)
return (x, y, z)
The guard
function works like this:
guard :: MonadPlus m => Bool > m ()
guard True = return ()
guard _ = mzero
Concretely, guard
will reduce a doblock to mzero
if its predicate is False
. Given the first law stated in the 'MonadPlus laws' section above, an mzero
on the lefthand side of an >>=
operation will produce mzero
again. As doblocks are decomposed to lots of expressions joined up by (>>=)
, an mzero
at any point will cause the entire doblock to become mzero
.
To further illustrate, we will examine guard
in the special case of the list monad, extending on the pythags
function above. First, here is guard
defined for the list monad:
guard :: Bool > [()]
guard True = [()]
guard _ = []
Basically, guard
blocks off a route. In pythags
, we want to block off all the routes (or combinations of x
, y
and z
) where x^2 + y^2 == z^2
is False
. Let's look at the expansion of the above do
block to see how it works:
pythags =
[1..] >>= \z >
[1..z] >>= \x >
[x..z] >>= \y >
guard (x^2 + y^2 == z^2) >>= \_ >
return (x, y, z)
Replacing >>=
and return
with their definitions for the list monad (and using some letbindings to keep it readable), we obtain:
pythags =
let ret x y z = [(x, y, z)]
gd z x y = concatMap (\_ > ret x y z) (guard $ x^2 + y^2 == z^2)
doY z x = concatMap (gd z x) [x..z]
doX z = concatMap (doY z ) [1..z]
doZ = concatMap (doX ) [1..]
in doZ
Remember that guard
returns the empty list in the case of its argument being False
. Mapping across the empty list produces the empty list, no matter what function you pass in. So the empty list produced by the call to guard
in the binding of gd
will cause gd
to be the empty list, and therefore ret
to be the empty list.
To understand why this matters, think about listcomputations as a tree. With our Pythagorean triple algorithm, we need a branch starting from the top for every choice of z
, then a branch from each of these branches for every value of x
, then from each of these, a branch for every value of y
. So the tree looks like this:
start ____________________________________________ ...    x 1 2 3 _______________ ... _______________ ... _______________ ...          y 1 2 3 2 3 4 3 4 5 ___...___...___... ___...___...___...___...___...___...                            z 1 2 3 2 3 4 3 4 5 2 3 4 3 4 5 4 5 6 3 4 5 4 5 6 5 6 7
Each combination of x, y and z represents a route through the tree. Once all the functions have been applied, each branch is concatenated together, starting from the bottom. Any route where our predicate doesn't hold evaluates to an empty list, and so has no impact on this concat operation.
Exercises 


Relationship with monoids[edit]
When discussing the MonadPlus laws, we alluded to the mathematical concept of monoids. It turns out that there is a Monoid
class in Haskell, defined in Data.Monoid. A fuller presentation of will be given in a later chapter. For now, a minimal definition of Monoid
implements two methods; namely, a neutral element (or 'zero') and an associative binary operation (or 'plus').
class Monoid m where
mempty :: m
mappend :: m > m > m
For example, lists form a simple monoid:
instance Monoid [a] where
mempty = []
mappend = (++)
Sounds familiar, doesn't it? In spite of the uncanny resemblance to MonadPlus
, there is a subtle yet key difference. Note the usage of [a]
instead of []
in the instance declaration. Monoids are not necessarily "containers" of anything or parametrically polymorphic. For instance, the integer numbers on form a monoid under addition with 0 as neutral element.
In any case, MonadPlus
instances look very similar to monoids, as both feature concepts of zero and plus. Indeed, we could even make MonadPlus
a subclass of Monoid
if it were worth the trouble:
instance MonadPlus m => Monoid (m a) where
mempty = mzero
mappend = mplus
Note
Due to the "free" type variable a
in the instance definition, the snippet above is not valid Haskell 98. If you want to test it, you will have to enable the GHC language extension FlexibleInstances:
 If you are testing with GHCi, start it with the command line option XFlexibleInstances or interactively type
:set XFlexibleInstances
.  Alternatively, if you are running a compiled program, add
{# LANGUAGE FlexibleInstances #}
to the top of your source file.
Again, Monoid
s and MonadPlus
work at different levels. As noted before, there is no requirement for monoids to be parameterized in relation to "contained" or related type. More formally, monoids have kind *, but instances of MonadPlus
(which are monads) have kind * > *.