From: Jim Pryor Date: Tue, 7 Dec 2010 22:20:27 +0000 (-0500) Subject: Merge branch 'pryor' X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=2214dd1acc23cde1348206b9ed29200670cc4abf;hp=4528f489f93c2f44f573678dff7359d54d9f9672 Merge branch 'pryor' --- diff --git a/assignment9.mdwn b/assignment9.mdwn new file mode 100644 index 00000000..13cf8fd4 --- /dev/null +++ b/assignment9.mdwn @@ -0,0 +1,134 @@ +Using continuations to solve the same-fringe problem +---------------------------------------------------- + +The problem +----------- + +The problem, recall, is to take two trees and decide whether they have +the same leaves in the same order. + +
+ 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));;
+
+ +So `ta` and `tb` are different trees that have the same fringe, but +`ta` and `tc` are not. + +We've seen two solutions to the same fringe problem so far. +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]], and +[[assignment8]]). In that solution, we pulled the zipper on the first +tree until we found the next leaf, then stored the zipper structure in +a mutable variable while we turned our attention to the other tree. +This solution is efficient: the zipper doesn't visit any leaves beyond +the first mismatch. + +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. Your assignment is to show how. + +The first step is to review your answer to [[assignment8]], and make +sure you understand what is going on. + + +Two strategies for solving the problem +-------------------------------------- + + +1. Review the list-zipper/list-continuation example given in + class in [[from list zippers to continuations]]; then + figure out how to re-functionalize the zippers used in the zipper + solution. + +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 + particular kind of data structure) below. The goal will be to + 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. + +------------------------------------- + +Whichever method you choose, here are some goals to consider. + +1. Make sure that your solution gives the right results on the trees +given above (`ta`, `tb`, and `tc`). + +2. Make sure your function works on trees that contain only a single +leaf, as well as when the two trees have different numbers of leaves. + +3. Figure out a way to prove that your solution satisfies the main +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. + +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? +What would you have to change in your solution so that it worked from +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 +until needed. We will turn the stream on and off by thunking it (see +class notes for [[week6]] on thunks, as well as [[assignment5]]). + + type 'a stream = End | Next of 'a * (unit -> 'a stream);; + +There is a special stream called `End` that represents a stream that +contains no (more) elements, analogous to the empty list `[]`. +Streams that are not empty contain a first object, paired with a +thunked stream representing the rest of the series. In order to get +access to the next element in the stream, we must *force* the thunk by +applying it to the unit. Watch the behavior of this stream in detail. +This stream delivers the natural numbers, in order: 1, 2, 3, ... + +
+# 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 *)
+
+# let tail = match int_stream with Next (i, rest) -> rest;;      
+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 *)
+
+# match tail () with Next (_, rest) -> rest ();;
+- : int stream = Next (3, [fun])                      (* Third element: 3 *)
+
+ +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". diff --git a/index.mdwn b/index.mdwn index 0db0d06d..0bb9d341 100644 --- a/index.mdwn +++ b/index.mdwn @@ -75,7 +75,8 @@ preloaded is available at [[assignment 3 evaluator]]. (6 Dec) Lecture notes for [[Week12]] -> Topics: [[List Monad as Continuation Monad]]; [[Manipulating Trees with Monads]]; ... +> Topics: [[List Monad as Continuation Monad]]; [[Manipulating + Trees with Monads]]; ...; [[Assignment9]]. (13 Dec) Lecture notes for Week13