assignment9.mdwn

   1 Using continuations to solve the same-fringe problem
   2 ----------------------------------------------------
   3
   4 The problem
   5 -----------
   6
   7 We've seen two solutions to the same fringe problem so far.
   8 The problem, recall, is to take two trees and decide whether they have
   9 the same leaves in the same order.
  10
  11 <pre>
  12  ta            tb          tc
  13  .             .           .
  14 _|__          _|__        _|__
  15 |  |          |  |        |  |
  16 1  .          .  3        1  .
  17   _|__       _|__           _|__
  18   |  |       |  |           |  |
  19   2  3       1  2           3  2
  20
  21 let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
  22 let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
  23 let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
  24 </pre>
  25
  26 So `ta` and `tb` are different trees that have the same fringe, but
  27 `ta` and `tc` are not.
  28
  29 The simplest solution is to map each tree to a list of its leaves,
  30 then compare the lists.  But because we will have computed the entire
  31 fringe before starting the comparison, if the fringes differ in an
  32 early position, we've wasted our time examining the rest of the trees.
  33
  34 The second solution was to use tree zippers and mutable state to
  35 simulate coroutines (see [[coroutines and aborts]]).  In that
  36 solution, we pulled the zipper on the first tree until we found the
  37 next leaf, then stored the zipper structure in the mutable variable
  38 while we turned our attention to the other tree.  Because we stopped
  39 as soon as we find the first mismatched leaf, this solution does not
  40 have the flaw just mentioned of the solution that maps both trees to a
  41 list of leaves before beginning comparison.
  42
  43 Since zippers are just continuations reified, we expect that the
  44 solution in terms of zippers can be reworked using continuations, and
  45 this is indeed the case.  Your assignment is to show how.
  46
  47 TO-DO LIST for solving the problem
  48 ----------------------------------
  49
  50 1.  Review the simple but inefficient solution (easy).
  51 2.  Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder).
  52
  53 3.  Two obvious approaches:
  54
  55 a.  Review the list-zipper/list-continuation example given in
  56     class in [[from list zippers to continuations]]; then
  57     figure out how to re-functionalize the zippers used in the zipper
  58     solution.
  59
  60 b.  Review the tree_monadizer application of continuations that maps a
  61 tree to a list of leaves in [[manipulating trees with monads]].  Spend
  62 some time trying to understand exactly what it does.  Suggestion:
  63 compute the transformation for a tree with two leaves, performing all
  64 beta reduction by hand using the definitions for bind_continuation and
  65 so on.  If you take this route, study the description of streams (a
  66 particular kind of data structure) below.  The goal will be to arrange
  67 for the continuation-flavored tree_monadizer to transform a tree into
  68 a stream instead of into a list.  Once you've done that, completing
  69 the same-fringe problem will be easy.
  70
  71 -------------------------------------
  72
  73 Whichever method you choose, here are some goals to consider.
  74
  75 1.  Make sure that your solution gives the right results on the trees
  76 given above.
  77
  78 2.  Make sure your function works on trees that contain only a single
  79 leaf, and when the two trees have different numbers of leaves.
  80
  81 3.  Figure out a way to prove that your solution satisfies the
  82 requirements of the problem, in particular, that when the trees differ
  83 in an early position, your code does not waste time visiting the rest
  84 of the tree.  One way to do this is to add print statements to your
  85 functions so that every time you visit a leaf (say), a message is
  86 printed on the output.
  87
  88 4.  What if you had some reason to believe that the trees you were
  89 going to compare were more likely to differ in the rightmost region?
  90 What would you have to change in your solution so that it compared the
  91 fringe from right to left?
  92
  93 Streams
  94 -------
  95
  96 A stream is like a list in that it contains a series of objects (all
  97 of the same type, here, type `'a`).  It differs from a list in that
  98 the tail of the list is left uncomputed until needed.  We will turn
  99 the stream on and off by thunking it (see class notes for [[week6]]
 100 on thunks, as well as [[assignment5]]).
 101
 102     type 'a stream = End | Next of 'a * (unit -> 'a stream);;
 103
 104 The first object in the stream corresponds to the head of a list,
 105 which we pair with a stream representing the rest of a the list.
 106 There is a special stream called `End` that represents a stream that
 107 contains no (more) elements, analogous to the empty list `[]`.
 108
 109 Actually, we pair each element not with a stream, but with a thunked
 110 stream, that is, a function from the unit type to streams.  The idea
 111 is that the next element in the stream is not computed until we forced
 112 the thunk by applying it to the unit:
 113
 114 <pre>
 115 # let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
 116 val make_int_stream : int -> int stream = [fun]
 117 # let int_stream = make_int_stream 1;;
 118 val int_stream : int stream = Next (1, [fun])         (* First element: 1 *)
 119 # match int_stream with Next (i, rest) -> rest;;
 120 - : unit -> int stream = [fun]                        (* Rest: a thunk *)
 121
 122 (* Force the thunk to compute the second element *)
 123 # (match int_stream with Next (i, rest) -> rest) ();;
 124 - : int stream = Next (2, [fun])
 125 </pre>
 126
 127 You can think of `int_stream` as a functional object that provides
 128 access to an infinite sequence of integers, one at a time.  It's as if
 129 we had written `[1;2;...]` where `...` meant "continue indefinitely".
 130
 131