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.
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.
+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.
-TO-DO LIST for solving the problem
-----------------------------------
+The first step is to review your answer to [[assignment8]], and make
+sure you understand what is going on.
+
-1. Review the simple but inefficient solution (easy).
-2. Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder).
+Two strategies for solving the problem
+--------------------------------------
-3. Two obvious approaches:
-a. Review the list-zipper/list-continuation example given in
+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.
-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.
+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.
-------------------------------------
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
+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
+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, ...
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 *)
+val tail : unit -> int stream = [fun] (* Tail: a thunk *)
(* Force the thunk to compute the second element *)
# tail ();;
-- : int stream = Next (2, [fun])
+- : int stream = Next (2, [fun]) (* Second element: 2 *)
# match tail () with Next (_, rest) -> rest ();;
-- : int stream = Next (3, <fun>)
+- : int stream = Next (3, [fun]) (* Third element: 3 *)
</pre>
You can think of `int_stream` as a functional object that provides