--- /dev/null
+Using continuations to solve the same-fringe problem
+----------------------------------------------------
+
+The problem
+-----------
+
+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.
+
+We've seen two solutions to the same fringe problem so far.
+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]], and
+[[assignment8]]). In that solution, we pulled the zipper on the first
+tree until we found the next leaf, then stored the zipper structure in
+a mutable variable while we turned our attention to the other tree.
+This solution is efficient: the zipper doesn't visit any leaves beyond
+the first mismatch.
+
+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.
+
+The first step is to review your answer to [[assignment8]], and make
+sure you understand what is going on.
+
+
+Two strategies for solving the problem
+--------------------------------------
+
+
+1. 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.
+
+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.
+ 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 (`ta`, `tb`, and `tc`).
+
+2. Make sure your function works on trees that contain only a single
+leaf, as well as when the two trees have different numbers of leaves.
+
+3. Figure out a way to prove that your solution satisfies the main
+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.
+
+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 worked from
+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
+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);;
+
+There is a special stream called `End` that represents a stream that
+contains no (more) elements, analogous to the empty list `[]`.
+Streams that are not empty contain a first object, paired with a
+thunked stream representing the rest of the series. In order to get
+access to the next element in the stream, we must *force* the thunk by
+applying it to the unit. Watch the behavior of this stream in detail.
+This stream delivers the natural numbers, in order: 1, 2, 3, ...
+
+<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 *)
+
+# let tail = match int_stream with Next (i, rest) -> rest;;
+val tail : unit -> int stream = [fun] (* Tail: a thunk *)
+
+(* Force the thunk to compute the second element *)
+# tail ();;
+- : int stream = Next (2, [fun]) (* Second element: 2 *)
+
+# match tail () with Next (_, rest) -> rest ();;
+- : int stream = Next (3, [fun]) (* Third element: 3 *)
+</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 for as long as
+some other process needs new integers".