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.

<pre>
 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));;
</pre>

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:

<pre>
# 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])      
</pre>

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".