You may have noticed, whilst studying monads, that the Maybe and list monads are quite similar, in that they 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 or 1 result), and you use the list monad when you want to indicate a computation could have many valid answers (i.e. it could have 0 results -- a failure -- or many results).
Given two computations in one of these monads, it might be interesting to amalgamate all valid solutions into a single result. Taking the list monad as an example, given two lists of valid solutions we can simply concatenate the lists together to get all valid solutions. In such a context, it is also useful, especially when working with folds, to require a value corresponding to "zero results" (i.e. failure). For lists, the empty list represents zero results.
MonadPlus is a type class which captures these features in a general way.
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 as Maybe can only have up to one -- solution, 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) is similar to
Maybe in that it represents computations that can fail, but it allows the failing computations to include an error "message" (often, but not necessarily, a string). Typically,
Left s means a failed computation carrying an error message
Right x means a successful computation with result
Example: parallel parsing
A traditional way of parsing an input is to write functions which consume it, one character at a time. That is, they take an input string, then chop off ('consume') some characters from the front if they satisfy certain criteria (for example, you could write a function which consumes one uppercase character). However, if the characters on the front of the string don't satisfy these criteria, the parsers have failed, and therefore they make a valid candidate for a Maybe.
Here we use
mplus to run two parsers in parallel. That is, we use the result of the first one if it succeeds, but if not, we use the result of the second. If that too fails, then our whole parser returns
-- | Consume a digit in the input, and return the digit that was parsed. We use -- a do-block so that if the pattern match fails at any point, fail of -- the Maybe monad (i.e. Nothing) is returned. digit :: Int -> String -> Maybe Int digit i s | i > 9 || i < 0 = Nothing | otherwise = do let (c:_) = s if read [c] == i then Just i else Nothing -- | Consume a binary character in the input (i.e. either a 0 or an 1) 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, these laws aren't set in stone anywhere and aren't fully agreed on. The most common (but not universal) are 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 -- (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" are meant with exactly the same sense that addition of integer numbers is said to be associative and to have zero as neutral element. In fact, this analogy gives the names of
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, and therefore you'll sometimes see monads like IO being used as a MonadPlus. Consult All About Monads and the Haskell Wiki page on MonadPlus for extra more information about such issues.
Beyond the basic
mzero themselves, there are two other important general-purpose functions involving
A very common task when working with instances of MonadPlus is to 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
A nice way of thinking about this is that it generalises the list-specific
concat operation. Indeed, for lists, the two are equivalent. For Maybe it finds the first
Just x in the list, or returns
Nothing if there aren't any.
When discussing the list monad we noted how similar it was to list comprehensions, but we left the question of how to mirror list comprehension filtering in the list monad hanging. The
guard function allows us to do exactly that. Our example for this section will be the following comprehension, which retrieves all pythagorean triples (that is, trios of integer numbers which taken together are the lengths of the sides for some right triangle) in the obvious, brute-force way. It uses 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 looks like this:
guard :: MonadPlus m => Bool -> m () guard True = return () guard False = mzero
guard will reduce a do-block to
mzero if its predicate is
False. By the very 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 that, 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 False = 
guard blocks off a route. For example, 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 |__________________... | | | z 1 2 3 | |____ |__________ | | | | | | x 1 1 2 1 2 3 | |__ | |____ |__ | | | | | | | | | | | y 1 1 2 2 1 2 3 2 3 3
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.
- Prove the MonadPlus laws for Maybe and the list monad.
- We could augment our above parser to involve a parser for any character:
-- | Consume a given character in the input, and return the character we -- just consumed, paired with rest of the string. We use a do-block so that -- if the pattern match fails at any point, fail of the Maybe monad (i.e. -- Nothing) is returned. char :: Char -> String -> Maybe (Char, String) char c s = do let (c':s') = s if c == c' then Just (c, s') else NothingIt would then be possible to write a
hexCharfunction which parses any valid hexidecimal character (0-9 or a-f). Try writing this function (hint:
map digit [0..9] :: [String -> Maybe Int]).
- More to come...
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 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
, in the instance declaration. Monoids are not necessarily "containers" of anything, or parametrically polymorphic. The integer numbers, for instance, 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 there was a real need to take the trouble:
instance MonadPlus m => Monoid (m a) where mempty = mzero mappend = mplus
However, they work at different levels. As noted, 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, as they are monads, have kind * -> *.
- A fuller presentation of it will be given in a later chapter.