index 0b3f464..f2e6989 100644 (file)
@@ -1,4 +1,3 @@
-
Refunctionalizing zippers: from lists to continuations
------------------------------------------------------

@@ -148,10 +147,11 @@ The recipe for constructing the list goes like this:
What is the type of each of these steps?  Well, it will be a function
from the result of the previous step (a list) to a new list: it will
be a function of type `char list -> char list`.  We'll call each step
-a **continuation** of the recipe.  So in this context, a continuation
-is a function of type `char list -> char list`.  For instance, the
-continuation corresponding to the portion of the recipe below the
-horizontal line is the function `fun (tail:char list) -> a::(b::tail)`.
+(or group of steps) a **continuation** of the recipe.  So in this
+context, a continuation is a function of type `char list -> char
+list`.  For instance, the continuation corresponding to the portion of
+the recipe below the horizontal line is the function `fun (tail:char
+list) -> a::(b::tail)`.

This means that we can now represent the unzipped part of our
zipper--the part we've already unzipped--as a continuation: a function
@@ -194,42 +194,44 @@ what the parallel would suggest.  The reason is that `unzipped` is a
list, but `c` is a function.  That's the most crucial difference, the
point of the excercise, and it should be emphasized.  For instance,
you can see this difference in the fact that in `tz`, we have to glue
-together the two instances of `unzipped` with an explicit `List.append`.
+together the two instances of `unzipped` with an explicit (and
+relatively inefficient) `List.append`.
In the `tc` version of the task, we simply compose `c` with itself:
`c o c = fun x -> c (c x)`.

Why use the identity function as the initial continuation?  Well, if
-you have already constructed the list "abSd", what's the next step in
-the recipe to produce the desired result (which is the same list,
-"abSd")?  Clearly, the identity continuation.
+you have already constructed the initial list `"abSd"`, what's the next
+step in the recipe to produce the desired result, i.e, the very same
+list, `"abSd"`?  Clearly, the identity continuation.

A good way to test your understanding is to figure out what the
continuation function `c` must be at the point in the computation when
`tc` is called with the first argument `"Sd"`.  Two choices: is it
-`fun x -> a::b::x`, or it is `fun x -> b::a::x`?
-The way to see if you're right is to execute the following
-command and see what happens:
+`fun x -> a::b::x`, or it is `fun x -> b::a::x`?  The way to see if
+you're right is to execute the following command and see what happens:

tc ['S'; 'd'] (fun x -> 'a'::'b'::x);;

There are a number of interesting directions we can go with this task.
-The task was chosen because the computation can be viewed as a
+The reason this task was chosen is because it can be viewed as a
simplified picture of a computation using continuations, where `'S'`
plays the role of a control operator with some similarities to what is
-often called `shift`.  In the analogy, the list portrays a string of
-functional applications, where `[f1; f2; f3; x]` represents `f1(f2(f3
-x))`.  The limitation of the analogy is that it is only possible to
-represent computations in which the applications are always
-right-branching, i.e., the computation `((f1 f2) f3) x` cannot be
-directly represented.
+often called `shift`.  In the analogy, the input list portrays a
+sequence of functional applications, where `[f1; f2; f3; x]` represents
+`f1(f2(f3 x))`.  The limitation of the analogy is that it is only
+possible to represent computations in which the applications are
+always right-branching, i.e., the computation `((f1 f2) f3) x` cannot
+be directly represented.

One possibile development is that we could add a special symbol `'#'`,
and then the task would be to copy from the target `'S'` only back to
the closest `'#'`.  This would allow the task to simulate delimited
-continuations (for right-branching computations).
+continuations with embedded prompts.
+
+The reason the task is well-suited to the list zipper is in part
+because the list monad has an intimate connection with continuations.
+The following section explores this connection.  We'll return to the