A ‘newbie’, in Haskell, is someone who hasn’t yet implemented a compiler. They’ve only written a monad tutorial.

With that quote in mind, I’ve decided to become a Haskell newbie and write myself a monad tutorial. This has a value, no matter how bad the monad tutorial might be- it’s as much about explaining the concept to the author as it is explaining it to anyone else. It’s also a test to show how well you really understand the concept. So, as usual, this should not be considered the final word on this subject (as if), but instead the first cut. Because I think I’ve gotten a handle on monads. So it’s time to step up an embrace the newbie experience.

Forget category theory. Forget space suits and free will and all the other bad analogies floating around about Monads. Monads are first and foremost a *design pattern*, as in the Gang of Four “Design Patterns” book.

Specifically, it’s a design pattern for manipulating computations and enforcing certain semantic constraints. Hopefully, what I mean by this will become clear before the end of the post.

The design patterns in that book were first discovered and codified (in both meanings of that word) by Object Oriented programmers (mainly in the Smalltalk community), so to are various new design patterns being discovered and codified by the functional programming community. Among the design patterns being discovered by the functional community are the various lazy evaluation tricks, and monads. And, like the patterns describes in the GoF book, monads are a usefull pattern outside of the language they were originally discovered in.

Which is why I’m doing something different with this tutorial, and using Ocaml instead of Haskell as the language of choice. The advantage of this choice is that Ocaml makes certain issues more clear and up front which Haskell muddles (or, to put it a different way, Ocaml forces you to deal with some things that Haskell doesn’t). Hopefully, this second pespective will lend a depth to the explanation (sorry- couldn’t resist the pun).

# Basic Monads

What is a monad? At the most simplistic level, it is simply any data structure or type which fullfills (or can fullfill) the following signature:

`module type MonadRequirements = sig`

type ‘a t

val bind : ‘a t -> (‘a -> ‘b t) -> ‘b t

val return : ‘a -> ‘a t

end;;

In other words, a monad is a box- you can put things into the box (with `return`

) and manipulate things inside of the box (with `bind`

). A surprising number of things qualify as monads under this simplistic definition. Here are two obvious ones, which Ocaml programmers are already familiar with. The first is the lowly `option`

type (for you Haskell programmers, the `option`

type is Ocaml’s version of `maybe`

):

`module OptionMonad = struct`

type ‘a t = ‘a option;;

let bind opt f =

match opt with

| Some(x) -> f x

| None -> None

;;

let return x = Some x;;

end;;

Another common Ocaml data structure that is a monad is the list (which demonstrates that, at least for some monads, the box can hold more than one thing):

`module ListMonad = struct`

type ‘a t = ‘a list;;

let bind lst f = List.concat (List.map f lst);;

let return x = [ x ];;

end;;

I want to pause for just a moment and focus on that `list.concat`

. It’s obviously necessary for the typing to be correct- after the `list.map`

, what we have is not a `‘a list`

, but instead a `‘a list list`

. The semantics of the monad are that the function `f`

passed in to bind is called on every element in the box. It returns another box with some number of elements in it. All the boxes created by all the calls to f are then combined into a single big box.

In a manner similiar to the example given above for lists, most simple data structures can be made into functors.

# Working With Monads

The monad definition I’ve supplied so far doesn’t look like much, but it allows me to build a wide array of useful monad-manipulating functions on top of what we have been given. For example, I can easily define the standard Haskell operators `>>`

and `>>=`

like this:

`let ( >>= ) = bind;;`

let ( >> ) m f = bind m (fun _ -> f ());;

I can define the `join`

function, which converts a double monad of type `‘a t t`

to a single monad of type `‘a t`

by binding to the identity function:

`let join mm = bind mm (fun x -> x)`

I can define the `map`

function, with the signature `(‘a -> ‘b) -> ‘a t -> ‘b t`

like:

`let map f m = bind (fun x -> return (f x)) m;;`

I can define a `bind2`

operator that combines two monads into a third monad, with a type of `‘a t -> ‘b t -> (‘a -> ‘b -> ‘c t) -> ‘c t`

like:

`let bind2 m_a m_b f = bind m_a (fun a -> bind m_b (f a));;`

