MonadPlus (Solutions) Monads Understanding monads Maybe List `do` notation IO State Additive monads (MonadPlus) Monad transformers edit this chapter

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.

## DefinitionEdit

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

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 parsingEdit

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

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

```mzero >>= f  =  mzero
m >> mzero   =  mzero
```

And the HaskellWiki page cites another (with controversy):

```(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k)
```

## Useful functionsEdit

Beyond the basic `mplus` and `mzero`, there are two other general-purpose functions involving `MonadPlus`:

### msumEdit

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

### guardEdit

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

The `guard` function works like this:

```guard :: MonadPlus m => Bool -> m ()
guard True  = return ()
guard _ = mzero
```

Concretely, `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 `(>>=)`, an `mzero` at any point will cause the entire do-block 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 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
|____________________________________________ ...
|                     |                    |
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
2. 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 hexadecimal character (0-9 or a-f). Try writing this function (hint: `map digit [0..9] :: [String -> Maybe Int]`).

## Relationship with monoidsEdit

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

## Notes

 MonadPlus Solutions to exercises Monads Understanding monads  >> Maybe >> List  >> `do` notation  >> IO >> State  >> Additive monads (MonadPlus)  >> Monad transformers edit this chapter Haskell edit book structure