Of monads and spacesuits

Eric Kow (firstname.lastname@loria.fr)
20 November 2005
Version: 0.8.2 (2007-08-30)

The following document is an attempt to explain monads in concrete visual terms. I shall use a metaphor of space stations and astronauts to cut down on the degree of abstraction. Hopefully this metaphor will help you lock into the internal logic of monads, without getting on your nerves.

A word of caution about this page: I do not actually explain how to use monads. Instead I mainly focus on how they work. Perhaps the best people to read this page are those who have some vague idea how to manipulate monadic code but would really like to know what's going on under the hood. I also do not explain why certain conceptual choices are made, preferring instead to short circuit this by use of the space station metaphor.

Edit of 2007-08-30: touched up a graphic; removed the wikibooks link (which is now very different, but becoming a fine tutorial of its own).


I'd like to start things off with a couple of simple functions which are useful for gluing other functions together. Now these functions aren't directly related to monads, but they help to give you an idea of how to write imperative-looking code in a functional language.

dollar

Imagine the following bit of code :
i (h (g (f x)))
Pretty ugly, isn't it? Fortunately, the Haskell library has a very handy operator called dollar (actually, $), which allows us to rewrite the same code in a more readable manner:
i $ h $ g $ f x
Implementing dollar is just a simple matter of function application. Here's the implementation in one line of Haskell:
 ($) f x = f x 
N.B.: the reason why dollar lets us drop all these parentheses is that it's got low precedence -- it lets other operators do their stuff first -- and is right associative.

euro

If you understand what dollar works, the next thing I want you to try is imagining what it would be like if it worked backwards. Say we wrote an operator called euro that does exactly the same thing as dollar, but with the arguments flipped around.
(€) x f = f x
N.B.: the euro symbol isn't valid Haskell... just use your imagination or make up some other operator.

Now, what on earth would something like this be good for? Let's revisit the dollar example from above:

    i $ h $ g $ f x
This is what the same example would look like using euro:
    f x € g € h € i
Now maybe if you are familiar with imperative languages like C and Java, things might look a little familiar. It's as if we were saying "first do f of x; next g; then h, then i". To drive the point home, we would even write the example above over multiple lines:
    f x €
    g €
    h €
    i
You could almost think of these euros as being the semicolons from the C or Java that you know and love.

The analogy is a bit shaky because you don't have the same notion of passing stuff from one step to the other step in those languages. Perhaps a better analogy would be to think of them as Unix pipes: the results of f x get fed into g, and those results into h and so forth.


Now, here is where things take a radical turn for the different. In this section, I will explain the context behind monads, basically what we are trying to accomplish, and eventually show how this relates to the euro operator.

I tend to deal very badly with abstraction when I'm in unfamiliar territory, say when I'm trying to understand monads. To cope with this, I sometimes like to tie everything down to nice concrete mental images, so please bear with me for the following moment of silliness.

the space station metaphor

Imagine that we are in some vast expanse of space. Scattered throughout space are a bunch of space stations. A space station is just a metaphor for a function: it takes astronauts in, and spits astronauts out.

functions as stations

These astronauts could be anything, Americans, Frenchmen, dogs, gorillas, whales, whatever. The only thing that matters is that, being a function, whenever you put the same astronaut in, you get the same astronaut out. That is, depending on the station, Bob in always results in Fred out. The other thing is to note that is our space stations are typed. You can have space stations that take Americans in and send Frenchmen out, or that takes cats in and send cats back, but no matter what, these spaces stations always work with the same kind of input and output.

Up to here, we have not done anything unusual. We have simply provided a new metaphor for functions in Haskell. But let's take a short breath. Here are the things we are manipulating so far:

  1. space stations (functions)
  2. astronauts (inputs)

One thing we would really like to do is somehow connect our space stations together: that is, you stick an astronaut into one space station and whatever comes out, you want to feed into another station. The problem is that we are in space. You can't just send an astronaut out into a vacuum, because he's going to encounter all sorts of unpleasantness: asphyxiation, explosive decompression (at least in pop culture), you know, that kind of thing.

The solution here would be to stick the astronaut into some kind of space suit before sending him or her to the next station. In fact, this is such a good solution, and we the people are so concerned about the well-being of our astronauts that we're going to issue a new directive: All space stations must put their astronauts into space suits before sending them out.

the space law

Whatever functions we're looking at now thus follow this general template.

λa -> putInSuit (???) 
The types of these functions is
a -> m b
This means that they take something of type a and return something of type b, but since we're in space, wrap the thing of type b in a space suit m.

