X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=2ec15d6a6c9a8ee37ec39304a5f4d1ee75befffc;hp=000772ad7df4d17122fa7beb7c36ffed88572cd0;hb=9fe62083953213cce34fc4458e36666902c5ee4b;hpb=0638e3b38097e20ebf645fe7cb1ecec4f17aef7a

diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 000772ad..2ec15d6a 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?]
@@ -81,7 +81,7 @@ in place of `double`:
 
 	let square i = i * i;;
 	tree_map square t1;;
-	- : int tree =ppp
+	- : 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
@@ -248,6 +248,37 @@ 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 (fun a -> fun s -> (s+1, s+1)) t1 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 (f : 'a -> 'b state) (t : 'a tree) : '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' ->
+	                       state_bind (tree_monadize f l) (fun l' ->
+	                         state_unit (Node (l', r'))));;
+
+        # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 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
 
@@ -327,6 +358,30 @@ generalizing the type of the Continuation monad to
 
 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 simplest is to map each tree to a list of its leaves, then compare
+the lists.  But if the fringes differ in an early position, we've
+wasted our time visiting the rest of the tree. 
+
+The second solution was to use tree zippers and mutable state to
+simulate coroutines.  We would unzip the first tree until we found the
+next leaf, then store the zipper structure in the mutable variable
+while we turned our attention to the other tree.  Because we stop 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.  To make this work in the most convenient
+way, we need to use the fully general type for continuations just mentioned.
+
+tree_monadize (fun a k -> a, k a) t1 (fun t -> 0);;
+
+
 
 The Binary Tree monad
 ---------------------