From 656923cf6fecaa0fc054f965e315ea08ea2df6f3 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 12 Dec 2010 13:28:20 -0500 Subject: [PATCH] deleted using contins..., moved remaining content into assignment9 comment Signed-off-by: Jim Pryor --- assignment9.mdwn | 63 ++++++++++-- using_continuations_to_solve_same_fringe.mdwn | 133 -------------------------- 2 files changed, 55 insertions(+), 141 deletions(-) delete mode 100644 using_continuations_to_solve_same_fringe.mdwn diff --git a/assignment9.mdwn b/assignment9.mdwn index 13cf8fd4..d27c5be8 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. + 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 + 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]]). @@ -132,3 +130,52 @@ 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/using_continuations_to_solve_same_fringe.mdwn b/using_continuations_to_solve_same_fringe.mdwn deleted file mode 100644 index 1c980a4b..00000000 --- a/using_continuations_to_solve_same_fringe.mdwn +++ /dev/null @@ -1,133 +0,0 @@ -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. - -
- 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. 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: - -
-# 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". - -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, ) - -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: - -
-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. Proving this claim requires adding print -statements (or other tracing technology) within the tree monadizer -function. - -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. - -- 2.11.0