Practical Fun with Monads --- Introducing: MonadPlus!

Monads. Haskell’s famous for them, but they are one of the most ill-understood concepts to the public. They are mostly shrouded in mystery because of their association with how Haskell models I/O. This reputation is undeserved. Monads don’t have anything to do with I/O.

This series is a part of a global effort to pull away the shroud of mystery behind monads and show that they are fun! And exciting! And really just a way of chaining together functions that allow for new ways of approaching puzzles.

The first sub-series (chapter?) will be on a specific class/family of monads known as MonadPlus. At the end of it all, we are going to be solving the classic logic puzzle, as old as time itself, using only the List monad instance, and no loops, queues, or fancy stuff like that:

A farmer has a wolf, a goat, and a cabbage that he wishes to transport across a river. Unfortunately, his boat can carry only one thing at a time with him. He can’t leave the wolf alone with the goat, or the wolf will eat the goat. He can’t leave the goat alone with the cabbage, or the goat will eat the cabbage. How can he properly transport his belongings to the other side one at a time, without any disasters?

Let us enter a brave new world!

A quick review of monads

Okay, so as a Haskell blogger, I’m actually not allowed to write any monad tutorials. Luckily for you, however, I don’t need too — there are a wealth of great ones. Adit provides a great concise one, and, if you want, a more in depth one is on the haskell.org wiki about all sorts of monads and using them in real life.

Remember — different monads do not actually have any non-superficial relationship to one another. When we say monads, we just mean objects for which we have defined a way to chain together functions “inside” wrappers, containers, or contexts.

Maybe, maybe not

Monads are very useful when you are dealing with objects that are containers. Let’s look at the most obvious container – a Maybe a. A Maybe a is a container that can either be Just x (representing a successful result x of type a) or a Nothing (representing a failed result).

Often times you’ll have functions that fail, and you want to chain them. The easiest way is that any function that is chained onto a failed value will be skipped; a failure is the final result.

Consider the halve function, which returns Just (x `div` 2) on a successful halving, or Nothing on an unsuccessful halving:

halve :: Int -> Maybe Int                       -- 1
halve x | even x    = Just (x `div` 2)          -- 2
        | otherwise = Nothing                   -- 3

Because Maybe comes built-in as a monad, we can now chain halves on results of other halves, and have any failures automatically propagate to the end and short circuit your entire computation:

ghci> halve 8
Just 4
ghci> halve 7
Nothing
ghci> halve 8 >>= halve
Just 2
ghci> halve 7 >>= halve
Nothing                         -- 1
ghci> halve 6 >>= halve
Nothing
ghci> halve 6 >>= halve >>= halve
Nothing
ghci> halve 32 >> Nothing
Nothing                         -- 2
ghci> halve 32 >>= halve >>= halve >>= halve
Just 2
ghci> halve 32 >> Nothing >>= halve >>= halve >>= halve
Nothing                         -- 3

You can play with this yourself by loading up the function yourself.

Remember, >>= means “use the results of the last thing to calculate this next thing” — it “chains” the functions.

How does this work, exactly? That’s not really in the scope of this article (any monad tutorial will explain this in more detail). But here are some interesting points:

1. Note that this command doesn’t even bother with the second halve. It knows that the end result will be Nothing no matter what (because halve 7 is Nothing), so it just skips right past the second halve.
2. >> is a special variation of >>=. >>= says “take the result of the last thing and use it on this”, while >> says “ignore the result of the last thing and always return this”. So >> Nothing means “I don’t care what the last thing succeeded with, I’m going to fail right here.”
3. Disastrous! Even though halving 32 four times usually is fine (giving Just 2), having just one failure along the way means that the entire thing is a failure. halve 32 >> Nothing is Nothing, so the whole thing is just (Nothing) >>= halve >>= halve >>= halve.

You can think of this failing phenomenon like this: At every step, Haskell attempts to apply halve to the result of the previous step. However, you can’t halve a Nothing because a Nothing has no value to halve!

Do notation

Haskell provides a convenient way of writing chained >>=’s called do notation; here are a few samples matched with their equivalent >>= form:

ghci> half 8
Just 4
ghci> do  half 8
Just 4

ghci> halve 8 >>= halve
Just 2
ghci> do  x <- halve 8
    |     halve x
Just 2

ghci> halve 32 >>= halve >>= halve >>= halve
Just 2
ghci> do  x <- halve 32
    |     y <- halve x
    |     z <- halve y
    |     halve z
Just 2

ghci> halve 32 >> Nothing >>= halve >>= halve
Nothing
ghci> do  x <- halve 32
    |     Nothing
    |     y <- halve x
    |     z <- halve y
    |     halve z
Nothing

In this notation, x, y, and z’s do not contain the Just/Nothing’s — they represent the actual Ints inside them, so we can so something like halve x (where halve only takes Ints, not Maybe Int’s)

It kind of feels very imperative-y — “do halve 32 and assign the result (16) to x…do halve x and assign the result (8) to y…” — but remember, it’s still just a bunch of chained >>=s in the end.

