X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=23abaa63ed33444ca1b3a6dd69fad974f4a8bb9d;hp=52b8508c58e8a94885473647130cdcf4c8f26bfa;hb=3d8a5a49ed7026e8a1bf68fa4c054a50925c1bb6;hpb=3b908cb0f0b83c55ea4e336f80ecc273a87d128f

diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 52b8508c..23abaa63 100644
--- a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ -22,7 +22,7 @@ the utility of replacing one monad with other.
 First, we'll be needing a lot of trees for the remainder of the
 course.  Here again is a type constructor for leaf-labeled, binary trees:
 
-    type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
+    type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree);;
 
 [How would you adjust the type constructor to allow for labels on the
 internal nodes?]
@@ -46,18 +46,18 @@ We'll be using trees where the nodes are integers, e.g.,
 
 Our first task will be to replace each leaf with its double:
 
-	let rec tree_map (leaf_modifier : 'a -> 'b) (t : 'a tree) : 'b tree =
+	let rec tree_map (t : 'a tree) (leaf_modifier : 'a -> 'b): 'b tree =
 	  match t with
 	    | Leaf i -> Leaf (leaf_modifier i)
-	    | Node (l, r) -> Node (tree_map leaf_modifier l,
-	                           tree_map leaf_modifier r);;
+	    | Node (l, r) -> Node (tree_map l leaf_modifier,
+	                           tree_map r leaf_modifier);;
 
-`tree_map` takes a function that transforms old leaves into new leaves,
-and maps that function over all the leaves in the tree, leaving the
-structure of the tree unchanged.  For instance:
+`tree_map` takes a tree and a function that transforms old leaves into
+new leaves, and maps that function over all the leaves in the tree,
+leaving the structure of the tree unchanged.  For instance:
 
 	let double i = i + i;;
-	tree_map double t1;;
+	tree_map t1 double;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
 	
@@ -80,8 +80,8 @@ each leaf instead by supplying the appropriate `int -> int` operation
 in place of `double`:
 
 	let square i = i * i;;
-	tree_map square t1;;
-	- : int tree =ppp
+	tree_map t1 square;;
+	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
 Note that what `tree_map` does is take some unchanging contextual
@@ -95,8 +95,6 @@ a Reader monad---is to have the `tree_map` function return a (monadized)
 tree that is ready to accept any `int -> int` function and produce the
 updated tree.
 
-\tree (. (. (f 2) (f 3)) (. (f 5) (. (f 7) (f 11))))
-
 	\f      .
 	   _____|____
 	   |        |
@@ -116,7 +114,7 @@ with `f i`.
 
 [Application note: this kind of reader object could provide a model
 for Kaplan's characters.  It turns an ordinary tree into one that
-expects contextual information (here, the `λ f`) that can be
+expects contextual information (here, the `\f`) that can be
 used to compute the content of indexicals embedded arbitrarily deeply
 in the tree.]
 
@@ -145,11 +143,11 @@ function of type `int -> int` to.
 
 But we can do this:
 
-	let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b reader) : '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' ->
+	    | Node (l, r) -> reader_bind (tree_monadize l f) (fun l' ->
+	                       reader_bind (tree_monadize r f) (fun r' ->
 	                         reader_unit (Node (l', r'))));;
 
 This function says: give me a function `f` that knows how to turn
@@ -187,17 +185,17 @@ Then we can expect that supplying it to our `int tree reader` will double all th
 In more fanciful terms, the `tree_monadize` function builds plumbing that connects all of the leaves of a tree into one connected monadic network; it threads the
 `'b reader` monad through the original tree's leaves.
 
-	# tree_monadize int_readerize t1 double;;
+	# tree_monadize t1 int_readerize double;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
 
 Here, our environment is the doubling function (`fun i -> i + i`).  If
 we apply the very same `int tree reader` (namely, `tree_monadize
-int_readerize t1`) to a different `int -> int` function---say, the
+t1 int_readerize`) to a different `int -> int` function---say, the
 squaring function, `fun i -> i * i`---we get an entirely different
 result:
 
-	# tree_monadize int_readerize t1 square;;
+	# tree_monadize t1 int_readerize square;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
@@ -215,16 +213,16 @@ Gratifyingly, we can use the `tree_monadize` function without any
 modification whatsoever, except for replacing the (parametric) type
 `'b reader` with `'b state`, and substituting in the appropriate unit and bind:
 
-	let rec tree_monadize (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b state) : 'b tree state =
 	    match t with
 	    | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
-	    | Node (l, r) -> state_bind (tree_monadize f l) (fun l' ->
-	                       state_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> state_bind (tree_monadize l f) (fun l' ->
+	                       state_bind (tree_monadize r f) (fun r' ->
 	                         state_unit (Node (l', r'))));;
 
 Then we can count the number of leaves in the tree:
 
-	# tree_monadize (fun a -> fun s -> (a, s+1)) t1 0;;
+	# tree_monadize t1 (fun a -> fun s -> (a, s+1)) 0;;
 	- : int tree * int =
 	(Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 5)
 	
@@ -248,10 +246,41 @@ increments the state. When we give that same operations to our
 `tree_monadize` function, it then wraps an `int tree` in a box, one
 that does the same state-incrementing for each of its leaves.
 
+We can use the state monad to replace leaves with a number
+corresponding to that leave's ordinal position.  When we do so, we
+reveal the order in which the monadic tree forces evaluation:
+
+        # tree_monadize t1 (fun a -> fun s -> (s+1, s+1)) 0;;
+        - : int tree * int =
+        (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)
+
+The key thing to notice is that instead of copying `a` into the
+monadic box, we throw away the `a` and put a copy of the state in
+instead.
+
+Reversing the order requires reversing the order of the state_bind
+operations.  It's not obvious that this will type correctly, so think
+it through:
+
+	let rec tree_monadize_rev (t : 'a tree) (f : 'a -> 'b state) : 'b tree state =
+	    match t with
+	    | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+	    | Node (l, r) -> state_bind (tree_monadize r f) (fun r' ->	   (* R first *)
+	                       state_bind (tree_monadize l f) (fun l'->    (* Then L  *)
+	                         state_unit (Node (l', r'))));;
+
+        # tree_monadize_rev t1 (fun a -> fun s -> (s+1, s+1)) 0;;
+        - : int tree * int =
+        (Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)
+
+We will need below to depend on controlling the order in which nodes
+are visited when we use the continuation monad to solve the
+same-fringe problem.
+
 One more revealing example before getting down to business: replacing
 `state` everywhere in `tree_monadize` with `list` gives us
 
-	# tree_monadize (fun i -> [ [i; square i] ]) t1;;
+	# tree_monadize t1 (fun i -> [ [i; square i] ]);;
 	- : int list tree list =
 	[Node
 	  (Node (Leaf [2; 4], Leaf [3; 9]),
@@ -259,9 +288,9 @@ One more revealing example before getting down to business: replacing
 
 Unlike the previous cases, instead of turning a tree into a function
 from some input to a result, this transformer replaces each `int` with
-a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun -> [ i; [2*i; 3*i] ]`. Use small trees for your experiment.
+a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun i -> [2*i; 3*i]`. Use small trees for your experiment.
 
-[Why is the argument to tree_monadize `int -> int list list` instead
+[Why is the argument to `tree_monadize` `int -> int list list` instead
 of `int -> int list`?  Well, as usual, the List monad bind operation
 will erase the outer list box, so if we want to replace the leaves
 with lists, we have to nest the replacement lists inside a disposable
@@ -274,11 +303,11 @@ of leaves?
 	let continuation_unit a = fun k -> k a;;
 	let continuation_bind u f = fun k -> u (fun a -> f a k);;
 	
-	let rec tree_monadize (f : 'a -> ('b, 'r) continuation) (t : 'a tree) : ('b tree, 'r) continuation =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> ('b, 'r) continuation) : ('b tree, 'r) continuation =
 	    match t with
 	    | Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b))
-	    | Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' ->
-	                       continuation_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> continuation_bind (tree_monadize l f) (fun l' ->
+	                       continuation_bind (tree_monadize r f) (fun r' ->
 	                         continuation_unit (Node (l', r'))));;
 
 We use the Continuation monad described above, and insert the
@@ -286,10 +315,21 @@ We use the Continuation monad described above, and insert the
 
 So for example, we compute:
 
-	# tree_monadize (fun a -> fun k -> a :: k a) t1 (fun t -> []);;
+	# tree_monadize t1 (fun a k -> a :: k ()) (fun _ -> []);;
 	- : int list = [2; 3; 5; 7; 11]
 
-We have found a way of collapsing a tree into a list of its leaves. Can you trace how this is working? Think first about what the operation `fun a -> fun k -> a :: k a` does when you apply it to a plain `int`, and the continuation `fun _ -> []`. Then given what we've said about `tree_monadize`, what should we expect `tree_monadize (fun a -> fun k -> a :: k a` to do?
+We have found a way of collapsing a tree into a list of its
+leaves. Can you trace how this is working? Think first about what the
+operation `fun a k -> a :: k a` does when you apply it to a
+plain `int`, and the continuation `fun _ -> []`. Then given what we've
+said about `tree_monadize`, what should we expect `tree_monadize (fun
+a -> fun k -> a :: k a` to do?
+
+Soon we'll return to the same-fringe problem.  Since the
+simple but inefficient way to solve it is to map each tree to a list
+of its leaves, this transformation is on the path to a more efficient
+solution.  We'll just have to figure out how to postpone computing the
+tail of the list until it's needed...
 
 The Continuation monad is amazingly flexible; we can use it to
 simulate some of the computations performed above.  To see how, first
@@ -297,7 +337,7 @@ note that an interestingly uninteresting thing happens if we use
 `continuation_unit` as our first argument to `tree_monadize`, and then
 apply the result to the identity function:
 
-	# tree_monadize continuation_unit t1 (fun t -> t);;
+	# tree_monadize t1 continuation_unit (fun t -> t);;
 	- : int tree =
 	Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11)))
 
@@ -305,28 +345,122 @@ That is, nothing happens.  But we can begin to substitute more
 interesting functions for the first argument of `tree_monadize`:
 
 	(* Simulating the tree reader: distributing a operation over the leaves *)
-	# tree_monadize (fun a -> fun k -> k (square a)) t1 (fun t -> t);;
+	# tree_monadize t1 (fun a -> fun k -> k (square a)) (fun t -> t);;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
 	(* Simulating the int list tree list *)
-	# tree_monadize (fun a -> fun k -> k [a; square a]) t1 (fun t -> t);;
+	# tree_monadize t1 (fun a -> fun k -> k [a; square a]) (fun t -> t);;
 	- : int list tree =
 	Node
 	 (Node (Leaf [2; 4], Leaf [3; 9]),
 	  Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))
 
 	(* Counting leaves *)
-	# tree_monadize (fun a -> fun k -> 1 + k a) t1 (fun t -> 0);;
+	# tree_monadize t1 (fun a -> fun k -> 1 + k a) (fun t -> 0);;
 	- : int = 5
 
-We could simulate the tree state example too, but it would require
-generalizing the type of the Continuation monad to
+[To be fixed: exactly which kind of monad each of these computations simulates.]
+
+We could simulate the tree state example too by setting the relevant 
+type to `('a, 'state -> 'result) continuation`.
+In fact, Andre Filinsky has suggested that the continuation monad is
+able to simulate any other monad (Google for "mother of all monads").
+
+We would eventually want to generalize the continuation type to
 
 	type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
 
 If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml).
 
+The idea of using continuations to characterize natural language meaning
+------------------------------------------------------------------------
+
+We might a philosopher or a linguist be interested in continuations,
+especially if efficiency of computation is usually not an issue?
+Well, the application of continuations to the same-fringe problem
+shows that continuations can manage order of evaluation in a
+well-controlled manner.  In a series of papers, one of us (Barker) and
+Ken Shan have argued that a number of phenomena in natural langauge
+semantics are sensitive to the order of evaluation.  We can't
+reproduce all of the intricate arguments here, but we can give a sense
+of how the analyses use continuations to achieve an analysis of
+natural language meaning.
+
+**Quantification and default quantifier scope construal**.  
+
+We saw in the copy-string example and in the same-fringe example that
+local properties of a tree (whether a character is `S` or not, which
+integer occurs at some leaf position) can control global properties of
+the computation (whether the preceeding string is copied or not,
+whether the computation halts or proceeds).  Local control of
+surrounding context is a reasonable description of in-situ
+quantification.
+
+    (1) John saw everyone yesterday.
+
+This sentence means (roughly)
+
+    forall x . yesterday(saw x) john
+
+That is, the quantifier *everyone* contributes a variable in the
+direct object position, and a universal quantifier that takes scope
+over the whole sentence.  If we have a lexical meaning function like
+the following:
+
+<pre>
+let lex (s:string) k = match s with 
+  | "everyone" -> Node (Leaf "forall x", k "x")
+  | "someone" -> Node (Leaf "exists y", k "y")
+  | _ -> k s;;
+
+let sentence1 = Node (Leaf "John", 
+                      Node (Node (Leaf "saw", 
+                                  Leaf "everyone"), 
+                            Leaf "yesterday"));;
+</pre>
+
+Then we can crudely approximate quantification as follows:
+
+<pre>
+# tree_monadize sentence1 lex (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "forall x",
+  Node (Leaf "John", Node (Node (Leaf "saw", Leaf "x"), Leaf "yesterday")))
+</pre>
+
+In order to see the effects of evaluation order, 
+observe what happens when we combine two quantifiers in the same
+sentence:
+
+<pre>
+# let sentence2 = Node (Leaf "everyone", Node (Leaf "saw", Leaf "someone"));;
+# tree_monadize sentence2 lex (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "forall x",
+  Node (Leaf "exists y", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))
+</pre>
+
+The universal takes scope over the existential.  If, however, we
+replace the usual tree_monadizer with tree_monadizer_rev, we get
+inverse scope:
+
+<pre>
+# tree_monadize_rev sentence2 lex (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "exists y",
+  Node (Leaf "forall x", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))
+</pre>
+
+There are many crucially important details about quantification that
+are being simplified here, and the continuation treatment here is not
+scalable for a number of reasons.  Nevertheless, it will serve to give
+an idea of how continuations can provide insight into the behavior of
+quantifiers.  
+
 
 The Binary Tree monad
 ---------------------
