Appropriate uses of Monad `fail` vs. MonadPlus `mzero`

Question

This is a question that has come up several times for me in the design code, especially libraries. There seems to be some interest in it so I thought it might make a good community wiki.

The fail method in Monad is considered by some to be a wart; a somewhat arbitrary addition to the class that does not come from the original category theory. But of course in the current state of things, many Monad types have logical and useful fail instances.

The MonadPlus class is a sub-class of Monad that provides an mzero method which logically encapsulates the idea of failure in a monad.

So a library designer who wants to write some monadic code that does some sort of failure handling can choose to make his code use the fail method in Monad or restrict his code to the MonadPlus class, just so that he can feel good about using mzero, even though he doesn't care about the monoidal combining mplus operation at all.

Some discussions on this subject are in this wiki page about proposals to reform the MonadPlus class.

---

So I guess I have one specific question:

What monad instances, if any, have a natural fail method, but cannot be instances of MonadPlus because they have no logical implementation for mplus?

But I'm mostly interested in a discussion about this subject. Thanks!

---

EDIT: One final thought occured to me. I recently learned (even though it's right there in the docs for fail) that monadic "do" notation is desugared in such a way that pattern match failures, as in (x:xs) <- return [] call the monad's fail.

It seems like the language designers must have been strongly influenced by the prospect of some automatic failure handling built in to haskell's syntax in their inclusion of fail in Monad.

Answer 1

In this answer, I want to discuss the topic, why fail isa member of Monad. I don't want to add this to my other answer, since it covers another topic.

---

Although the mathematical definition of a monad doesn't contains fail, the creators of Haskell 98 put it into the Monad typeclass. Why?

In order to ease the usage of monads and to make it easier to abstract the usage of monads, they introduced the do notation, a very useful piece of sugar. For example, this code:

do putStr "What's your full name? "
   [name,surname] <- getLine >>= return . words
   putStr "How old are you? "
   age <- getLine >>= return . read
   if age >= 18
      then putStrLn $ "Hello Mr / Ms " ++ surname
      else putStrLn $ "Hello " ++ name

translates to:

putStr "What's your full name? " >>
getLine >>= return . words >>= \[name,surname] ->
putSr "How old are you? " >>
getLine >>= return . read >>= \age ->
if age >= 18
   then putStrLn $ "Hello Mr / Ms " ++ surname
   else putStrLn $ "Hello " ++ name

What's the problem here? Imagine you have a name with a space in between, like Jon M. Doe. In this case, the whole construct will be _|_. Sure, you can work around this by adding some ad-hoc function with let, but this is pure boilerplate. At the time Haskell 98 was created, there wasn't an exception system like today, where you could simply catch the failed pattern matching. Also, incomplete patterns are considered bad coding style.

What's the solution? The creators of Haskell 98 added a special function fail, called in the case of a mismatch. The desugaring looks somewhat like this:

putStr "What's your full name? " >> let
  helper1 [name,surname] =
    putSr "How old are you? " >> let
      helper2 age =
        if age >= 18
           then putStrLn $ "Hello Mr / Ms " ++ surname
           else putStrLn $ "Hello " ++ name
      helper2 _ = fail "..."
    in getLine >>= return . read >>= helper2
  helper1 _ = fail "..."
in getLine >>= return . words >>= helper1

(I'm not sure whether there is really a helper2, but I think so)

If you look twice at this, you'll find out how smart it is. First, there's never an incomplete pattern match, and second you can make fail configurizable. To achieve this, they just put fail into the monads definition. For example, for Maybe, fail is simply Nothing and for the instance of Either String, it's Left. This way, it's easy to write monad-independent monadic code. For instance, for a long time lookup was defined as (Eq a,Monad b) => a -> [(a, b)] -> m b, and lookup returned fail if there wasn't a match.

Now, there's still the big question in the Haskell community: isn't it a bad idea to add something completely independent to the Monad typeclass like fail? I can't answer this question, but IMHO this decision was right, as other places aren't that comfortable for fail.

Answer 2

Think of Either. It's monadic instance looks like this:

{-# LANGUAGE FlexibleInstances #-}
instance Monad (Either String) where
  (Left x) >>= _   = Left x
  (Right a)  >>= f = f a
  return           = Right
  fail             = Left

(We need FlexibleInstances in order to allow an instance like Either String)
So it's basically like Maybe with an optional error message if something happens. You can't recreate this with mzero, as you can't add an error message to the failure. It's somewhat different from fail.

Each instance of mplus should satisfy these two laws:

mzero `mplus` a -> a
a `mplus` mzero -> a

Simple, isn't it? But these laws make mplus special. With them, it's possible to write a reasonable MonadPlus instance for it:

instance MonadPlus (Either a) where
  mzero = Left undefined
  mplus (Left _) b = b
  mplus a _        = a

What is this? It represents a choice. If the first computation is successful, it will be returned. Else, mplus returns the second computation. Note how it differs from (>>), which doesn't satisfies the laws:

Left a   >>    Right b -> Left a
Left a `mplus` Right b -> Right b

(>>) will stop on the first computation, while mplus tries the second one instead. [] also behaves like this:

[] >> [1..4] -> []
[] `mplus` [1..4] -> [1,2,3,4]

This is just to discuss the aspects of MonadPlus and specially the aspect of mplus in contrast to (>>).