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=038cdc3697a4ab501734dac5209ffe2402d0ecd3;hb=5fda6b40cf467cf820cf7ecf022ac796dd0e316b;hpb=8f067600295d47935d4ec86e612c189d0e39b0d7

diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 038cdc36..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 `λ 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,21 +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
+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?
 
-In a moment, we'll return to the same-fringe problem.  Since the
+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 its needed...
+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
@@ -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,157 +345,33 @@ 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.]
 
-	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).
-
-Using continuations to solve the same fringe problem
-----------------------------------------------------
-
-We've seen two solutions to the same fringe problem so far.  
-The problem, recall, is to take two trees and decide whether they have
-the same leaves in the same order.
-
-<pre>
- ta            tb          tc
- .             .           .
-_|__          _|__        _|__
-|  |          |  |        |  |
-1  .          .  3        1  .
-  _|__       _|__           _|__
-  |  |       |  |           |  |
-  2  3       1  2           3  2
-
-let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
-let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
-let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
-</pre>
-
-So `ta` and `tb` are different trees that have the same fringe, but
-`ta` and `tc` are not.
-
-The simplest solution is to map each tree to a list of its leaves,
-then compare the lists.  But because we will have computed the entire
-fringe before starting the comparison, if the fringes differ in an
-early position, we've wasted our time examining the rest of the trees.
-
-The second solution was to use tree zippers and mutable state to
-simulate coroutines (see [[coroutines and aborts]]).  In that
-solution, we pulled the zipper on the first tree until we found the
-next leaf, then stored the zipper structure in the mutable variable
-while we turned our attention to the other tree.  Because we stopped
-as soon as we find the first mismatched leaf, this solution does not
-have the flaw just mentioned of the solution that maps both trees to a
-list of leaves before beginning comparison.
-
-Since zippers are just continuations reified, we expect that the
-solution in terms of zippers can be reworked using continuations, and
-this is indeed the case.  Before we can arrive at a solution, however,
-we must define a data structure called a stream:
-
-    type 'a stream = End | Next of 'a * (unit -> 'a stream);;
-
-A stream is like a list in that it contains a series of objects (all
-of the same type, here, type `'a`).  The first object in the stream
-corresponds to the head of a list, which we pair with a stream
-representing the rest of a the list.  There is a special stream called
-`End` that represents a stream that contains no (more) elements,
-analogous to the empty list `[]`.  
-
-Actually, we pair each element not with a stream, but with a thunked
-stream, that is, a function from the unit type to streams.  The idea
-is that the next element in the stream is not computed until we forced
-the thunk by applying it to the unit:
-
-<pre>
-# let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
-val make_int_stream : int -> int stream = <fun>
-# let int_stream = make_int_stream 1;;
-val int_stream : int stream = Next (1, <fun>)         (* First element: 1 *)
-# match int_stream with Next (i, rest) -> rest;;      
-- : unit -> int stream = <fun>                        (* Rest: a thunk *)
-
-(* Force the thunk to compute the second element *)
-# (match int_stream with Next (i, rest) -> rest) ();;
-- : int stream = Next (2, <fun>)      
-</pre>
-
-You can think of `int_stream` as a functional object that provides
-access to an infinite sequence of integers, one at a time.  It's as if
-we had written `[1;2;...]` where `...` meant "continue indefinitely".
-
-So, with streams in hand, we need only rewrite our continuation tree
-monadizer so that instead of mapping trees to lists, it maps them to 
-streams.  Instead of 
-
-	# tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);;
-	- : int list = [2; 3; 5; 7; 11]
-
-as above, we have 
-
-        # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);;
-        - : int stream = Next (2, <fun>)
-
-We can see the first element in the stream, the first leaf (namely,
-2), but in order to see the next, we'll have to force a thunk.
-
-Then to complete the same-fringe function, we simply convert both
-trees into leaf-streams, then compare the streams element by element.
-The code is enitrely routine, but for the sake of completeness, here it is:
-
-<pre>
-let rec compare_streams stream1 stream2 =
-    match stream1, stream2 with 
-    | End, End -> true (* Done!  Fringes match. *)
-    | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
-    | _ -> false;;
-
-let same_fringe t1 t2 =
-  let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in 
-  let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in 
-  compare_streams stream1 stream2;;
-</pre>
+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").
 
-Notice the forcing of the thunks in the recursive call to
-`compare_streams`.  So indeed:
+We would eventually want to generalize the continuation type to
 
-<pre>
-# same_fringe ta tb;;
-- : bool = true
-# same_fringe ta tc;;
-- : bool = false
-</pre>
-
-Now, this implementation is a bit silly, since in order to convert the
-trees to leaf streams, our tree_monadizer function has to visit every
-node in the tree.  But if we needed to compare each tree to a large
-set of other trees, we could arrange to monadize each tree only once,
-and then run compare_streams on the monadized trees.
+	type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
 
-By the way, what if you have reason to believe that the fringes of
-your trees are more likely to differ near the right edge than the left
-edge?  If we reverse evaluation order in the tree_monadizer function,
-as shown above when we replaced leaves with their ordinal position,
-then the resulting streams would produce leaves from the right to the
-left.
+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
 ------------------------------------------------------------------------
@@ -525,7 +401,7 @@ quantification.
 
 This sentence means (roughly)
 
-    &Forall; x . yesterday(saw x) john
+    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
@@ -547,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",
@@ -560,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",
@@ -572,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",
@@ -669,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:
@@ -683,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]].