From: Chris Barker Date: Tue, 7 Dec 2010 17:42:25 +0000 (-0500) Subject: edit X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=b92c1aa7255f31ec081258f7fc6d5d0918602564 edit --- diff --git a/assignment9.mdwn b/assignment9.mdwn new file mode 100644 index 00000000..2277a925 --- /dev/null +++ b/assignment9.mdwn @@ -0,0 +1,131 @@ +Using continuations to solve the same-fringe problem +---------------------------------------------------- + +The 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. + +
+ 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. + +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. Your assignment is to show how. + +TO-DO LIST for solving the problem +---------------------------------- + +1. Review the simple but inefficient solution (easy). +2. Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder). + +3. Two obvious approaches: + +a. 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. + +b. Review the tree_monadizer application of continuations that maps a +tree to a list of leaves in [[manipulating trees with monads]]. Spend +some time trying to understand exactly what it does. Suggestion: +compute the transformation for a tree with two leaves, performing all +beta reduction by hand using the definitions for bind_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. + +2. Make sure your function works on trees that contain only a single +leaf, and when the two trees have different numbers of leaves. + +3. Figure out a way to prove that your solution satisfies the +requirements 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. + +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 compared the +fringe from right to left? + +Streams +------- + +A stream is like a list in that it contains a series of objects (all +of the same type, here, type `'a`). 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);; + +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: + +
+# 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])      
+
+ +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". + +