There are three interesting things about the `bind2`

function. The first is that it’s the first example of calling come function other than `return`

within a monad. So long as the end result is the correct sort of monad, it works.

The second interesting thing about this function is what it does when there is more than one element in the monad, like when we’re using the list monad. Consider what would happen if bind where ListMonad.bind, and we did `ListMonad.bind2 [1;2;3] ['a';'b';'c';'d'] (fun i j -> return (i, j) )`

? The result we get back (a list of tuples) is `[(1, 'a'); (1, 'b'); (1, 'c'); (1, 'd'); (2, 'a'); (2, 'b'); (2, 'c'); (2, 'd'); (3, 'a'); (3, 'b'); (3, 'c'); (3, 'd')]`

. Every element in monad a is paired off with every element in monad b- in a fasion not unlike an unrestricted SQL join. Again we’re finding deep similiarities between functional programming (in Ocaml or Haskell) and relational programming (in SQL).

The third interesting thing about `bind2`

is that now that we can bind together two monads, we can leverage that to bind together any number of monads. For example, we can now define a function that given a list of monads, returns a monad of a list (with a type `‘a t list -> ‘a list t`

), like:

`let lift_m lstm =`

let f m1 m2 =

let g a b = return (a :: b) in

bind2 m1 m2 g

in

List.fold_right f lstm (return [])

;;

Note that the above code does not filter out the Nones if you’re using it on the OptionMonad! If any single element of the list is None, the resulting monad is None. Only if all the elements are Some(val) is the result Some(list).

# Intermission

There is already a value in what we’ve done so far- for example, we can now manipulate a wide class of data structures with the same abstract code. And we have made working with those data structures much easier- for example, code stringing together functions that return options is much simpler using `OptionMonad.bind`

than repeated nested if statements. Indeed, one of this author’s favorite monads is just:

`module SuccessMonad = struct`

type ‘a t =

| Success of ‘a

| Failure of string

;;

let return x = Success x;;

let bind m f = match m with

| Success(x) -> f x

| Failure(s) -> Failure(s)

;;

end;;

Functions can then just return `‘a SuccessMonad.t`

, and can be chained together. And that’s not even touching camlp4 magic to implement the do-notation (can someone pretty please port this to the new camlp4? Thanks).

But the real power of monads is yet to be tapped…

# More Advanced Monads

Now, let’s write a fun monad, pun intended:

`module FunMonad = struct`

type ‘a t = unit -> ‘a;;

let return x = (fun () -> x);;

let bind m f = (fun () -> (f (m ())) ());;

end;;

The first thing that’s interesting about this monad is that it isn’t a data structure that holds a value, it’s a process that produces a value. We see that `bind`

is just a sequencing operator- after producing the value `‘a`

, apply this process to turn the `‘a`

into a `‘b`

. And all of the various monad manipulations we coded above automatically become not about manipulating an abstract data structure, but about manipulating a process, manipulating code. They’re just fancier ways to plug code together, to sequence code. We’re pluging functions together like lego blocks.

This is why I think it’s easier to learn about Monads in Ocaml than it is in Haskell- in Haskell, a value is both a value, and a process to produce that value. This is because everything is lazily evaluated in Haskell. In eagerly-evaluated Ocaml, a value is just a value. I could just as easily have written the above monad in Ocaml as:

`module LazyMonad = struct`

type ‘a t = ‘a lazy_t;;

let return x = lazy x;;

let bind m f = lazy (Lazy.force g (Lazy.force m));;

end;;

The equivelent Haskell is a lot less illuminating:

`data Example a = M a`

return :: a -> Example a

return x = M x

bind :: Example a -> (a -> Example b) -> Example b

bind (M x) g = g x

Note that this Haskell code is the more or less literal translation of the `LazyMonad`

example, which is more or less the equivelent of `FunMonad`

example. What the `FunMonad`

makes obvious, but what is true for all three monads in both languages, is that I’m manipulating the process to produce the value, and not the value itself.

The second interesting thing about the `FunMonad`

is why I didn’t write it like this:

`module FunMonad2 = struct`

type ‘a t = unit -> ‘a;;

let return x = (fun () -> x);;

let bind m g = g (m ());;

end;;

