# Haskell/MonadPlus

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.

## 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 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

Remember that `(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 `s`

, and `Right x`

means a successful computation with result `x`

.

## Example: parallel parsing[edit]

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 `Nothing`

.

-- | 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

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, 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 `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, 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.

## Useful functions[edit]

Beyond the basic `mplus`

and `mzero`

themselves, there are two other important general-purpose functions involving `MonadPlus`

:

### msum[edit]

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 `mplus`

. `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.

### guard[edit]

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

Concretely, `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 `(>>=)`

, an `mzero`

at any point will cause the entire do-block to become `mzero`

.

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`

, `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 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

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 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.

## Exercises[edit]

- 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 Nothing

It would then be possible to write a`hexChar`

function 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[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.^{[1]} 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]`

, not `[]`

, 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

*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`. - Alternatively, if you are running a compiled program, add
`{-# LANGUAGE FlexibleInstances #-}`

to the top of your source file.

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 * -> *.

## Notes[edit]

- ↑ A fuller presentation of it will be given in a later chapter.