-
Refunctionalizing zippers: from lists to continuations
------------------------------------------------------
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
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
+list task after talking about generalized quantifiers below.
+
-The task is well-suited to the list zipper because the list monad has
-an intimate connection with continuations. The following section
-makes this connection. We'll return to the list task after talking
-about generalized quantifiers below.