@@ -352,8 +486,6 @@ induction on the structure of the first argument that the tree
 resulting from `bind u f` is a tree with the same strucure as `u`,
 except that each leaf `a` has been replaced with `f a`:
 
-\tree (. (f a1) (. (. (. (f a2) (f a3)) (f a4)) (f a5)))
-
 	                .                         .
 	              __|__                     __|__
 	              |   |                     |   |
@@ -383,9 +515,6 @@ As for the associative law,
 we'll give an example that will show how an inductive proof would
 proceed.  Let `f a = Node (Leaf a, Leaf a)`.  Then
 
-\tree (. (. (. (. (a1) (a2)))))
-\tree (. (. (. (. (a1) (a1)) (. (a1) (a1)))))
-
 	                                           .
 	                                       ____|____
 	          .               .            |       |
@@ -416,7 +545,7 @@ called a
 that is intended to represent non-deterministic computations as a tree.
 
 
-What's this have to do with tree\_mondadize?
+What's this have to do with tree\_monadize?
 --------------------------------------------
 
 So we've defined a Tree monad:
@@ -430,122 +559,26 @@ So we've defined a Tree monad:
 
 What's this have to do with the `tree_monadize` functions we defined earlier?
 
-	let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b reader) : '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' ->
+	    | Node (l, r) -> reader_bind (tree_monadize l f) (fun l' ->
+	                       reader_bind (tree_monadize r f) (fun r' ->
 	                         reader_unit (Node (l', r'))));;
 
 ... and so on for different monads?
 
