X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment9.mdwn;h=3ec13ae742d2356b094ee9b60f55e7af0799485a;hp=524c9efead1823ce9c95248d66acfe4f2335f88b;hb=336590c5e10edd92eacf93d0ff04dfe93e0d376a;hpb=6634e47c2d920a24c18277147590c8146b2d1284

diff --git a/assignment9.mdwn b/assignment9.mdwn
index 524c9efe..3ec13ae7 100644
--- a/assignment9.mdwn
+++ b/assignment9.mdwn
@@ -56,15 +56,15 @@ Two strategies for solving the problem
     figure out how to re-functionalize the zippers used in the zipper
     solution.
 
-2.  Review how the continuation-flavored tree\_monadizer managed to
+2.  Review how the continuation-flavored `tree_monadizer` managed to
     map a tree to a list of its leaves, in [[manipulating trees with monads]].
     Spend some time trying to understand exactly what it
     does: compute the tree-to-list transformation for a tree with two
     leaves, performing all beta reduction by hand using the
-    definitions for bind\_continuation, unit\_continuation and so on.
-    If you take this route, study the description of streams (a
+    definitions for `continuation_bind`, `continuation_unit` and so on.
+    If you take this route, study the description of **streams** (a
     particular kind of data structure) below.  The goal will be to
-    arrange for the continuation-flavored tree_monadizer to transform
+    arrange for the continuation-flavored `tree_monadizer` to transform
     a tree into a stream instead of into a list.  Once you've done
     that, completing the same-fringe problem will be easy.
 
@@ -83,9 +83,7 @@ requirement of the problem; in particular, that when the trees differ
 in an early position, your code does not waste time visiting the rest
 of the tree.  One way to do this is to add print statements to your
 functions so that every time you visit a leaf (say), a message is
-printed on the output.  If two trees differ in the middle of their
-fringe, you should show that your solution prints debugging
-information for the first half of the fringe, but then stops.
+printed on the output. (In OCaml: `print_int 1` prints an `int`, `print_string "foo"` prints a `string`, `print_newline ()` prints a line break, and `print_endline "foo"` prints a string followed by a line break.) If two trees differ in the middle of their fringe, you should show that your solution prints debugging information for the first half of the fringe, but then stops.
 
 4.  What if you had some reason to believe that the trees you were
 going to compare were more likely to differ in the rightmost region?
@@ -95,8 +93,8 @@ right to left?
 Streams
 -------
 
-A stream is like a list in that it contains a series of objects.  It
-differs from a list in that the tail of the list is left uncomputed
+A stream is like a list in that it wraps a series of elements of a single type.
+It differs from a list in that the tail of the series is left uncomputed
 until needed.  We will turn the stream on and off by thunking it (see
 class notes for [[week6]] on thunks, as well as [[assignment5]]).
 
@@ -118,17 +116,66 @@ val make_int_stream : int -> int stream = [fun]
 val int_stream : int stream = Next (1, [fun])         (* First element: 1 *)
 
 # let tail = match int_stream with Next (i, rest) -> rest;;      
-val tail : unit -> int stream = <fun>                     (* Tail: a thunk *)
+val tail : unit -> int stream = [fun]                 (* Tail: a thunk *)
 
 (* Force the thunk to compute the second element *)
 # tail ();;
-- : int stream = Next (2, [fun])                     (* Second element: 2 *)
+- : int stream = Next (2, [fun])                      (* Second element: 2 *)
 
 # match tail () with Next (_, rest) -> rest ();;
-- : int stream = Next (3, <fun>)                         (* Third element: 3 *)
+- : int stream = Next (3, [fun])                      (* Third element: 3 *)
 </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 for as long as
 some other process needs new integers".
+
+
+<!--
+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 entirely routine, but for the sake of completeness, here it is:
+
+	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;;
+
+Notice the forcing of the thunks in the recursive call to
+`compare_streams`.  So indeed:
+
+	# same_fringe ta tb;;
+	- : bool = true
+	# same_fringe ta tc;;
+	- : bool = false
+
+Now, you might think that 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, so we'd have to traverse
+the entire tree at some point.  But you'd be wrong: part of what gets
+suspended in the thunking of the stream is the computation of the rest
+of the monadized tree.
+
+-->