Haskell/MonadPlus

From Wikibooks, open books for an open world
< Haskell
Jump to: navigation, search



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]

  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]).
  3. 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]

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