It’s much simpler and has the same type as `FunMonad`

has. The difference is when `g`

and the monads get executed? In `FunMonad2`

, but the passed in monad and the function are executed immediately. In the original `FunMonad`

, neither are executed immediately- rather they are all just bound up into a single big thunk, to be executed, in sequence, at some later point. A similiar argument holds for why I wrote `LazyMonad`

the way I did, rather than simplifying it.

The important point here is that a monad does not gaurentee immediate execution. Why this is important and usefull is just about to be explained.

# Putting a Lid on the Box

There has been a shortcomming (of a sort) in my definition of a monad that’s probably been niggling at you for the entire time. I’ve shown how you can put things into the monad, and how to manipulate things within a monad. But how, you might ask, do you ever get anything back out of the monad?

The short answer is that, in the general case, you can’t. If you know the “real form” of the monad, like it’s an option or a list, then you can use the normal accessors to those data types. But each Monad has it’s own special access rules. The power of a monad comes from the fact that the monad creator has total control over taking things out of the box.

Take, for example, the following API:

`module SerialMonad : sig`

type ‘a t

val return : ‘a -> ‘a t

val bind : ‘a t -> (‘a -> ‘b t) -> ‘b t

val access : ‘a t -> ‘a

It’s a monad, so all the above manipulations work. But since it’s an abstract type, there is only one way to get the value produced by the process back out of the box again- and that is by calling the `access`

function. And since there is no gaurentee that a function passed into `bind`

will be executed at that point, and not some later pointer, the implementor of the monad can easily just say that functions passed into `bind`

are not executed until `access`

is called- and even then, are only executed in the carefully constructed environment that `access`

executes it in.

I didn’t name `SerialMonad`

randomly. You’ve probably guessed by now that I named it with malice of forethought, as an example of what I mean by a “special environment”. And you’d be right:

`module SerialMonad = struct`

type ‘a t = unit -> ‘a;;

let serial_mutex = Mutex.create ();;

let return x = (fun () -> x);;

let bind m g = (fun () -> (g (m ())) ());;

let access m =

Mutex.lock serial_mutex;

try

let r = m () in

Mutex.unlock serial_mutex;

r

with

| e ->

begin

Mutex.unlock serial_mutex;

raise e

end

end;;

This monad is basically identical to the previous `FunMonad`

with the addition of the `access`

function- which executes the process while holding the `serial_mutex`

lock, which is always unlocked when the process completes (even if the process throws an exception). This forces all processes executing within a `SerialMonad`

to be executed sequentially and serially (thus the name). The “special environment” that `access`

executes the process in is, in this case, while holding the mutex.

# Magic Monad Values

The fact that you can put anything you want into a `SerialMonad`

means you can wrap anything you want into it. Let’s say you had a reference to an integers, and you wanted to make sure that reference was only ever accessed serially, you write:

`let int_val = SerialMonad.return (ref 0);;`

let read_int_val = SerialMonad.bind int_val (fun r -> !r);;

let write_int_val x = SerialMond.bind int_val (fun r -> r := x);;

What’s interesting is the type of `read_int_val`

, which is just `int SerialMonad.t`

. Remember that the value of `‘a SerialMonad.t`

doesn’t mean “a value of type `‘a`

within a `SerialMonad.t`

” but instead means “A process to produce a `‘a`

within a `SerialMonad.t`

“.

Likewise, the way to read the type of `write_int_val`

, which is `int -> unit SerialMonad.t`

, is “a function that takes an integer, and returns a unit value inside of a `SerialMonad`

. When this unit value is evaluated (within the “special environment” of `SerialMonad.access`

), it sets the integer value to the given value.”

Thanks to mutable data, I can’t gaurentee that references to mutable data won’t sneak out of the monad’s “special environment”. It, unfortunately, doesn’t prevent malice, but it does prevent (most) accidents. By wrapping this reference into a SerialMonad, combined with hiding the reference itself,

I can also have “secret data” for the monad, which is only visible within the monad’s “special environment”, and even then only to special functions I provide. For example, I might want to write a monad wrapper around file reading, like:

`module IOMonad = struct`

type ‘a t = in_channel -> ‘a;;

