(* monadic operations for the Reader monad *)

env -> 'a;;
let mid (x : 'a) : 'a reader =
fun e -> x;;
fun e -> (fun x -> k x e) (xx e);;


We've just beta-expanded the familiar k (xx e) e into (fun x -> k x e) (xx e). We did that so as to factor out the parts where the payload of any Reader value is being supplied as an argument to another function. That will help make some patterns that are coming up more salient.

Well, one way to proceed would be to just let values of the other monad M be the 'a in your 'a reader. Then you could apply reader_mbind to get at the wrapped 'a M, and then apply M.mbind to get at its wrapped 'a. This sometimes works.

But there are two problems: (1) It's cumbersome having to work with both reader_mbind and M.mbind. It'd be nice to figure out some systematic way to connect the plumbing of the different monadic layers, so that we could have a single mbind that took our 'a Reader_around_M, and sequenced it with a single 'a -> 'b Reader_around_M function. Similarly for mid. This is what the ReaderT monad transformer will let us do.

(2) For some combinations of monads, the best way to implement a Tish monadic wrapper around an inner M monad won't be equivalent to either an ('a m) t or an ('a t) m. It will be a tighter intermingling of the two. So some natural activities will remain out of reach until we equip ourselves to go beyond ('a m) ts and so on.

What we want in general are monadic transformers. For example, a ReaderT transformer will be parameterized not just on the type of its innermost payload 'a, but also on the monadic box type M that wraps 'a. It will make use of monad M's existing operations M.mid and M.mbind, together with the Reader patterns for mid and mbind, to define a new monad ReaderT(M) that fuses the behavior of Reader and M.

Here's how it's implemented:

(* monadic operations for the ReaderT monadic transformer *)

(* We're not giving valid OCaml code, but rather something
* that's conceptually easier to digest.
* How you really need to write this in OCaml is more circuitous... *)

