A Monad Tutorial for Ocaml August 6, 2007 | 06:37 pm

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 -&gt ‘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 Foos 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.

Tags: ,

  • Antoine

    Nice turorial! I’m not too familiar with OCaml, and it helps to see programs I know done in a language I don’t .
    A comment on your terminology: I’m used to refering to the functor (like Maybe or List) as a monad, not the “boxed” values themselves.

    So I was pretty confused when you were talking of functions taking in two monads and returning a third monad :-)

  • augustss

    You didn’t use type signatures much. What’s the type of, e.g., join?
    Don’t you need to put that in a functor to make it work for any monad? And even if you do, you’ll need a functor application when you want, e.g., join.

  • Brian

    Antoine: Yeah, I have a bad habit of using “monad” to mean the generic concept, a specific type, and an object of the specific type. Of course, programmers do this all the time- for example, using the name ‘integer’ to refer to the platonic ideal (number), the specific data type (31-bit ints) and specific objects (7).

    augustss: The type of join is ‘a t t -> ‘a t. Yeah, the whole “working with monads” section should be wrapped in a functor, like:

    module MonadMake(Monad: MonadRequirements) = struct
    open Monad;;
    … much code here …
    end;;

    I vascillated over wether to spell this out or not- wether to just toss a functor in there and expect people to know what it is (limiting the scope of my audience, as even most Ocaml programmers are not the most comfortable with functors), or adding in a quick introduction to functors (distracting from the main thread of the post, and confusing and scaring off a lot of people- I’ve found, as a general rule, it’s best to only introduce one big, scary word at a time- and both ‘functor’ and ‘monad’ qualify as big, scary words). In the end I decided to just tap dance around the issue, and when someone mentioned in the comments “hey, shouldn’t you use a functor there?” to reply with “why yes, you should! But that’s a topic for another post…”

  • Roland Kaufmann

    I think that your wish has been granted: Version 1.2.0 of pa_monad is out, and it supports OCaml 3.10.

  • http://www.ffconsultancy.com Jon Harrop

    Awesome post!

  • Fabrice Marchant

    Very interesting. I wish to grasp the meaning of this mysterious monad that sounds like a female first name.

    I read here :
    http://groups.google.com/group/fa.haskell/browse_frm/thread/c86fadfc0486ddae/63d448d4eea4df31?lnk=gst&q=joel+reymont&rnum=8#63d448d4eea4df31
    that Haskell was useful to suggest techniques that can be used with other languages.

    One day, Virgile Prevosto send this on Beginners-list to solve a circular list problem :
    http://tech.groups.yahoo.com/group/ocaml_beginners/message/8180

    However, he did it an Haskell way, using a monad and I didn’t understood a lot…
    Now I can try to use this tutorial and notice the monad “return”.

    Please, could you dismantle, at the light of this tuto., how module “State_monad” works ?

    Thanks for advance.

  • Raj B

    Great tutorial! I like reading your tutorials in general, you have a knack for making difficult concepts accessible. Do you have or plan to write one on CPS style?

    A request: is it possible to somehow increase the size of the font you use to write code? It’s almost too small to be readable compared to the size of the normal text. I’m using firefox on a Mac, so it’s a pretty standard setup.

  • Norry Ogata

    Thank you very much.
    I could study monads in OCaml as a beginner.
    By the way, now I’m trying to make a monad of type of ‘a->’a list, say D.
    When I define bind and map of D, I cannot define them.
    My incomplete definitions of them are as follows:

    let mapD (h:’a->’b) (m:’a->’a list) = fun x -> (List.flatten(List.map h (m ((inv h) x))));;

    let bindD (m:’a->’a list) (p:’a->’b->’b liist)
    = fun y -> fun x ->(List.flatten(List.map (fun a->(p a x)) (m y))

    But, I noticed that function “inv” which means the inverse of a function does not have not unique value and I coundn’t have defined yet.
    Similarly, bindD is of type (‘a -> ‘a list) -> (‘a -> ‘b -> ‘b list) -> ‘a -> ‘b -> ‘ b list,
    although I want the function of type of (‘a -> ‘a list) -> (‘a -> ‘b -> ‘b list) -> ‘b -> ‘ b list.

    Do you have any idea?

  • Norry Ogata

    Sorrry, in my previous comment, “inv has not unique value” is wrong. Naturally, (inv f) ,where f is a bijection, it must have a unique value. Even so, I couldn’t have defined it yet.

  • Norry Ogata

    Hi again,
    In my previous comment,
    I showed:
    mapD (h:’a->’b) (m:’a->’a list) = fun x -> (List.flatten(List.map h (m ((inv h) x))));;

    Instead if:
    mapD (h:’a->’b) (m:’a->’a list) = fun (h x) -> (List.flatten(List.map h (m x)));;
    is possible, it’s fine, but such a definition is not accepted.

  • Norry Ogata

    I’m ashamed that I couldn’t notice the fact that generally exponent functors cannot be defined unless the functor is defined over cartesian-closed categories. Of course, the functor D:’a -> ‘a list what I want to define is an exponent functor. So the type variable ‘a must be restricted. I could define the limited version of D, say D’, in a Haskell program by restricting ‘a to “bounded and enumerable type classes” in the sense of Haskell. But even now I want to define D’ in Ocaml. I know the Extlib library of Ocaml. Can we define D’ in Ocaml?

  • Nicolas Pouillard

    @Norry Ogata
    Your last mapD definition is not syntactically correct (fun (h x) -> …), maybe you want to write (fun h x -> …)
    let mapD (h:’a->’b) (m:’a->’a list) = fun h x -> (List.flatten(List.map h (m x)));;

    @Brian
    Thanks for this post! That’s always a pleasure to see this concept being more-and-more popularized to other functional languages.

    I have a small remark about your monads, in particular the return function. One have to remember that OCaml has a call-by-value semantics such that :

    let return x = fun () -> x
    OR
    let return x = lazy x

    Don’t defer any effects, they are just there to fulfill the type, then expanding the definitions will not lead to the same result, “return (print_int 3)” is different from
    “lazy (print_int 3)”, however this is maybe not that problematic.

    Moreover, there is a typo in your bind definition (ill-scoped/ill-typed):
    let bind m f = lazy (Lazy.force g (Lazy.force m));;
    =>
    let bind m f = lazy (Lazy.force (f (Lazy.force m)));;

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

  • Paulo Villela

    Your great tutorial demystifies monads and makes them accessible to OCaml programmers. Thanks!

  • Louis

    I have a question about the int_val example. I’d have expected that read_int_val should have been something like

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

    just to make the types work out. What’s wrong with how I am thinking about it?

    Also, do you have sample code for the thread example?

  • Elias

    i liked it :) i’m bookmarking, thank you.

    i just missed an explanation on doing functional I/O with monads — this is something that looks very arcane and i never got it very well..

  • kk

    @Brian — Many thanks, this clears up the Monad concept quite bit for me.  Now you have me wondering how I might go about doing Monads in Perl5 …  ;-)

  • Matthias

    Shouldn’t
    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;;

    be
    module LazyMonad = struct
    type ‘a t = ‘a lazy_t;;
    let return x = lazy x;;
    let bind m f = lazy (Lazy.force f (Lazy.force m));;
    end;;

    ?

  • Li Weijian

    Thanks, that’s an interesting article.

    I’m trying to test the codes of this post and got some trouble.

    At first, I tested the `return` function, it works well:
    `let om = OptionMonad.return 5;;`

    But when I tried to test the bind function as follows:
    `let read_om = OptionMonad.bind om (fun x -> x)`

    I encountered an error:
    `Error: This expression has type int but an expression was expected of type ‘a option`

    I think that should be easy to solve, but I had spent more than half an hour on it. Any hints would be appriciated:)