-The answer is that each of those `tree_monadize` functions is adding a Tree monad *layer* to a pre-existing Reader (and so on) monad. 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 adds a Reader monad layer to 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 *)
-
-	type 'a reader =
-		env -> 'a;;
-	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);;
-
-We've just beta-expanded the familiar `f (u e) e` into `(fun v -> f v e) (u e)`, in order to factor out the parts where any Reader monad is being supplied as an argument to another function. Then if we want instead to add a Reader layer to some arbitrary other monad M, with its own M.unit and M.bind, 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. *)
-
-	type ('a, M) readerT =
-		env -> 'a M;;
-	(* this is just an 'a M reader; but don't rely on that pattern to generalize *)
-
-	let unit (a : 'a) : ('a, M) readerT =
-		fun e -> M.unit a;;
-
-	let bind (u : ('a, M) readerT) (f : 'a -> ('b, M) readerT) : ('b, M) readerT =
-		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 in the types.
-
-What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
+Well, notice that `tree\_monadizer` takes arguments whose types
+resemble that of a monadic `bind` function.  Here's a schematic bind
+function compared with `tree\_monadizer`:
 
-	type 'a identity = 'a;;
-	let unit (a : 'a) : 'a = a;;
-	let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
-
-and you used the ReaderT transformer to add a Reader monad layer to the Identity monad. 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 unit (a : 'a) : 'a state =
-		fun s -> (a, s);;
-
-	let bind (u : 'a state) (f : 'a -> 'b state) : 'b state =
-		fun s -> (fun (a, s') -> f a s') (u s);;
-
-We've used `(fun (a, s') -> f a s') (u s)` instead of the more familiar `let (a, s') = u s in f a s'` in order to factor out the part where a value of type `'a state` is supplied as an argument to a function. Now StateT will be:
-
-	(* monadic operations for the StateT monadic transformer *)
-
-	type ('a, M) stateT =
-		store -> ('a * store) M;;
-	(* notice this is not an 'a M state *)
-
-	let unit (a : 'a) : ('a, M) stateT =
-		fun s -> M.unit (a, s);;
-
-	let bind (u : ('a, M) stateT) (f : 'a -> ('b, M) stateT) : ('b, M) stateT =
-		fun s -> M.bind (u s) (fun (a, s') -> f a s');;
-
-Do you see the pattern? Where ordinarily we'd return an `'a` value, now we instead return an `'a M` value. Where ordinarily we'd supply a `'a state` value as an argument to a function, now we instead `M.bind` it to that function.
-
-Okay, now let's do the same thing for our Tree monad.
-
-	(* monadic operations for the Tree monad *)
-
-	type 'a tree =
-		Leaf of 'a | Node of ('a tree) * ('a tree);;
-
-	let unit (a: 'a) : 'a tree =
-		Leaf a;;
-
-	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);;
-
-	(* monadic operations for the TreeT monadic transformer *)
-	(* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)
-
-	type ('a, M) treeT =
-		'a tree M;;
-
-	let unit (a: 'a) : ('a, M) tree =
-		M.unit (Leaf a);;
-
-	let rec bind (u : ('a, M) tree) (f : 'a -> ('b, M) tree) : ('b, M) 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'));;
-
-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 =
-	    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'))));;
+          bind             (u:'a Monad) (f: 'a -> 'b Monad): 'b Monad
+          tree\_monadizer  (u:'a Tree)  (f: 'a -> 'b Monad): 'b Tree Monad 
 
+Comparing these types makes it clear that `tree\_monadizer` provides a
+way to distribute an arbitrary monad M across the leaves of any tree to
+form a new tree inside an M box.
 
+The more general answer is that each of those `tree\_monadize`
+functions is adding a Tree monad *layer* to a pre-existing Reader (and
+so on) monad. We discuss that further here: [[Monad Transformers]].