env -> 'a M;;
(* this _happens_ also to be the type of an ('a M) reader
* but as we noted, you can't rely on that pattern always to hold *)

let mid (x : 'a) : 'a readerT(M) =
fun e -> M.mid x;;

fun e -> M.mbind (xx e) (fun x -> k x e);;


Notice the key differences: where before mid x was implemented by a function that just returned x, now we instead return M.mid x. Where before mbind just supplied the payload xx e of an 'a reader as an argument to a function, now we instead M.mbind the corresponding value to the function. Notice also the differences in the types.

type 'a identity = 'a;;
let mid (x : 'a) : 'a = x;;
let mbind (xx : 'a) (k : 'a -> 'b) : 'b = k xx;;


and you used the ReaderT transformer to wrap the Identity monad inside Readerish packaging. What do you suppose you would get?

The relations between the State monad and the StateT monadic transformer are parallel:

(* monadic operations for the State monad *)

type 'a state =
store -> ('a * store);;

let mid (x : 'a) : 'a state =
fun s -> (x, s);;

let mbind (xx : 'a state) (k : 'a -> 'b state) : 'b state =
fun s -> (fun (x, s') -> k x s') (xx s);;


We've used (fun (x, s') -> k x s') (xx s) instead of the more familiar let (x, s') = xx s in k x s' in order to factor out the part where the payload of an 'a state value is supplied as an argument to a function. Now StateT will be:

(* monadic operations for the StateT monadic transformer *)

type 'a stateT(M) =
store -> ('a * store) M;;
(* notice this is not an ('a M) state *)

let mid (x : 'a) : 'a stateT(M) =
fun s -> M.mid (x, s);;

let mbind (xx : 'a stateT(M)) (k : 'a -> 'b stateT(M)) : 'b stateT(M) =
fun s -> M.mbind (xx s) (fun (x, s') -> k x s');;


Do you see the pattern? Where before mid was implemented by a function that returned an 'a * store value, now we instead use M.mid to return an ('a * store) M value. Where before mbind supplied an 'a state payload (xx s) as an argument to a function, now we instead M.mbind it to that function.

Once again, what do you think you'd get if you wrapped StateT monadic packaging around an Identity monad?

We spell out all the common monads, their common dedicated operations (such as asks- and shift-like operations for the Reader monad), and monad transformer cousins of all of these, in an OCaml ?monad library. Read the linked page for details about how to use the library, and some design choices we made. Our ?State Monad Tutorial gives some more examples of using the library. LINK TODO

When a T monadic layer encloses an inner M monad, the T's interface is the most exposed one. To use operations defined in the inner M monad, you'll have to hoist them into the outer T packaging. Haskell calls this operation lift, but we call it hoist because the term "lift" is already now too overloaded. The hoist operation brings monadic values or functions from a wrapped monad out into the wrapping.

Here's an example. Suppose S is an instance of a State monad:

# module S = Monad.State(struct type store = int end);;


and OS is a OptionT wrapped around S:

# module OS = Monad.Option.T(S);;


Then if you want to use an S-specific monad like modify succ inside OS, you'll have to use OS's hoist function, like this:

# OS.(...hoist (S.modify succ) ...)


Each monad transformer's hoist function will be defined differently. They have to obey the following laws:

• Outer.hoist (Inner.mid a) <~~> Outer.mid a
• Outer.hoist (Inner.mbind xx k) <~~> Outer.mbind (Outer.hoist xx) (fun x -> Outer.hoist (k x))

We said that when T encloses M, you can rely on T's interface to be most exposed. That is intuitive. What you cannot also assume is that the implementing type has a Tish structure surrounding an Mish structure. Often it will be reverse: a ListT(Option) is implemented by a 'a list option, not by an 'a option list. Until you've tried to write the code to a monadic transformer library yourself, this will probably remain counter-intuitive. But you don't need to concern yourself with it in practice. Think of what you have as a ListT(Option); don't worry about whether the underlying implementation is as an 'a list option or an 'a option list or as something more complicated.

(Except for the homework. There we do prompt you to experiment and figure some of these out. But you won't remember them.)

Notice from the code for StateT, above, that an 'a stateT(M) is not an ('a M) state; neither is it an ('a state) M. The pattern by which we transform the types from a Blah monad to a BlahT monad transformer is:

't0                  --->  't0 M
't1 -> 't0           --->  't1 -> 't0 M
('t1 -> 't0) -> 't0  --->  ('t1 -> 't0 M) -> 't0 M


Ken Shan's paper Monads for natural language semantics (2001) discusses how to systematically move from some base monads to the corresponding monad transformers. But as he notes, his algorithm isn't the only one possible, and it only applies to monads whose type has a certain form. (Reader and State have that form; List for example doesn't.)

As best we know, figuring out how a monad transformer should be defined is still something of an art, not something that can be done mechanically. However, you can think that all of the art goes into deciding what StateT and so on should be; having figured that out, plain State would follow as the simple case where StateT is parameterized on the Identity monad.

Apart from whose interface is outermost, the behavior of a StateT(Option) and a OptionT(State) will partly coincide. But in certain crucial respects they will diverge, and you need to think carefully about which behavior you want and what the appropriate layering is for your needs. Consider these examples:

# module OS = Monad.Option.T(S);;
# module SO = S.Z(Monad.Option);; (* we use S.Z instead of S.T because Monad.Option has a mzero *)
# OS.(run (hoist (S.modify succ) >> mzero >> hoist S.get >>= fun cur -> mid (cur+10) )) 0;;
- : int option * S.store = (None, 1)
# OS.(run (hoist (S.modify succ) >> mzero >> hoist (S.put 5) )) 0;;
- : unit option * S.store = (None, 1)


Although we have a wrapped None, notice that the store (as it was at the point of failure) was still retrievable.

# SO.(run (modify succ >> mzero >> get >>= fun cur -> mid (cur+10) )) 0;;
- : (int * S.store) Monad.Option.result = None


When Option is on the inside, on the other hand, as in SO, failure means the whole computation has failed, and even the store is no longer available.

Here's an example wrapping Option around List, and vice versa:

# module LO = Monad.List.T(Monad.Option);;
# module OL = Monad.Option.P(Monad.List);; (* we use the .P transformer to hoist List's ++ operation *)
# OL.(run (mzero ++ mid 20 >>= fun x -> mid (x+10) ));;
- : int OL.result = [Some 30]


When List is on the inside, the failed results just got dropped and the computation proceeds without them.

# LO.(run (hoist Monad.Option.mzero ++ mid 20 >>= fun x -> mid (x+10) ));;
- : int LO.result = None


On the other hand, when Option is on the inside, as in LO, failures (which we again represent by mzeros from the Option monad, not the List monad's own mzero; but here since it's the inner monad we need to hoist Monad.Option.mzero) abort the whole computation. (If you instead used the List monad's mzero, it'd be ignored by ++ and you'd end with just Some [30].)

This is fun. Here is a List around a List. Notice the difference it makes whether the second ++ is native to the outer Monad.List, or whether it's the inner Monad.List's ++ hoisted into the outer wrapper:

# module LL = Monad.List.T(Monad.List);;

# LL.(run(mid 1 ++ mid 2 >>= fun x -> mid x ++ mid (10*x) ));;
- : int LL.result = [[1; 10; 2; 20]]
#  LL.(run(mid 1 ++ mid 2 >>= fun x -> hoist Monad.List.(mid x ++ mid (10*x)) ));;
- : int LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]