+
+Do you see the pattern? Where before we'd return an `'a * store` value, now we instead return an `('a * store) M` value. Where before we'd supply a `'a state` value `(u s)` as an argument to a function, now we instead `M.bind` it to that function.
+
+Once again, what do you think you'd get if you wrapped a StateT monadic box around an Identity monad?
+
+Notice that an `('a, M) stateT` is not an `'a M state`. The pattern by which the types are transformed from an Blah monad to a BlahT monad transformer is:
+
+ 't0 ---> 't0 M
+ 't1 -> 't0 ---> 't1 -> 't0 M
+ ('t1 -> 't0) -> 't0 ---> ('t1 -> 't0 M) -> 't0 M
+
+Here's how this works for List and ListT:
+
+ (* monadic operations for the List monad *)
+
+ (* type 'a list is already pre-defined *)
+
+ let unit (a : 'a) : 'a list =
+ [a];;
+
+ let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
+ (fun v -> List.concat (List.map f v)) u
+
+ (* monadic operations for the ListT monadic transformer *)
+
+ type ('a, M) listT =
+ 'a list M;;
+
+ let unit (a : 'a) : 'a list =
+ [a];;
+
+ let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
+ (fun v -> List.concat (List.map f v)) u
+
+
+Some comments before we proceed:
+
+* Ken Shan's paper [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (2001) discusses how to systematically move from some plain 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 thet 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 ReaderT and so on should be; having figured that out, plain Reader would follow as the simple case where ReaderT is parameterized on the Identity monad.
+* We spell out all the common monads, their common dedicated operations (such as `lookup` for the Reader monad), and monad transformer cousins of all of these, in the following OCaml library: [[code/monads.ml]].
+