From: Jim Pryor
Date: Sun, 12 Dec 2010 22:24:32 +0000 (0500)
Subject: expand transformers
XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=e32623b19bb5a3fd40ada29c912c7ecfc5784fab
expand transformers
Signedoffby: Jim Pryor

diff git a/monad_transformers.mdwn b/monad_transformers.mdwn
index f370f4a1..8e459f0b 100644
 a/monad_transformers.mdwn
+++ b/monad_transformers.mdwn
@@ 16,33 +16,40 @@ being supplied as an argument to another function. That will help make some patt
That was the plain Reader monad. Now if we want instead to wrap some other monad M inside Reader packaging. How could we do it?
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_bind` to get at the wrapped `'a M`, and then apply `M.bind` to get at *its* wrapped `'a`. This works. It's what we did in the hints to GSV assignment, where we said we "combined State and Set in an ad hoc way."
+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_bind` to get at the wrapped `'a M`, and then apply `M.bind` to get at *its* wrapped `'a`. This sometimes works. It's what we did in the hints to GSV assignment, where we said we "combined State and Set in an ad hoc way."
It's be nice to figure out some systematic way to connect the plumbing of the different monadic layers, though, so that we could have a *single* `bind` that took our `'a M_inside_Reader`, and sequenced it with a single `'a > 'b M_inside_Reader` function. Similarly for `unit`. This is what the ReaderT monad transformer lets us do.
+But there are two problems: (1) It's cumbersome having to work with *both* `reader_bind` and `M.bind`. It's be nice to figure out some systematic way to connect the plumbing of the different monadic layers, though, so that we could have a *single* `bind` that took our `'a M_inside_Reader`, and sequenced it with a single `'a > 'b M_inside_Reader` function. Similarly for `unit`. This is what the ReaderT monad transformer will let us do.
A ReaderT transformer will be parameterized not just on the type of its innermost contents `'a`, but also on the monadic box `M` that wraps `'a`. It will make use of monad `M`'s existing operations `M.unit` and `M.bind`. Here's how we do it:
+(2) For some combinations of monads, the best way to implement an X monadic wrapper around an inner M monad won't be equivalent to either an `('a m) x` or an `('a x) m`. It will be a tighether intermingling of the two. So some natural activities will remain out of reach until we equip ourselves to go beyond `('a m) x`s 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 contents `'a`, but also on the monadic box `M` that wraps `'a`. It will make use of monad `M`'s existing operations `M.unit` and `M.bind`, together with the Reader patterns for unit and bind, to define a new monad ReaderT(M) that fuses the behavior of Reader and M.
+
+Here's how we do it:
(* 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...
 * see http://lambda.jimpryor.net/code/tree_monadize.ml for some details. *)
+ * see http://lambda.jimpryor.net/code/tree_monadize.ml
+ * and http://lambda.jimpryor.net/code/monads.ml
+ * for some details. *)
 type (M, 'a) readerT =
+ type 'a readerT(M) =
env > 'a M;;
 (* this happens also to be the type of an ('a M) reader; but don't rely on that pattern to generalize *)
+ (* 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 unit (a : 'a) : (M, 'a) readerT =
+ let unit (a : 'a) : 'a readerT(M) =
fun e > M.unit a;;
 let bind (u : (M, 'a) readerT) (f : 'a > (M, 'b) readerT) : (M, 'b) readerT =
+ let bind (u : 'a readerT(M)) (f : 'a > 'b readerT(M)) : 'b readerT(M) =
fun e > M.bind (u e) (fun v > f v e);;
Notice the key differences: where before we just returned `a`, now we
instead return `M.unit a`. Where before we just supplied value `u e`
of type `'a reader` as an argument to a function, now we instead
`M.bind` the `'a reader` to that function. Notice also the differences
+`M.bind` the corresponding value to the function. Notice also the differences
in the types.
What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
@@ 70,66 +77,43 @@ We've used `(fun (a, s') > f a s') (u s)` instead of the more familiar `let (a,
(* monadic operations for the StateT monadic transformer *)
 type (M, 'a) stateT =
+ type 'a stateT(M) =
store > ('a * store) M;;
(* notice this is not an ('a M) state *)
 let unit (a : 'a) : (M, 'a) stateT =
+ let unit (a : 'a) : 'a stateT(M) =
fun s > M.unit (a, s);;
 let bind (u : (M, 'a) stateT) (f : 'a > (M, 'b) stateT) : (M, 'b) stateT =
+ let bind (u : 'a stateT(M)) (f : 'a > 'b stateT(M)) : 'b stateT(M) =
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.
+Do you see the pattern? Where before we'd return an `'a * store` value, now we instead use `M.unit` to 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:
+Notice that an `'a stateT(M)` 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 predefined *)

 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;;
+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 need to use T's `elevate` function on them. This brings the Mbased operation into the TaroundM monadic bundle. Haskell calls this `lift` (MORE...)
 let unit (a : 'a) : 'a list =
 [a];;
+We said that when T is around 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 the Tlike type structure surrounding an Mlike structure. Often it will be reverse: a ListT(Maybe) 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 counterintuitive. But you don't need to concern yourself with it in practise. Think of what you have as a ListT(Maybe); don't worry about whether the underlying implementation is as an `'a list option` or an `'a option list` or as something more complicated. (As we noted, an `'a stateT(M)` is not an `('a M) state` nor an `('a state) M`.)
 let bind (u : 'a list) (f : 'a > 'b list) : 'b list =
 (fun v > List.concat (List.map f v)) u
+Apart from whose interface is outermost, the behavior of a StateT(Maybe) and a MaybeT(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. (MORE...)
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.)
* 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]].
+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 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.

+Our library includes a `Tree_monad`, for binary, leaflabeled trees. There are other kinds of trees you might want to monadize, but we took the name `Tree_monad` for this one. Like the Haskell [SearchTree](http://hackage.haskell.org/packages/archive/treemonad/0.2.1/doc/html/src/ControlMonadSearchTree.html#SearchTree) monad, our `Tree_monad` also incorporates an optionlike layer. (See the comments in our library code about `plus` and `zero` for some discussion of why.)

Okay, now let's do the same thing for our Tree monad.
+So how does our `Tree_monad` behave? Simplified, its implementation would look something like this:
(* monadic operations for the Tree monad *)
@@ 142,27 +126,80 @@ Okay, now let's do the same thing for our Tree monad.
let rec bind (u : 'a tree) (f : 'a > 'b tree) : 'b tree =
match u with
 Leaf a > f a;;
  Node (l, r) > (fun l' r' > Node (l', r')) (bind l f) (bind r f);;
+  Node (l, r) >
+ let l' = bind l f in
+ let r' = bind r f in
+ Node (l', r')
 (* monadic operations for the TreeT monadic transformer *)
 (* NOTE THIS IS NOT YET WORKING  STILL REFINING *)
+Recall how `bind` works for the List monad. If you have a list:
 type (M, 'a) treeT =
 'a tree M;;
+ let u = [1; 2; 4; 8];;
 let unit (a: 'a) : (M, 'a) tree =
 M.unit (Leaf a);;
+and a function `f` such that:
 let rec bind (u : (M, 'a) tree) (f : 'a > (M, 'b) tree) : (M, 'b) tree =
 match u with
  Leaf a > M.bind (f a) (fun b > M.unit (Leaf b))
  Node (l, r) > M.bind (bind l f) (fun l' >
 M.bind (bind r f) (fun r' >
 M.unit (Node (l', r'));;
+ f 1 ~~> []
+ f 2 ~~> [2]
+ f 4 ~~> [2; 4]
+ f 8 ~~> [2; 4; 8]
+
+then `list_bind u f` would be `concat [[]; [2]; [2; 4]; [2; 4; 8]]`, that is `[2; 2; 4; 2; 4; 8]`. It splices the lists returned by `f` into the corresponding positions in the original list structure. The `tree_bind` operation works the same way. If `f'` maps `2` to the tree `Leaf 2` and `8` to the tree `Node (Leaf 2, Node (Leaf 4, Leaf 8))`, then binding the tree `u` to `f'` will splice the trees returned by `f'` to the corresponding positions in the original structure:
+
+ u
+ . .
+ ___ >>= f' ~~> ___
+    
+ 2 8 2 .
+ ___
+  
+ 2 .
+ ___
+  
+ 4 8
+
+Except, as we mentioned, our implementation of the Tree monad incorporates an optionlike layer too. So `f' 2` should be not `Leaf 2` but `Some (Leaf 2)`. What if `f'` also mapped `1` to `None` and `4` to `Some (Node (Leaf 2, Leaf 4))`. Then binding the tree `Node (Leaf 1, Node (Leaf 2, Leaf 4))` to `f'` would delete thr branch corresponding to the original `Leaf 1`, and would splice in the results for `f' 2` and `f' 4`, yielding:
+
+ .
+ ___ >>= f' ~~>
+  
+ 1 . .
+ ___ ___
+    
+ 2 4 2 .
+ ___
+  
+ 2 4
+
+As always, the functions you bind an `'a tree` to need not map `'a`s to `'a tree`s; they can map them to `'b tree`s instead. For instance, we could map `Node (Leaf 1, Node (Leaf 2, Leaf 4))` instead to `Node (Leaf "two", Node (Leaf "two", Leaf "four"))`.
 (* 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. *)
+As we mention in the notes to the [[monad library]], the library encapsulates the implementation of its monadic types. So to work with it you have to use the primitives it provides. You can't say:
Compare this definition of `bind` for the TreeT monadic transformer to our earlier definition of `tree_monadize`, specialized for the Reader monad:
+ # Tree_monad.(orig_tree >>= fun a > match a with
+  4 > Some (Node (Leaf 2, Leaf 4))
+  _ > None);;
+ Error: This expression has type int Tree_monad.tree option
+ but an expression was expected of type ('a, 'b) Tree_monad.m
+
+You have to instead say something like this:
+
+ # Tree_monad.(orig_tree >>= fun a > match a with
+  4 > plus (unit 2) (unit 4)
+  _ > zero () );;
+  : ('_a, int) Tree_monad.m =
+
+
+Further Reading
+
+
+* This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.grabmueller.de/martin/www/pub/Transformers.pdf)
+
+* Read Part III of [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. Some but not all of this site has been [absorbed into the Haskell wikibook](http://en.wikibooks.org/wiki/Haskell/Monad_transformers).
+
+
+How is all this related to our tree\_monadize function?
+
+
+
+Recall 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 =
match t with
@@ 172,6 +209,5 @@ Compare this definition of `bind` for the TreeT monadic transformer to our earli
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 Part III of [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. Some but not all of this site has been [absorbed into the Haskell wikibook](http://en.wikibooks.org/wiki/Haskell/Monad_transformers).
+(MORE...)