Note: In reality, a lot of very useful space stations are not compliant with our new law, but that's ok, because as I'll show in future sections, there's a way to retrofit these stations to make them useful!


bind (>>=)

As I wrote above, our job is to connect space stations together, that is, to send astronauts from one space station to another. We've accomplished half of this job by declaring that all stations must output their astronauts in space suits.

The only problem is that space stations do not accept space suits as inputs, they accept astronauts! One possible solution might be to hack something onto all of our space stations that removes the space suit and feeds the astronaut in. But that would just be boring and ugly.

So instead, what we're going to do is create a kind of robot that takes a space suit (containing some astronaut), takes a space station, removes the astronaut from its suit and feeds the naked astronaut to the space station. This robot shall be called bind informally but will be written in Haskell as >>=. This is roughly what the bind robot would do:

    (>>=) suit fn = 
      let a = extractAstronaut suit 
      in  fn a
Its type signature is then
(>>=) :: m a -> (a -> m b) -> m b

That is, it takes an astronaut in a space suit (m a), it takes a space station (a -> m b). It unpacks the suit, feeds the astronaut in and sends out whatever the space station sends out (m b), also an astronaut in a space suit.

what bind does

To be precise, bind sometimes does do something to the space suit that the station sends out, but this detail does not matter right now.

bind and the euro

Remember the euro operator I talked about early on in this tutorial? Well, bind pretty much serves the same purpose; with the exception being that it handles all this business of removing astronauts from space suits. But the idea remains the same. Using the bind robot, we can chain together various space stations much in the same way that you would use euro in a non-monadic context.

To illustrate this idea, here is an example of three space stations connected together by bind. They all take astronauts and return space suits, and the bind operator simply feeds the output of one space station into the another.

    astronautInASpaceSuit >>=
    (λa1 -> putInSuit (singing a1)) >>=
    (λa2 -> putInSuit (dancing a2)) >>=
    (λa3 -> putInSuit (farting a3)) 
    

So now you get the idea the bind robot is used to connect the output of one space station (an astronaut in a space suit) into the input of another space station. In the rest of this tutorial, I shall show different ways of building a bind robot.


kinds of space (monads)

Here's where things get even more exotic: there may many different kinds of space, and depending on what kind of space you're in, the way the bind robot works is going to be different. In the upcoming section, I will discuss two simple kinds of space: the Maybe space and the List space, and show what the corresponding bind robot looks like.

But first, I would like to review the list of things we are manipulating so far:

  1. space stations (functions)
  2. astronauts (inputs)
  3. space suits (monadic values)
  4. the bind robot (>>=)
  5. kind of space (monads)

the Maybe monad

Prerequisite: to understand this section, you ought to be comfortable with the Maybe datatype (though not necessarily the fact that it too is a monad)

The Maybe monad is one of the simplest monads you can show that does something interesting. In Maybe space, the bind robot looks something like this:

    (>>=) suit fn =
      case suit of 
        Nothing -> Nothing
        Just a  -> fn a
    

So what's the story here? There are two kinds of space suits to be used in Maybe space: those that contain nothing and those that contain an astronaut. If bind receives a space suit with nothing in it, well there isn't much to do, we just return an empty space suit as well. If, however, there was an astronaut, well then we use pattern matching on Just (i.e. Just a) to extract the astronaut from the suit, and then we feed it to the space station fn.

Now remember, the space stations we're interested in all output astronauts in space suits, so as far as types are concerned, everything fits together: either we return Nothing (which is a space suit) or we return whatever fn a returns, which also is a space suit.

Just to be explicit: the type signature of bind in general is as follows

(>>=) :: m a -> (a -> m b) -> m b

In Maybe space, this reduces down to something a little more specific:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b

the List monad

Another simple monad to work with is List. Here's what the bind robot looks like in List space:

    (>>=) suit fn =
      case suit of 
        [] -> [] 
        xs -> concat (map fn xs)
    

This largely resembles the Maybe monad: except this time, we can either have an empty space suit or some kind of weird family space suit that contains a bunch of astronauts (all the same type!). If we get an empty space suit, we just return an empty space suit.

If we have some number of astronauts in the suit, then we have to individually feed each one of these astronauts into the space station. This gives us a bunch of space suits, which we then have to merge together (concat) into one single space suit so that all the types fit together and everything continues working smoothly.

Here is the type of the bind robot under List space:

(>>=) :: [a] -> (a -> [b]) -> [b]


If you've understood everything up to here despite all my tortured metaphors, I salute you, because you have understood the essence of how monads work. The next thing we will need to concentrate on is figuring out how to do something truly useful them, something more substantial than manipulating Maybe and List.