Failure is an option

The important thing to note here is that “do” notation basically builds up one “giant” object. Remember the last two examples — the second to last one, all of those lines were in an effort to build one giant Just 2 value. In the last example, all of those lines were in an effort to build one giant Nothing value. That’s why one Nothing “ruined” the whole thing. The entire computation is one big Maybe a. If at any point in your attempt to build that Maybe a, you fail, then you have Nothing.

Now, remember, saying “x is a monad” just means “we have defined a way of chaining functions/operations on x”. Just like how we can now chain multiple functions that return Maybe’s (that don’t take Maybe’s as input). However, given any object, there is probably more than one way to meaningfully define this “chaining”.

Sometimes, it’s useful to base your definition of chaining on the idea of a failure/success process. Sometimes it’s useful to define chaining as “We are building up either a success or a failure…and if at any point I fail, the whole thing is a failure”.

There is a special name for this design pattern. In Haskell, we call something like this a “MonadPlus”^{1 2}.

I know, it’s an embarrassingly bad name, and it’s like this is for historical reasons (related to the footnote above). The name doesn’t even hint at a fail/succeedness. But we’re stuck with it for pretty much the entire foreseeable future, so when you chose to adopt a success/failure model for your chaining process, you have a MonadPlus.

There is a vocabulary we can use so we can talk about all MonadPlus’s in a general way:

• We call a success a “return”. Yeah…the name is super confusing because of how the word “return” is used in almost every other context in computer science. But hey. Oh well.
• We call a failure an “mzero”. Yes, this name is pretty lame too.

For Maybe, a “return” with the value x is Just x, and an “mzero” is a Nothing.

Something cool about Haskell is that if we type return x, it’ll interpret it as an auto-success of value x. If we type mzero, it’ll be an “alias” of whatever your failure is.

That means that for Maybe, return x is the same as Just x, and mzero is an alias for Nothing.

As a small note, the term/command “return”/return is shared by all monads. However, monads don’t ascribe any (general) conceptual “meaning” or “purpose” to return. For any old monad, it can mean whatever you want it to mean for that specific monad. However, in the context of MonadPlus, “return” has a very specific meaning: succeed. Because of this, “return” and “succeed” will be treated as synonyms in this article.

MonadPlus examples

To see this in action, let’s revisit the last do block and make it more generic, and just rephrase it in a form that we are going to be encountering more when we solve our problem with the List monad (which is (spoilers) also a MonadPlus):

halveThriceOops :: Int -> Maybe Int
halveThriceOops n = do          -- call with n = 32
    x <- halve n                -- Just 16              -- 1
    mzero                       -- Nothing              -- 2
    y <- halve x                -- (skip)               -- 3
    z <- halve y                -- (skip)
    return z                    -- (skip)               -- 4

Note that I’ve also included a line-by-line ‘trace’ of the do block with what the monad “is” at that point. It is what is calculated on that line, and it would be the value returned if you just exited at that step.

1. Business as usual. Halve n if possible and place the result in x. If n is 32, then x will be 16.
2. The failure. Remember, mzero means “fail here automatically”, which, in a Maybe object, means Nothing.
3. Now from here on, nothing else even matters…the entire block is a failure!
4. If possible, succeed with the value in z. This is supposed to be a Just with the value of z. Unfortunately, the entire block failed a long time ago. So sad!

ghci> sequence [Just 1, Just 4, Just 6]
Just [1,4,6]
ghci> sequence [Just 1, Nothing, Just 6]
Nothing

Guards

It feels like just slapping in mzero willy-nilly is not that useful, because then things just fail always no matter what. Wouldn’t it be handy to have a function that says “fail right…here, if this condition is not met”? Like mzero, but instead of always failing, fails on certain conditions.

Luckily, Haskell gives us one in the standard library:

guard :: MonadPlus m => Bool -> m ()        -- 1
guard True  = return ()
guard False = mzero

So guard will make sure a condition is met, or else it fails the entire thing. If the condition is met, then it succeeds and places a () in the value.

We can use this to re-implement halve, using do notation, aware of Maybe’s MonadPlus-ness:

halve :: Int -> Maybe Int
halve n = do                -- <halve 8>   <halve 7>
    guard $ even n          -- Just ()      Nothing
    return $ n `div` 2      -- Just 4       (skip)

So, first, halve is Just () (succeeds with a blank value ()) if n is even, or else Nothing (fails automatically) otherwise. Finally, if it has not yet failed, it attempts to succeed with n `div` 2.

You can trust me when I say this works the exact same way! You can try it out yourself!

As a friendly reminder, this entire block is “compiled”/desugared to:

halve n :: Int -> Maybe Int
halve n = guard (even n) >> return (n `div` 2)

A practical use

We aren’t where we need to be to begin tackling that Wolf/Goat/Cabbage puzzle yet…so to let this article not be a complete anticlimax (as a result of my bad planning — I had originally intended to do the entire three-part series as one article), let’s look at a practical problem that you can solve using the Maybe monad.

