Last modified on 8 July 2014, at 11:50

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

The MonadPlus lawsEdit

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 extra more information about such issues.

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
  1. Prove the MonadPlus laws for Maybe and the list monad.
  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 hexidecimal 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, Monoids 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 * -> *.


NotesEdit