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.

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

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 continuation_bind, continuation_unit 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. (In OCaml: print_int 1 prints an int, print_string "foo" prints a string, print_newline () prints a line break, and print_endline "foo" prints a string followed by a line break.) 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?


A stream is like a list in that it wraps a series of elements of a single type. It differs from a list in that the tail of the series 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, ...

# 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 *)

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