The obvious examples are situations where it is useful to be able to chain failable operations such as retrieving things from a database or a network connection or applying partial functions (functions that only work on some values, like our halve).

However, here is a neat one.

Let’s say we are making a game where you can lose health by being hit or gain health by picking up powerups. We want to calculate the final health at the end of the game. It seems a bit easy: just add up all the losses and gains! Unfortunately, it’s not so simple — it needs to be implemented such that if your health ever dips below 0, you are dead. Forever. No powerups will ever help you.

Think about how you would implement this normally. You might have a state object that stores the current health as well as a flag with the current dead/alive state, and at every step, check if the health is 0 or lower; if it is, swap the flag to be dead and ignore all other updates.

But let’s try doing this instead with the Maybe monad:

-- source: https://github.com/mstksg/inCode/tree/master/code-samples/monad-plus/MaybeGame.hs#L26-L51

-- die or fail immediately
die :: Maybe Int
die = mzero                         -- or die = mzero

-- if not dead, sets the health to the given level
setHealth :: Int -> Maybe Int
setHealth n = return n              -- or setHealth n = return n

-- damage the player (from its previous health) and check for death
hit :: Int -> Maybe Int
hit currHealth = do
    let newHealth = currHealth - 1
    guard $ newHealth > 0           -- fail/die immediately unless newHealth
                                    --     is positive
    return newHealth                -- succeed with newHealth if not already
                                    --     dead

-- an alternative but identical definition of `hit`, using >>= and >>
hit' :: Int -> Maybe Int
hit' currHealth = guard (newHealth > 0) >> return newHealth
    where
        newHealth = currHealth - 1

-- increase the player's health from its previous health
powerup :: Int -> Maybe Int
powerup currHealth = return $ currHealth + 1

ghci> setHealth 2 >>= hit >>= powerup >>= hit >>= powerup >>= powerup
Just 3
ghci> setHealth 2 >>= hit >>= powerup >>= hit >>= hit >>= powerup
Nothing
ghci> setHealth 10 >>= powerup >> die >>= powerup >>= powerup
Nothing
ghci> do  h0 <- setHealth 2        -- Just 2
    |     h1 <- hit h0             -- Just 1
    |     h2 <- powerup h1         -- Just 2
    |     h3 <- hit h2             -- Just 1
    |     h4 <- hit h3             -- Nothing
    |     h5 <- powerup h4         -- (skip)
    |     h6 <- powerup h5         -- (skip)
    |     return h6                -- (skip)
Nothing

And voilà! Fire it up yourself if you want to test it out in person!

You can think of the last do block conceptually this way: remember, h3 does not represent the Just 1 value — h3 represents the number inside the Just 1 — the 1. So h4 is supposed to represent the number inside its value, too. But because hit h3 results in Nothing; Nothing has no value “inside”, so h4 doesn’t even have a value! So obviously it doesn’t even make sense to call powerup h4…therefore h5 has no value either! It’s therefore meaningless to call powerup h5, so meaningless to return h6…the entire thing is a beautiful disaster. A fiasco. Mission accomplished!

The whole thing works as expected; you can even die suddenly with die, which ignores your current health.

Interestingly enough, we could actually eliminate all references to Maybe altogether by always using return and mzero instead of Just and Nothing. And if we make our type signatures generic enough, we could use this with any MonadPlus! But that is for another day.

Looking forward

Wow, who knew you could spend so much time talking about failure. Anyways, this is a good place to stop before we move onto how List is also a MonadPlus. Okay, so what have we learned?

• Monads are just a way of chaining functions on objects, and of course, every object’s chaining process is different. In fact there might be even more than one way to meaningfully chain functions on an object!
• One useful “chaining approach” is to model things as success-failure chains, where you are building something from successes, but if you fail once in the process, the entire process fails. An object that uses this approach/design pattern is called a MonadPlus.
• The Maybe object is one such example. We can define ‘chaining’ failable functions as functions that continue if the previous function succeeded, or propagate a failure if the previous function fails. A failable function, for a Maybe object, is a function :: a -> Maybe b or even :: Maybe b.
• There is a common vocabulary for talking about MonadPlus concepts — “return” means “succeed with this value”, and “mzero” means “fail now”.
• Due to Haskell’s polymorphism, we can “forget” we are using Maybe and in fact talk about/write for “general” MonadPlus’s, with return x and mzero resulting in the appropriate success/fail objects.

For the mean time, think about how it might make sense to chain operations on lists (ie, repeatedly applying functions :: a -> [b] to lists).

By this, I mean, given a function that turns a value into a list of values f :: a -> [b], find a way to meaningfully “chain” that function to a previous list and get a new list:

ghci> oldList >>= f
newList             -- a new list based on old list; f "chained" to `oldList`.

Is there more than one way to think about chaining them, even? And in what ways we can define this “chaining” to represent success/failure? Until next time!