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.
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
(Either e) represents computations that can fail. Unlike
(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
Right x means a successful computation with result
Example: parallel parsing
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.
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
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 do-block assures that any failed pattern match will result in returning
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
The MonadPlus laws
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
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)
Beyond the basic
mzero, there are two other general-purpose functions involving
A common task when working with MonadPlus: take a list of monadic values, e.g.
[Maybe a] or
[[a]], and fold it down with
msum fulfills this role:
msum :: MonadPlus m => [m a] -> m a msum = foldr mplus mzero
In a sense,
msum generalizes the list-specific
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.
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 brute-force 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)
guard function works like this:
guard :: MonadPlus m => Bool -> m () guard True = return () guard _ = mzero
guard will reduce a do-block to
mzero if its predicate is
False. Given the first law stated in the 'MonadPlus laws' section above, an
mzero on the left-hand side of an
>>= operation will produce
mzero again. As do-blocks are decomposed to lots of expressions joined up by
mzero at any point will cause the entire do-block to become
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 _ = 
guard blocks off a route. In
pythags, we want to block off all the routes (or combinations of
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)
return with their definitions for the list monad (and using some let-bindings 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
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 list-computations 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.
Relationship with monoids
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
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 * -> *.