using_continuations_to_solve_same_fringe.mdwn

   1 Using continuations to solve the same fringe problem
   2 ----------------------------------------------------
   3
   4 We've seen two solutions to the same fringe problem so far.
   5 The problem, recall, is to take two trees and decide whether they have
   6 the same leaves in the same order.
   7
   8 <pre>
   9  ta            tb          tc
  10  .             .           .
  11 _|__          _|__        _|__
  12 |  |          |  |        |  |
  13 1  .          .  3        1  .
  14   _|__       _|__           _|__
  15   |  |       |  |           |  |
  16   2  3       1  2           3  2
  17
  18 let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
  19 let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
  20 let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
  21 </pre>
  22
  23 So `ta` and `tb` are different trees that have the same fringe, but
  24 `ta` and `tc` are not.
  25
  26 The simplest solution is to map each tree to a list of its leaves,
  27 then compare the lists.  But because we will have computed the entire
  28 fringe before starting the comparison, if the fringes differ in an
  29 early position, we've wasted our time examining the rest of the trees.
  30
  31 The second solution was to use tree zippers and mutable state to
  32 simulate coroutines (see [[coroutines and aborts]]).  In that
  33 solution, we pulled the zipper on the first tree until we found the
  34 next leaf, then stored the zipper structure in the mutable variable
  35 while we turned our attention to the other tree.  Because we stopped
  36 as soon as we find the first mismatched leaf, this solution does not
  37 have the flaw just mentioned of the solution that maps both trees to a
  38 list of leaves before beginning comparison.
  39
  40 Since zippers are just continuations reified, we expect that the
  41 solution in terms of zippers can be reworked using continuations, and
  42 this is indeed the case.  Before we can arrive at a solution, however,
  43 we must define a data structure called a stream:
  44
  45     type 'a stream = End | Next of 'a * (unit -> 'a stream);;
  46
  47 A stream is like a list in that it contains a series of objects (all
  48 of the same type, here, type `'a`).  The first object in the stream
  49 corresponds to the head of a list, which we pair with a stream
  50 representing the rest of a the list.  There is a special stream called
  51 `End` that represents a stream that contains no (more) elements,
  52 analogous to the empty list `[]`.
  53
  54 Actually, we pair each element not with a stream, but with a thunked
  55 stream, that is, a function from the unit type to streams.  The idea
  56 is that the next element in the stream is not computed until we forced
  57 the thunk by applying it to the unit:
  58
  59 <pre>
  60 # let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
  61 val make_int_stream : int -> int stream = [fun]
  62 # let int_stream = make_int_stream 1;;
  63 val int_stream : int stream = Next (1, [fun])         (* First element: 1 *)
  64 # match int_stream with Next (i, rest) -> rest;;
  65 - : unit -> int stream = [fun]                        (* Rest: a thunk *)
  66
  67 (* Force the thunk to compute the second element *)
  68 # (match int_stream with Next (i, rest) -> rest) ();;
  69 - : int stream = Next (2, [fun])
  70 </pre>
  71
  72 You can think of `int_stream` as a functional object that provides
  73 access to an infinite sequence of integers, one at a time.  It's as if
  74 we had written `[1;2;...]` where `...` meant "continue indefinitely".
  75
  76 So, with streams in hand, we need only rewrite our continuation tree
  77 monadizer so that instead of mapping trees to lists, it maps them to
  78 streams.  Instead of
  79
  80         # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);;
  81         - : int list = [2; 3; 5; 7; 11]
  82
  83 as above, we have
  84
  85         # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);;
  86         - : int stream = Next (2, <fun>)
  87
  88 We can see the first element in the stream, the first leaf (namely,
  89 2), but in order to see the next, we'll have to force a thunk.
  90
  91 Then to complete the same-fringe function, we simply convert both
  92 trees into leaf-streams, then compare the streams element by element.
  93 The code is enitrely routine, but for the sake of completeness, here it is:
  94
  95 <pre>
  96 let rec compare_streams stream1 stream2 =
  97     match stream1, stream2 with
  98     | End, End -> true (* Done!  Fringes match. *)
  99     | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
 100     | _ -> false;;
 101
 102 let same_fringe t1 t2 =
 103   let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in
 104   let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in
 105   compare_streams stream1 stream2;;
 106 </pre>
 107
 108 Notice the forcing of the thunks in the recursive call to
 109 `compare_streams`.  So indeed:
 110
 111 <pre>
 112 # same_fringe ta tb;;
 113 - : bool = true
 114 # same_fringe ta tc;;
 115 - : bool = false
 116 </pre>
 117
 118 Now, you might think that this implementation is a bit silly, since in
 119 order to convert the trees to leaf streams, our tree_monadizer
 120 function has to visit every node in the tree, so we'd have to traverse
 121 the entire tree at some point.  But you'd be wrong: part of what gets
 122 suspended in the thunking of the stream is the computation of the rest
 123 of the monadized tree.  Proving this claim requires adding print
 124 statements (or other tracing technology) within the tree monadizer
 125 function.
 126
 127 By the way, what if you have reason to believe that the fringes of
 128 your trees are more likely to differ near the right edge than the left
 129 edge?  If we reverse evaluation order in the tree_monadizer function,
 130 as shown above when we replaced leaves with their ordinal position,
 131 then the resulting streams would produce leaves from the right to the
 132 left.
 133