*deterministic*, meaning that the computation occurs in only one way. As we have seen, monads can be helpful with this kind of computation. But monads can be helpful with

*nondeterministic*computations, or computations that proceed along multiple possible paths, as we shall see.

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