+++ /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]]). 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. 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.
-
-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 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 forced 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])
-
-# match tail () with Next (_, rest) -> rest ();;
-- : int stream = Next (3, <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 for as long as
-some other process needs new integers".