return

But before going further, it's time to remedy a little social injustice. Way back in the beginning, we declared that all space stations must output their astronauts in space suits. But what about all the old decrepit space stations that can't afford to retrofit themselves for space suit output capability?

These space stations can be helped with a little robot called return, whose only job is to take naked astronauts and put them into space suits. Having the return robot would let us bring all these ancient old-school space stations in line with the law. We just have to call return on them.

The type signature of return is then something like this:

    return :: a -> m a
    

Here is what return looks like in Maybe space:

    return a = Just a
    

Nothing to it. No pun intended. And in List space?

    return a = [a]
    

In our earlier examples, we said used an imaginary function called putInSuit. In fact, this is exactly the return robot we've just shown you. What happens when you are working with monads is that with some space stations, you have to use return function to wrap the output astronaut in a suit.

why bother?

Return puts astronauts in space suits, and bind takes them back out. If you've been following up to here, you might be asking yourself why we're going through all this business if we're only going to cancel ourselves out?

One reason is that some space stations have their monad compatibility built-in. They don't need some special function like putInSuit or a some robot like return because returning space suits is part of their raison d'etre. You can recognise these space stations by their type, because they always return a monadic value. The putStr function, for example, returns IO (), which is simply an IO space suit with an astronaut of type () inside.

If you want, the real reason we're using all this monadic stuff is because we want to handle these fancy new space stations in an elegant manner. If connecting the older space-suit-less space stations together was the only issue, we could have just used something simpler, like dollar or euro.

And if you want the real real reason, this is not the document for you!


State monad

The State monad is where things start to really get useful, but -- I'm not going to hide this from you -- it is also where they start to get a little crazy. No matter what happens here, I want you to keep in mind that we're always doing the same thing, building a bind robot which takes a space suit, takes a space station, extracts the astronaut from the suit and feeds it into the station.

A State monad is useful if you want to pass some information around at the same time you run your function. The tricky thing here is that in State space, a space suit is itself a function!

return a = λst -> (a, st)
This looks a little exotic, but let me show some implementations of return to reassure you that it's really just more of the same thing :
Maybe
return a = Just a
List
return a = [a]
State
return a = λst -> (a, st)

See, nothing special. With Maybe, we return a maybe, with List, we return a list, and with state, well, we return a function.

The way I like to think of it is that in State space, the space suits are very sophisticated: all space suits have a ticket reader, and when you feed a ticket (st) into the space suit, it opens up to reveal an astronaut and ticket (a, st).

I like to think of this new ticket as a receipt. Now in the case of return, the suit trivially reveals the same ticket you fed in, but other space suits might not do the same. In fact, that is the whole point! Tickets are used to represent some kind of state (say some kind of routing information), and this mechanism of taking tickets in and spitting receipt tickets out is how we pass state information from one space station into another.

state space suit

State and the bind robot

Under the State monad, the bind robot implements what my friend Dmitry likes to call a bureaucratic mess. But remember, it's doing exactly the same thing as all the other bind robots, just under the conditions of State space.

    (>>=) suit fn =
      λst -> 
        let (a, st2) = suit st
            suit2    = fn a 
        in  suit2 st2 
    

To start things off, don't worry about the λst. Just imagine that somehow magically, we have a ticket st. This is very fortunate, because the only way we're going to get our sophisticated State space suits to open is by feeding them a ticket.

In the line (a, st2) = suit st, we do exactly that; we feed our ticket st into the suit. And it opens up to reveal both the astronaut and a receipt (a, st2).

Next, in line suit2 = fn a, we feed the astronaut into the space station fn, which by the way, outputs a space suit, as mandated by the "law" we set into place in the beginning of this tutorial.

Here is the hard part: what does the line in suit2 st2 mean? Well, here it's useful to ignore the whole let..in construct and think of the whole expression. Ultimately, the implementation of bind is λst -> suit2 st2. And all this does is to encapsulate an interesting chain reaction into a container space suit. The idea is that when you feed a ticket (st) into the container:

  1. st gets fed to the first space suit. This results in astronaut and a receipt (a, st2).
  2. a gets fed into space station fn. This results in a new space suit (suit2)
  3. the container suit now feeds the new ticket (st2) into the new space suit (suit2) and comes out is yet another astronaut and new receipt which represents the result of the whole Rube Goldberg contraption.
the container suit
This is the hardest part to understand. Once you get this bit, you pretty much have the monads story cinched. It's all easy from here on out.

useful functions

