From: Chris Barker <barker@kappa.linguistics.fas.nyu.edu>
Date: Wed, 8 Dec 2010 22:43:32 +0000 (-0500)
Subject: edits
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=5fda6b40cf467cf820cf7ecf022ac796dd0e316b

edits
---

diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 3247ce62..23abaa63 100644
--- a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ -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,7 +80,7 @@ each leaf instead by supplying the appropriate `int -> int` operation
 in place of `double`:
 
 	let square i = i * i;;
-	tree_map square t1;;
+	tree_map t1 square;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
@@ -114,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 `&lambda; 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.]
 
@@ -143,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
@@ -185,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)))
 
@@ -213,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)
 	
@@ -250,7 +250,7 @@ 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 (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        # 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)
 
@@ -262,14 +262,14 @@ 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 (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+	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 f r) (fun r' ->	   (* R first *)
-	                       state_bind (tree_monadize f l) (fun l'->    (* Then L  *)
+	    | 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 (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        # 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)
 
@@ -280,7 +280,7 @@ 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]),
@@ -303,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
@@ -315,12 +315,12 @@ 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
+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?
@@ -337,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)))
 
@@ -345,19 +345,19 @@ 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
 
 [To be fixed: exactly which kind of monad each of these computations simulates.]
@@ -423,7 +423,7 @@ let sentence1 = Node (Leaf "John",
 Then we can crudely approximate quantification as follows:
 
 <pre>
-# tree_monadize lex sentence1 (fun x -> x);;
+# tree_monadize sentence1 lex (fun x -> x);;
 - : string tree =
 Node
  (Leaf "forall x",
@@ -436,7 +436,7 @@ sentence:
 
 <pre>
 # let sentence2 = Node (Leaf "everyone", Node (Leaf "saw", Leaf "someone"));;
-# tree_monadize lex sentence2 (fun x -> x);;
+# tree_monadize sentence2 lex (fun x -> x);;
 - : string tree =
 Node
  (Leaf "forall x",
@@ -448,7 +448,7 @@ replace the usual tree_monadizer with tree_monadizer_rev, we get
 inverse scope:
 
 <pre>
-# tree_monadize_rev lex sentence2 (fun x -> x);;
+# tree_monadize_rev sentence2 lex (fun x -> x);;
 - : string tree =
 Node
  (Leaf "exists y",
@@ -559,14 +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. We discuss that further here: [[Monad Transformers]].
+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`:
 
+          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]].