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 x
(where x
is the specific value of the computation). The Maybe
monad is illustrated by the two dialogues below:Scenario 1 | |
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. |
Scenario 2 | |
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 mplus
tries to choose a non-Nothing
value (roughly: "If a
is Nothing
, pick b
; otherwise
pick a
." Here's a question for you: what happens when both a
and b
are 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
So, now
madd
has 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 a
to the second argument (which is a function that converts an a
to 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 mplus
here 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:[3] `mplus` [] = [3]
Just 3 `mplus` Nothing = Just 3
But, on the other hand,
mplus
is differnet when handling non-base cases for the Maybe
and list monad types, for:[3] `mplus` [4] = [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 a
to the first argument (a function that converts the input value of type a
to the output of type c
), but if the answer from the third argument is of type Right b
, then feed b
to the second argument (a function that converts the input value of type b
to the output of type c
).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
MonadPlus
class and some of its powerful functions, such as msum
and guard
, and how the MonadPlus
class allows us to code in a declarative nondeterministic style.
3 comments:
Your blog keeps getting better and better! Your older articles are not as good as newer ones you have a lot more creativity and originality now keep it up!
Web design
very handy, thanx a lot for this blog -- This is exactlyy what I weas lookingfor.
Post a Comment