Here are a couple of functions that increase the usefulness of the State monad. Note that these are space stations, like all the others; they accept astronauts and produce space suits. One thing than makes them special though, is that they are the kind of function that have monad-compatibility built right in! But they only work in State space, though.

get

get is a function that simply returns the current state.

    get = λa -> λst -> (st,st)
Yep, it's weird. The first thing is that we completely ignore any astronauts that get passed into it. The other is that the astronaut we send out is a ticket! It is a state! But why not? The astronaut would be Dutch, Russian, a baboon, why not a state?

put

put is the flipside of get. It sets the current state to some arbitrary value.

    put x = λa -> λst -> ((),x)

Here the astronaut that we return is simply (), which isn't very interesting in itself, which is fine. Putting things in states isn't about the astronauts, it's about the tickets. The only thing you have to be careful of is that the tickets always have to be the same type. If you are using a State thumbprint monad, then you can only put thumbprints. If you are using a State Int monad, then you can only put Ints.


The (I)O monad

If you understand the State monad, then you pretty much understand that IO monad that you make so much use of. The first useful idea is simplify matters by only concentrating on output. Let's call this the O monad. The O monad is simply a state monad where the state (the ticket) is a list of things to be written to the screen. Putting something on the screen simply consists of appending something to the list.

putStr

Perhaps a good way to illustrate the point is to show one way that the putStr function would work. Remember all functions take an astronaut and return a space suit. Here, we take an astronaut and pretty much ignore it:

    putStr str = 
      λa -> λout -> ((), out ++ str)
    
That's all there is to it. We append the string to the output. If this isn't completely clear, try noticing how much this putStr in our hypothetical O monad looks like the put function in the State monad.

what about input?

So what about all the complicated stuff like stdin and stderr? Same old thing. The IO monad is still just a State monad, but instead of the state being a list, it is now a tuple of lists, one for each file handle. Or to be more realistic, the state in an IO monad is some horribly complicated data structure which represents the state of the computer at some point in the computation. That's what you're passing around when you manipulate IO: the entire environment as a nothing more than a state.


do notation

Now that you know how monads work, what you would hopefully like to do is make use of them in a comfortable manner. Well, you could write your monadic code like this:

       astronautInASpaceSuit >>=
       λa1 -> foo a1 >>=
       λa2 -> bar a2 >>=
       λa3 -> baz a3 
    
But I would argue that is plenty cumbersome. This is why Haskell introduces a little bit of syntactic sugar. But before we get there, let's just fiddle with the whitespace. Same code as above, but with the newlines in funny places:
       astronautInASpaceSuit >>= λa1 -> 
       foo a1 >>= λa2 -> 
       bar a2 >>= λa3 -> 
       baz a3 
    
All the do notation does is move all the weird stuff on the right to the left.
    do
       a1 <- astronautInASpaceSuit 
       a2 <- foo a1 
       a3 <- bar a2 
       baz a3 
    

See? Same code, but sugarfied. There's more to the do notation, especially the use of let. For more information, please look to a more official Haskell tutorial. By now, you should be comfortable enough with the abstract stuff to deal with all this.


conclusion

This concludes the astronauts and space stations tutorial on monads. I hope this has given you a clearer idea of what's really going on when you use a monad.

You should note that I've left out a good bit of detail. In fact, some of the more monad-aware readers point out that the tutorial actually misses the point a bit. So you should most definitely have a look at some other tutorials, or even the Haskell API. Control.Monad , to get a more complete picture.

If you are interested in the implementation of the State monad, you should also note that I've taken some liberty with the type system and left out some minor details. Namely, you need to use newtype and type constructors to get things exactly right. For more details, see the Hal Daume tutorial mentioned below.

feedback please

I'd appreciate any feedback and insults you may have regarding this document. It was originally written for a couple of friends I had who have complained that monads are well nigh impossible to understand. I beg to differ...

acknowledgments

Without a combination of Hal Daume's Yet Another Haskell Tutorial and Jeff Newbern's All about Monads I wouldn't have had the slightest clue what a Monad was. Hopefully this tutorial will provide another useful point of view to the path of getting it.

Many thanks to Dmitry for beta testing my metaphor (and being a very good sport about it) and introducing the card reader interpretation of space suits in the State monad. Thanks also to Emilie for comments on this tutorial.

Brian Slesinsky pointed out a pretty big goof in version 0.7 of this tutorial: I had been incorrectly writing the bind operator as <<=. Many thanks! For the curious, there is also a backwards bind operator, =<< What do you think it does?


cc-by-nc-sa
Also licensed GFDL for possible incorporation into wikibooks.