let bind (u : (M, 'a) stateT) (f : 'a -> (M, 'b) stateT) : (M, 'b) stateT =
fun s -> M.bind (u s) (fun (a, s') -> f a s');;
+
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.)
* 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]].
-
Okay, now let's do the same thing for our Tree monad.
(* monadic operations for the Tree monad *)
M.bind (bind r f) (fun r' ->
M.unit (Node (l', r'));;
+ (* problems --- why isn't Leaf clause simpler? trying to match u as if it were a tree. u and f's type is different than in tree_monadize. *)
+
Compare this definition of `bind` for the TreeT monadic transformer to our earlier definition of `tree_monadize`, specialized for the Reader monad:
let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
reader_unit (Node (l', r'))));;
+* This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.grabmueller.de/martin/www/pub/Transformers.pdf)
+* Read more about Monad Transformers [at the Haskell wikibook](http://en.wikibooks.org/wiki/Haskell/Monad_transformers)
+* Read more at [All About Monads](http://web.archive.org/web/20071106232016/haskell.org/all_about_monads/html/introIII.html). This link is to an archived version, the main link to haskell.org seems to be broken.
+