Haskell comes with three kinds of monads that have been used specifically for nondeterministic computation: the Maybe monad, the list data type and, a new one, the Either monad.
We saw the first one in the previous post: the Maybe monad. This monad type has two instances: Nothing and Just
xis the specific value of the computation). The Maybe monad is illustrated by the two dialogues below:
|Waiter:||How is the pork chop, can I get you anything to go with that?|
|Custamah:||Oh, Nothing for me, thanks.|
|Waiter:||Wonderful, enjoy your meal.|
|Waiter:||How is the pork chop, can I get you anything to go with it?|
|Custamah:||Oh, Just a small bowl of applesauce, please?|
|Waiter:||Sure, I'll bring that right out.|
The waiter in the above two scenarios doesn't know exactly what the customer will want, but that waiter is pretty sure the customer will ask for Nothing or for Just something, and these options describe the Maybe monad type.
Another example of this kind of monad is the list data type. But whereas the Maybe monad allows two options (the answer or failure), the list data type (a monad) allows multiple answers (including no answers, which is represented by the empty list). These kinds of monads form a protocol called the MonadPlus class, just as the more general monad data types form the more general protocol of the Monad class, and just like regular monads, conform to a set of laws.
First, let us specify and explain what the MonadPlus protocol is. All MonadPlus types must have the following two properties defined:
mzero :: m a— the base, or usually interpreted as fail, value; and,
mplus :: m a → m a → m a— a function that chooses a success value when offered two values
For the Maybe MonadPlus type the above properties are defined as follows:
mzero = Nothing
Nothing `mplus` b = b
a `mplus` b = a
In other words, Nothing is the failure case, and
mplustries to choose a non-Nothing value (roughly: "If
ais Nothing, pick
b; otherwise pick
a." Here's a question for you: what happens when both
bare Nothing, and for what reason?) Note the interesting semantics of
mplus— it is not at all addition, as we expect, for:
Just 3 `mplus` Just 4 = Just 3
Recall that if we wish to do monadic addition, we need to define such an operator.
madd :: (Monad m, Num a) ⇒ m a → m a → m a
madd = liftM2 (+)
Just 3 `madd` Just 4 = Just 7
maddhas the triple meaning here: it is not
mplus(which is not addition), it is addition for monads containing numbers, and it either heightens awareness or annoys the cause of "MADD". Got all that?
The Maybe type has a special handler, called maybe. Its type signature is:
maybe :: b → (a → b) → Maybe a → b
What does this function do? Well, we've already seen it in action with the monadic Ackermann and Fibonacci solutions. One can read the arguments from right to left, to get the feel of an if-then-else: if the last argument is Just
a, then pass
ato the second argument (which is a function that converts an
ato the proper return type); else execute the first argument. A very compact and useful function when working with Maybe types.
The second most commonly used data type used for non-deterministic computation is the list MonadPlus data type. It has an interesting variation from the Maybe definition:
mzero = 
mplus = (++)
In other words, the empty list (
) is the base (failure) case, and
mplushere actually is addition ('concatenation', to be technically correct); addition, that is, in the list-sense. But it all works out, particularly when it comes to the base cases, for:
 `mplus`  = 
Just 3 `mplus` Nothing = Just 3
But, on the other hand,
mplusis different when handling non-base cases for the Maybe and list monad types, for:
 `mplus`  = [3, 4]
Just 3 `mplus` Just 4 = Just 3
But this difference is consistent with the different types: the list monad allows for multiple solutions, whereas the Maybe monad allows only one.
The list data type has too many special functions associated with it to review in this post. I recommend a review of the Haskell online report to get a taste of list's rich functionality, and then read Eric Kidd's post on backtracking with monads for some insights into using list monads in nondeterministic programming.
The third data type that is used, albeit less frequently, for non-deterministic computation is the Either data type. It's structure is as follows:
data Either a b = Left a | Right b
The way Either operates is that it offers a mutually-exclusive choice. For example, little Isabel sits to my Left and her até Elena Marie sits to my Right, so at 4 p.m. I must choose Either one to serve tea first: Left Isabel or Right ElenaMarie.
The interesting distinction of the Either monad to MonadPlus types such as the list data type and the Maybe monad is that both options are weighed equally, or, more to the point, neither is considered to be the base case. This means that Either, qua Either, is not in the MonadPlus class. With this caveat, can the Either type be used for non-deterministic computation? Yes, absolutely!
Not only can the Either type be used in its basic monadic form, but it also can be coerced into the MonadPlus class. How? It's simple, really. By simply choosing one of the branches to be the base (the Haskell library designers chose Left), the Either type now conforms to that protocol. The convention assigns the error message (a String) to the Left and the value sought is assigned to the Right one. This rather reduces Either to a glorified, error-handling, Maybe, and that is how it is used in every-day Haskell code for the most part.
The Either monad also has a special handler, either, with the type signature of:
either :: (a → c) → (b → c) → Either a b → c
This function is in the same vein as the Maybe handler, but complicated by the fact that maybe has only one (success) type to handle, whereas this function has two possible types it deals with — either's type translates as: if the answer from the third argument (Either
a b) is Left
a, then feed
ato the first argument (a function that converts the input value of type
ato the output of type
c), but if the answer from the third argument is of type
Right b, then feed
bto the second argument (a function that converts the input value of type
bto the output of type
What we've seen in this entry is an introduction to the MonadPlus class and three examples of monads that allow for choice, Maybe, the list data type and Either, and saw an example for each which demonstrated their ability to code with choice.
The next entry will further explore the
MonadPlusclass and some of its powerful functions, such as
msumand guard, and how the MonadPlus class allows us to code in a declarative nondeterministic style.