let return x : ‘a t = (fun _ -> x);;

let bind m g : ‘a t = (fun chan -> (g (m chan)) chan);;

let access filename m =

let chan = open_in filename in

try

let r = m chan in

close_in chan;

r

with

| e ->

begin

close_in chan;

raise e

end

;;

let read : string t = (fun chan -> input_line chan);;

end;;

Note that `read`

is another magic monad function.

# Russian Nesting Doll Monads

So far, we’ve been mainly working with monads that have an access function of the type `‘a t -> ‘a`

. The other common pattern for allowing things to escape the box is to provide a “repackaging” function, which converts a value of type `‘a Foo.t`

into a value of type `‘a Bar.t`

, for monad types `Foo`

and `Bar`

. The existence (or lack thereof) of these conversion functions determines a priority among the various monads. If we can convert a `Foo`

to a `Bar`

, that means we can use `Foo`

s inside of a `Bar`

, but not the other way around.

For example, assume we have three monads. The first monad is the `Deferred`

monad:

`module DeferredMonad : sig`

type ‘a t;;

val return : ‘a -> ‘a t;;

val bind : ‘a t-> (‘a -> ‘b t) -> ‘b t;;

val wait_for : ‘a t -> ‘a;;

end;;

The `Deferred`

monad represents an ongoing asynchronous process returning a type `‘a`

. For this monad, `bind`

means “when the passed in monad is complete, apply this transformation to the resultant data”. There is a function `wait_for`

of type `‘a Deferred.t -> ‘a`

which waits for the deferred process to complete, and returns the completed data (with all associated transforms applied).

The second monad is the thread monad:

`module ThreadMonad : sig`

type ‘a t;;

val return : ‘a -> ‘a t;;

val bind : ‘a -> (‘a -> ‘b t) -> ‘b t;;

val spawn : ‘a t -> ‘a Deferred.t;;

end;;

The thread monad builds up a thunk like `FunMonad`

does, and has a function `spawn`

of type `‘a Thread.t -> ‘a Deferred.t`

, which spawns the thread and creates a deferred monad which is complete when the thread exits.

The third is our old friend the `SerialMonad`

, except that instead of the `access`

function, we have a `serialize`

function:

`module SerialMonad : sig`

type ‘a t;;

val return : ‘a -> ‘a t;;

val bind : ‘a -> (‘a -> ‘b t) -> ‘b t;;

val serialize : ‘a t -> ‘a ThreadMonad.t;;

end;;

Given these three monads, we find that the range of possible behaviors we can express is limited by the lack of conversion operators. For example, every serialize computation has to take place in a thread. The only way to get the value out of a `SerialMonad`

is to first convert it into a `ThreadMonad`

, and then `spawn`

the thread, converting it into a `DeferredMonad`

, and then calling `wait_for`

to wait for the thread to exit. This is an important consideration- we are starting to enforce high-level semantic constraints, such as “a serialized computation can only take place within a spawned thread”, or “the return value of a thread can not be accessed until the thread has exited”, in the type system.

Haskell takes monads to an interesting extreme- there is one monad, the IO monad, which is defined to not have any safe conversion functions to normal values (ignoring unsafePerformIO). Instead, you return the IO monad from the main program, and it’s thunk is evaluated by the run time. In the Ocaml example above, you can spawn a thread, and wait for it to return, within the serialized code executing in a SerialMonad. In Haskell, `DeferredMonad.wait_for`

would probably return an IO monad- meaning that only the top level thread can truly wait for another thread. The most a `SerialMonad`

or `ThreadMonad`

could do is package a bunch of operations up into an IO monad and request the top level thread perform them. This allows Haskell to have an even tighter amount of control over what operations can be performed, and who can do them.

# Monads in the Real World

I’d like at this point to return to an off-hand comment I made in this post. In the midst of ranting about how great static type systems can be, I argued that static type systems could enforce semantic constaints, such as the buffer returned from an async read can only be accessed after the asynchronous read is complete, or that a postgresql cursor can only be accessed within a transaction.

Hopefully at this point, how the type system can enforce these constraints within the type system has been made clear- the answer is to use monads.

Pingback: Benjamin L. Russell’s Adventures in Programming Language Theory Wonderland