Example: The Maybe Monad

As we've seen before, sometimes functions are partial: there is no good output they can produce for some inputs. For example, the function max_list : int list -> int doesn't necessarily have a good output value to return for the empty list. One possibility is to raise an exception. Another possibility is to change the return type to be int option, and use None to represent the function's inability to produce an output. In other words, maybe the function produces an output, or maybe it is unable to do so hence returns None.

As another example, consider the built-in OCaml integer division function (/) : int -> int -> int. If its second argument is zero, it raises an exception. Another possibility, though, would be to change its type to be (/) : int -> int -> int option, and return None whenever the divisor is zero.

Both of those examples involved changing the output type of a partial function to be an option, thus making the function total. That's a nice way to program, until you start trying to combine many functions together. For example, because all the integer operations—addition, subtraction, division, multiplication, negation, etc.—expect an int (or two) as input, you can form large expressions out of them. But as soon as you change the output type of division to be an option, you lose that compositionality.

Here's some code to make that idea concrete:

(* this works fine and evaluates to 3 *)
let x = 1 + (4 / 2)

let div (x:int) (y:int) : int option =
  if y=0 then None
  else Some (x / y)

let ( / ) = div

(* this won't type check *)
let x = 1 + (4 / 2)

The problem is that we can't add an int to an int option: the addition operator expects its second input to be of type int, but the new division operator returns a value of type int option.

One possibility would be to re-code all the existing operators to accept int option as input. For example,

let plus_opt (x:int option) (y:int option) : int option =
  match x,y with
  | None, _ | _, None -> None
  | Some a, Some b -> Some (Stdlib.( + ) a b)

let ( + ) = plus_opt

let minus_opt (x:int option) (y:int option) : int option =
  match x,y with
  | None, _ | _, None -> None
  | Some a, Some b -> Some (Stdlib.( - ) a b)

let ( - ) = minus_opt

let mult_opt (x:int option) (y:int option) : int option =
  match x,y with
  | None, _ | _, None -> None
  | Some a, Some b -> Some (Stdlib.( * ) a b)

let ( * ) = mult_opt

let div_opt (x:int option) (y:int option) : int option =
  match x,y with
  | None, _ | _, None -> None
  | Some a, Some b -> 
    if b=0 then None else Some (Stdlib.( / ) a b)

let ( / ) = div_opt

(* does type check *)
let x = Some 1 + (Some 4 / Some 2)

But that's a tremendous amount of code duplication. We ought to apply the Abstraction Principle and deduplicate. Three of the four operators can be handled by abstracting a function that just does some pattern matching to propagate None:

let propagate_none (op : int -> int -> int) (x : int option) (y : int option) =
  match x, y with
  | None, _ | _, None -> None
  | Some a, Some b -> Some (op a b)

let ( + ) = propagate_none Stdlib.( + )
let ( - ) = propagate_none Stdlib.( - )
let ( * ) = propagate_none Stdlib.( * )

Unfortunately, division is harder to deduplicate. We can't just pass Stdlib.( / ) to propagate_none, because neither of those functions will check to see whether the divisor is zero. It would be nice if we could pass our function div : int -> int -> int option to propagate_none, but the return type of div makes that impossible.

So, let's rewrite propagate_none to accept an operator of the same type as div, which makes it easy to implement division:

let propagate_none 
  (op : int -> int -> int option) (x : int option) (y : int option)
=
  match x, y with
  | None, _ | _, None -> None
  | Some a, Some b -> op a b

let ( / ) = propagate_none div

Implementing the other three operations requires a little more work, because their return type is int not int option. We need to wrap their return value with Some:

let wrap_output (op : int -> int -> int) (x : int) (y : int) : int option =
  Some (op x y)

let ( + ) = propagate_none (wrap_output Stdlib.( + ))
let ( - ) = propagate_none (wrap_output Stdlib.( - ))
let ( * ) = propagate_none (wrap_output Stdlib.( * ))

Finally, we could re-implement div to use wrap_output:

let div (x:int) (y:int) : int option =
  if y = 0 then None
  else wrap_output Stdlib.( / ) x y

let ( / ) = propagate_none div

Where's the Monad?

The work we just did was to take functions on integers and tranform them into functions on values that maybe are integers, but maybe are not—that is, values that are either Some i where i is an integer, or are None. We can think of these "upgraded" functions as computations that may have the effect of producing nothing. They produce metaphorical boxes, and those boxes may be full of something, or contain nothing.

There were two fundamental ideas in the code we just wrote, which correspond to the monad operations of return and bind.

The first (which admittedly seems trivial) was upgrading a value from int to int option by wrapping it with Some. That's what the body of wrap_output does. We could expose that idea even more clearly by defining the following function:

let return (x : int) : int option =
  Some x

This function has the trivial effect of putting a value into the metaphorical box.

The second idea was factoring out code to handle all the pattern matching against None. We had to upgrade functions whose inputs were of type int to instead accept inputs of type int option. Here's that idea expressed as its own function:

let bind (x : int option) (op : int -> int option) : int option =
  match x with
  | None -> None
  | Some a -> op a

let (>>=) = bind

The bind function can be understood as doing the core work of upgrading op from a function that accepts an int as input to a function that accepts an int option as input. In fact, we could even write a function that does that upgrading for us using bind:

let upgrade : (int -> int option) -> (int option -> int option) =
  fun (op : int -> int option) (x : int option) -> (x >>= op)

All those type annotations are intended to help the reader understand the function. Of course, it could be written much more simply as:

let upgrade op x = 
  x >>= op

Using just the return and >>= functions, we could re-implement the arithmetic operations from above. For example, here are addition and division:

let ( + ) (x : int option) (y : int option) : int option = 
  x >>= fun a ->
  y >>= fun b ->
  return (Stdlib.( + ) a b)

let ( - ) (x : int option) (y : int option) : int option = 
  x >>= fun a ->
  y >>= fun b ->
  return (Stdlib.( - ) a b)  

let ( * ) (x : int option) (y : int option) : int option = 
  x >>= fun a ->
  y >>= fun b ->
  return (Stdlib.( * ) a b)    

let ( / ) (x : int option) (y : int option) : int option = 
  x >>= fun a ->
  y >>= fun b ->
  if b = 0 then None else return (Stdlib.( / ) a b)

Recall, from our discussion of the bind operator in Lwt, that the syntax above should be parsed by your eye as

• take x and extract from it the value a,
• then take y and extract from it b,
• then use a and b to construct a return value.

Of course, there's still a fair amount of duplication going on there. We can de-duplicate by using the same techniques as we did before:

let upgrade_binary op x y =
  x >>= fun a ->
  y >>= fun b ->
  op a b

let return_binary op x y = 
  return (op x y)

let ( + ) = upgrade_binary (return_binary Stdlib.( + ))
let ( - ) = upgrade_binary (return_binary Stdlib.( - ))
let ( * ) = upgrade_binary (return_binary Stdlib.( * ))
let ( / ) = upgrade_binary div

The Maybe Monad

The monad we just discovered goes by several names: the maybe monad (as in, "maybe there's a value, maybe not"), the error monad (as in, "either there's a value or an error", and error is represented by None—though some authors would want an error monad to be able to represent multiple kinds of errors rather than just collapse them all to None), and the option monad (which is obvious).

Here's an implementation of the monad signature for the maybe monad:

module Maybe : Monad = struct
  type 'a t = 'a option

  let return x = Some x

  let (>>=) m f = 
    match m with
    | None -> None
    | Some x -> f x
end

These are the same implementations of return and >>= as we invented above, but without the type annotations to force them to work only on integers. Indeed, we never needed those annotations; they just helped make the code above a little clearer.

In practice the return function here is quite trivial and not really necessary. But the >>= operator can be used to replace a lot of boilerplate pattern matching, as we saw in the final implementation of the arithmetic operators above. There's just a single pattern match, which is inside of >>=. Compare that to the original implementations of plus_opt, etc., which had many pattern matches.

The result is we get code that (once you understand how to read the bind operator) is easier to read and easier to maintain.