cleanup
[lambda.git] / monad_transformers.mdwn
index f370f4a..26fb13f 100644 (file)
@@ -1,5 +1,9 @@
+[[!toc]]
 
-So far, we've defined monads as single-layered things. Though in the Groenendijk, Stokhoff, and Veltmann homework, we had to figure out how to combine Reader, State, and Set monads in an ad-hoc way. In practice, one often wants to combine the abilities of several monads. Corresponding to each monad like Reader, there's a corresponding ReaderT **monad transformer**. That takes an existing monad M and wraps a Reader monad box around it. The way these are defined parallels the way the single-layer versions are defined. For example, here's the Reader monad:
+Multi-layered monadic boxes
+===========================
+
+So far, we've defined monads as single-layered boxes. Though in the Groenendijk, Stokhof, and Veltman homework, we had to figure out how to combine Reader, State, and Set monads in an ad-hoc way. In practice, one often wants to combine the abilities of several monads. Corresponding to each monad like Reader, there's a corresponding ReaderT **monad transformer**. That takes an existing monad M and wraps Readerish monad packaging around it. The way these are defined parallels the way the single-layer versions are defined. For example, here's the Reader monad:
 
        (* monadic operations for the Reader monad *)
 
@@ -8,41 +12,50 @@ So far, we've defined monads as single-layered things. Though in the Groenendijk
        let unit (a : 'a) : 'a reader =
                fun e -> a;;
        let bind (u: 'a reader) (f : 'a -> 'b reader) : 'b reader =
-               fun e -> (fun v -> f v e) (u e);;
+               fun e -> (fun a -> f a e) (u e);;
 
-We've just beta-expanded the familiar `f (u e) e` into `(fun v -> f v
+We've just beta-expanded the familiar `f (u e) e` into `(fun a -> f a
 e) (u e)`. We did that so as to factor out the parts where any Reader monad is
 being supplied as an argument to another function. That will help make some patterns that are coming up more salient.
 
-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?
+That was the plain Reader monad. Now if we want instead to wrap some other monad M inside Readerish 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 sometimes works. It's what we did in the hints to GSV assignment, where as we said, we "combined State and Set in an ad hoc way."
+
+But there are two problems: (1) It's cumbersome having to work with *both* `reader_bind` and `M.bind`. 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* `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.
+
+(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) t`s and so on.
 
-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."
+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.
 
-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.
+To be clear: ReaderT isn't itself a monad. It's a kind of Readerish packaging (wrapping paper) that converts one monadic box M into another monadic box ReaderT(M).
 
-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:
+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...
-        * 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 =
-               fun e -> M.bind (u e) (fun v -> f v e);;
+       let bind (u : 'a readerT(M)) (f : 'a -> 'b readerT(M)) : 'b readerT(M) =
+               fun e -> M.bind (u e) (fun a -> f a 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`
+Notice the key differences: where before `unit` was implemented by a function that just returned `a`, now we
+instead return `M.unit a`. Where before `bind` 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:
@@ -51,7 +64,7 @@ What is the relation between Reader and ReaderT? Well, suppose you started with
        let unit (a : 'a) : 'a = a;;
        let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
 
-and you used the ReaderT transformer to wrap the Identity monad inside Reader packaging. What do you suppose you would get?
+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:
 
@@ -70,66 +83,133 @@ 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 `unit` was implemented by a function that returned an `'a * store` value, now we instead use `M.unit` to return an `('a * store) M` value. Where before `bind` supplied an `'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 StateT monadic packaging around an Identity monad?
+
+
+We spell out all the common monads, their common dedicated operations (such as `lookup`- 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.
+
+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 "elevate" them into the outer T packaging. Haskell calls this operation `lift`, but we call it `elevate` because the term "lift" is already now too overloaded. In our usage, `lift` (and `lift2`) are functions that bring non-monadic operations into a monad; `elevate` brings monadic operations from a wrapped monad out into the wrapping.
+
+Here's an example. Suppose `S` is an instance of a State monad:
+
+       # #use "path/to/monads.ml";;
+       # module S = State_monad(struct type store = int end);;
+
+and `MS` is a MaybeT wrapped around `S`:
+
+       # module MS = Maybe_monad.T(S);;
+
+Then if you want to use an `S`-specific monad like `puts succ` inside `MS`, you'll have to use `MS`'s `elevate` function, like this:
 
-Once again, what do you think you'd get if you wrapped a StateT monadic box around an Identity monad?
+       # MS.(...elevate (S.puts succ) ...)
 
-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:
+Each monad transformer's `elevate` function will be defined differently. They have to obey the following laws:
+
+*      `Outer.elevate (Inner.unit a) <~~> Outer.unit a`
+*      `Outer.elevate (Inner.bind u f) <~~> Outer.bind (Outer.elevate u) (fun a -> Outer.elevate (f a))`
+
+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(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 counter-intuitive. 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.
+
+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
 
-Here's how this works for List and ListT:
+Ken Shan's paper [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (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.)
 
-       (* monadic operations for the List monad *)
+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.
 
-       (* type 'a list is already pre-defined *)
+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. Consider these examples:
 
-       let unit (a : 'a) : 'a list =
-               [a];;
+       # module MS = Maybe_monad.T(S);;
+       # module SM = S.T(Maybe_monad);;
+       # MS.(run (elevate (S.puts succ) >> zero () >> elevate S.get >>= fun cur -> unit (cur+10) )) 0;;
+       - : int option * S.store = (None, 1)
+       # MS.(run (elevate (S.puts succ) >> zero () >> elevate (S.put 5) )) 0;;
+       - : unit option * S.store = (None, 1)
 
-       let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
-               (fun v -> List.concat (List.map f v)) u
+Although we have a wrapped `None`, notice that the store (as it was at the point of failure) is still retrievable.
 
-       (* monadic operations for the ListT monadic transformer *)
+       # SM.(run (puts succ >> elevate (Maybe_monad.zero ()) >> get >>= fun cur -> unit (cur+10) )) 0;;
+       - : ('a, int * S.store) Maybe_monad.result = None
 
-       type ('a, M) listT =
-               'a list M;;
+When Maybe is on the inside, on the other hand, a failure means the whole computation has failed, and even the store is no longer available.
 
-       let unit (a : 'a) : 'a list =
-               [a];;
+<!--
+       # ES.(run( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i -> unit(i+10) )) 0;;
+       - : int Failure.error * S.store = (Failure.Error "bye", 1)
+       # SE.(run( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i -> unit(i+10) )) 0;;
+       - : (int * S.store) Failure.result = Failure.Error "bye"
+       # ES.(run_exn( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i -> unit(i+10) )) 0;;
+       Exception: Failure "bye".
+       # SE.(run_exn( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i -> unit(i+10) )) 0;;
+       Exception: Failure "bye".
+-->
 
-       let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
-               (fun v -> List.concat (List.map f v)) u
+Here's an example wrapping Maybe around List, and vice versa:
 
+       # module LM = List_monad.T(Maybe_monad);;
+       # module ML = Maybe_monad.T(List_monad);;
+       # ML.(run (plus (zero ()) (unit 20) >>= fun i -> unit (i+10)));;
+       - : ('_a, int) ML.result = [Some 30]
 
-Some comments before we proceed:
+When List is on the inside, the failed results just get dropped and the computation proceeds without them.
 
-*      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]].
+       # LM.(run (plus (elevate (Maybe_monad.zero ())) (unit 20) >>= fun i -> unit (i+10)));;
+       - : ('_a, int) LM.result = None
 
+On the other hand, when Maybe is on the inside, failures abort the whole computation.
 
 <!--
-This module is inspired by the paper Functional Programming with Overloading and Higher-Order Polymorphism, Mark P Jones (http://www.cse.ogi.edu/~mpj/) Advanced School of Functional Programming, 1995.
-http://web.cecs.pdx.edu/~mpj/pubs/springschool.html
-Mark Jones' influential paper that inspired the Haskell monad template library. 
+       # EL.(run( plus (throw "bye") (unit 20) >>= fun i -> unit(i+10)));;
+       - : int EL.result = [Failure.Error "bye"; Failure.Success 30]
+       # LE.(run( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i -> unit(i+10)));;
+       - : int LE.result = Failure.Error "bye"
+       # EL.(run_exn( plus (throw "bye") (unit 20) >>= fun i -> unit(i+10)));;
+       Exception: Failure "bye".
+       # LE.(run_exn( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i -> unit(i+10)));;
+       Exception: Failure "bye".
 -->
 
+This is fun. Notice the difference it makes whether the second `plus` is native to the outer `List_monad`, or whether it's the inner `List_monad`'s `plus` elevated into the outer wrapper:
+
+       # module LL = List_monad.T(List_monad);;
+
+       # LL.(run(plus (unit 1) (unit 2) >>= fun i -> plus (unit i) (unit(10*i)) ));;
+       - : ('_a, int) LL.result = \[[1; 10; 2; 20]]
+       # LL.(run(plus (unit 1) (unit 2) >>= fun i -> elevate L.(plus (unit i) (unit(10*i)) )));;
+       - : ('_a, int) LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
+
+
+
+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).
+
+
+Tree Monads
+===========
 
-Okay, now let's do the same thing for our Tree monad.
+Our [[monad library]] includes a `Tree_monad`, for binary, leaf-labeled 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/tree-monad/0.2.1/doc/html/src/Control-Monad-SearchTree.html#SearchTree) monad, our `Tree_monad` also incorporates an Optionish layer. (See the comments in our library code about `plus` and `zero` for discussion of why.)
+
+So how does our `Tree_monad` behave? Simplified, its implementation looks something like this:
 
        (* monadic operations for the Tree monad *)
 
@@ -142,36 +222,270 @@ 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 Optionish 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))` (really the tree itself needs to be wrapped in a `Some`, too, but let me neglect that) to `f'` would delete the 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 transform `Node (Leaf 1, Node (Leaf 2, Leaf 4))` instead into `Node (Leaf "two", Node (Leaf "two", Leaf "four"))`.
+
+As we [mention in the notes](/monad_library), our monad 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:
+
+       # 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
 
-       (* 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. *)
+You have to instead say something like this:
 
-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 -> plus (unit 2) (unit 4)
+           | _ -> zero () );;
+       - : ('_a, int) Tree_monad.m = <abstr>
+
+
+
+How is all this related to our tree\_monadize function?
+-------------------------------------------------------
+
+Our Tree monad has a corresponding TreeT transformer. Simplified, its implementation looks something like this (we apply it to an inner Reader monad):
+
+
+       type 'a tree_reader = 'a tree reader;;
+       (* really it's an 'a tree option reader, but as I said we're simplifying *)
+
+       let tree_reader_unit (a:'a) : 'a tree_reader = reader_unit (Leaf a);;
+
+       let tree_reader_bind (u: 'a tree_reader) (f: 'a -> 'b tree_reader) : 'b tree_reader =
+         reader_bind u (fun us ->
+               let rec loop us = match us with
+                 | Leaf a ->
+                 f a
+                 | Node(l,r) ->
+                         reader_bind (loop l) (fun ls ->
+                               reader_bind (loop r) (fun rs ->
+                                 reader_unit (Node(ls, rs))))
+               in loop us);;
+
+       let tree_reader_elevate (inner : 'a reader) : 'a tree_reader =
+               reader_bind inner (fun a -> reader_unit (Leaf a))
+
+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
-           | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
-           | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
-                              reader_bind (tree_monadize f r) (fun r' ->
-                                reader_unit (Node (l', r'))));;
+           | Leaf a ->
+                       (* the next line is equivalent to: tree_reader_elevate (f a) *)
+               reader_bind (f a) (fun b -> reader_unit (Leaf b))
+           | Node (l, r) ->
+               reader_bind (tree_monadize f l) (fun ls ->
+                 reader_bind (tree_monadize f r) (fun rs ->
+                   reader_unit (Node (ls, rs))));;
 
+We rendered the result type here as `'b tree reader`, as we did in our earlier discussion, but as we can see from the above implementation of TreeT(Reader), that's the type of an `'b tree_reader`, that is, of a layered box consisting of TreeT packaging wrapped around an inner Reader box.
+
+The definitions of `tree_monadize` and `tree_reader_bind` should look very similar. They're not quite the same. There's the difference in the order of their function-like and tree-like arguments, but that's inconsequential. More important is that the types of their arguments differs. `tree_reader_bind` wants a tree that's already fused with a reader; `tree_monadize` instead just wants a plain tree. `tree_reader_bind` wants a function that takes the elements occupying its leaves into other `tree_reader`s; `tree_monadize` just wants it to take them into plain `reader`s. That's why the application of `f` to `a` has to be `elevate`d in the `tree_monadize` clause for `Leaf a -> ...`.
+
+But there is an obvious common structure to these two functions, and indeed in the [[monad library]] their more complicated cousins are defined in terms of common pieces. In the monad library, the `tree_monadize` function is called `distribute`; this is an operation living inside the TreeT packaging. There's an analogous `distribute` function living inside the ListT packaging. (Haskell has the second but not the first; it calls it `mapM` and it lives inside the wrapped base monad, instead of the List packaging.)
+
+We linked to [some code](/code/tree_monadize.ml) earlier that demonstrated all the `tree_monadize` examples in a compact way.
+
+Here's how to demonstrate the same examples, using the monad library. First, preliminaries:
+
+       # #use "path/to/monads.ml";;
+       # module T = Tree_monad;;
+       # module R = Reader_monad(struct type env = int -> int end);;
+       # module S = State_monad(struct type store = int end);;
+       # module L = List_monad;;
+       # module C = Continuation_monad;;
+       # module TR = T.T(R);;
+       # module TS = T.T(S);;
+       # module TL = T.T(L);;
+       # module TC = T.T(C);;
+       # let t1 = Some (T.Node (T.Node (T.Leaf 2, T.Leaf 3), T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))));;
+
+We can use TreeT(Reader) to modify leaves:
+
+       # let tree_reader = TR.distribute (fun i -> R.asks (fun e -> e i)) t1;;
+       # TR.run tree_reader (fun i -> i+i);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 4, T.Leaf 6),
+               T.Node (T.Leaf 10, T.Node (T.Leaf 14, T.Leaf 22))))
+
+Here's a comparison of how distribute works for trees and how it works for lists:
+
+       # module LR = L.T(R);;
+       # let l1 = [2; 3; 5; 7; 11];;
+       # LR.(run (distribute (fun i -> R.(asks (fun e -> e i))) l1)) (fun i -> i+i);;
+       - : int list = [4; 6; 10; 14; 22]
+
+<!--
+More complex: here we use the monadic `list_reader` or `tree_reader` we got back from `distribute` and `bind` it to other operations:
+
+       # let u = LR.distribute (fun i -> R.(asks (fun e -> e i))) l1 in
+         LR.(run(u >>= fun i -> plus (unit i) (unit (10*i)))) (fun i -> i + i);;
+       - : int list = [4; 40; 6; 60; 10; 100; 14; 140; 22; 220]
+       # let v = TR.distribute (fun i -> R.(asks (fun e -> e i))) t1 in
+         TR.(run(v >>= fun i -> plus (unit i) (unit (10*i)))) (fun i -> i + i);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Node (T.Leaf 4, T.Leaf 40), T.Node (T.Leaf 6, T.Leaf 60)),
+               T.Node
+                (T.Node (T.Leaf 10, T.Leaf 100),
+                 T.Node (T.Node (T.Leaf 14, T.Leaf 140), T.Node (T.Leaf 22, T.Leaf 220)))))
+-->
+
+We can use TreeT(State) to count leaves:
+
+       # let tree_counter = TS.distribute (fun i -> S.(puts succ >> unit i)) t1 in
+         TS.run tree_counter 0;;
+       - : int T.tree option * S.store =
+       (Some
+         (T.Node
+               (T.Node (T.Leaf 2, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11)))),
+        5)
+
+or to annotate leaves:
+
+       # let tree_annotater = TS.distribute (fun i -> S.(puts succ >> get >>= fun s -> unit (i,s))) t1 in
+         TS.run tree_annotater 0;;
+       - : (int * S.store) T.tree option * S.store =
+       (Some
+         (T.Node
+               (T.Node (T.Leaf (2, 1), T.Leaf (3, 2)),
+                T.Node (T.Leaf (5, 3), T.Node (T.Leaf (7, 4), T.Leaf (11, 5))))),
+        5)
+
+Here's a comparison of how distribute works for trees and how it works for lists:
+
+       # module LS = L.T(S);;
+
+       # let list_counter = LS.distribute (fun i -> S.(puts succ >> unit i)) l1 in
+         LS.run list_counter 0;;
+       - : int list * S.store = ([2; 3; 5; 7; 11], 5)
+
+       # let list_annotater = LS.distribute (fun i -> S.(puts succ >> get >>= fun s -> unit (i,s) )) l1 in
+         LS.run list_annotater 0;;
+       - : (int * S.store) list * S.store =
+       ([(2, 1); (3, 2); (5, 3); (7, 4); (11, 5)], 5)
+
+
+<!--
+#   let u = LS.distribute (fun i -> if i = -1 then S.get else if i < 0 then S.(puts     succ >> unit 0) else S.unit i) [10;-1;-2;-1;20] in
+  LS.run u 0;;
+- : S.store list * S.store = ([10; 0; 0; 1; 20], 1)
+-->
+
+
+We can use TreeT(List) to copy the tree with different choices for some of the leaves:
+
+       # let tree_chooser = TL.distribute (fun i -> L.(if i = 2 then plus (unit 20) (unit 21) else unit i)) t1;;
+       # TL.run tree_chooser;;
+       - : ('_a, int) TL.result =
+       [Some
+         (T.Node
+               (T.Node (T.Leaf 20, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))));
+        Some
+         (T.Node
+               (T.Node (T.Leaf 21, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))))]
+
+
+Finally, we use TreeT(Continuation) to do various things. For reasons I won't explain here, the library currently requires you to run the Tree-plus-Continuation bundle using a different sequence of `run` commands:
+
+We can do nothing:
+<!--
+let initial_continuation = fun t -> t in
+TreeCont.monadize Continuation_monad.unit t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.unit t1)) (fun t -> t);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 2, T.Leaf 3),
+               T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))))
+
+We can square each leaf:
+<!--
+let initial_continuation = fun t -> t in
+TreeCont.monadize (fun a k -> k (a*a)) t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k (a*a))) t1)) (fun t -> t);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 4, T.Leaf 9),
+               T.Node (T.Leaf 25, T.Node (T.Leaf 49, T.Leaf 121))))
+
+The meaning of `shift` will be explained in [[CPS and Continuation Operators]]. Here you should just regard it as a primitive operation in our Continuation monad. In [this code](/code/tree_monadize.ml) you could simply write:
+
+       TreeCont.monadize (fun a -> fun k -> k (a*a)) t1 (fun t -> t);;
+
+But because of the way our monad library hides the underlying machinery, here you can no longer just say `fun k -> k (a*a)`; you have to say `shift (fun k -> k (a*a))`.
+
+Moving on, we can count the leaves:
+<!--
+let initial_continuation = fun t -> 0 in
+TreeCont.monadize (fun a k -> 1 + k a) t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k a >>= fun v -> unit (1+v))) t1)) (fun t -> 0);;
+       - : int = 5
+
+
+And we can convert the tree to a list of leaves:
+<!--
+let initial_continuation = fun t -> [] in
+TreeCont.monadize (fun a k -> a :: k a) t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k a >>= fun v -> unit (a::v))) t1)) (fun t -> []);;
+       - : int list = [2; 3; 5; 7; 11]
 
-*      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).