concreteness and understandability of the zipper provides a way of
understanding an equivalent treatment using continuations.
-Let's work with lists of `char`s for a change. To maximize readability, we'll
-indulge in an abbreviatory convention that "abSd" abbreviates the
-list `['a'; 'b'; 'S'; 'd']`.
+Let's work with lists of `char`s for a change. We'll sometimes write
+"abSd" as an abbreviation for
+`['a'; 'b'; 'S'; 'd']`.
We will set out to compute a deceptively simple-seeming **task: given a
string, replace each occurrence of 'S' in that string with a copy of
to get there, we'll first do the exact same thing we just did with
concrete zipper using procedures instead.
-Think of a list as a procedural recipe: `['a'; 'b'; 'S'; 'd']` is the result of
-the computation `'a'::('b'::('S'::('d'::[])))` (or, in our old style,
-`make_list 'a' (make_list 'b' (make_list 'S' (make_list 'd' empty)))`). The
+Think of a list as a procedural recipe: `['a'; 'b'; 'c'; 'd']` is the result of
+the computation `'a'::('b'::('c'::('d'::[])))` (or, in our old style,
+`make_list 'a' (make_list 'b' (make_list 'c' (make_list 'd' empty)))`). The
recipe for constructing the list goes like this:
> (0) Start with the empty list []
> (1) make a new list whose first element is 'd' and whose tail is the list constructed in step (0)
-> (2) make a new list whose first element is 'S' and whose tail is the list constructed in step (1)
+> (2) make a new list whose first element is 'c' and whose tail is the list constructed in step (1)
> -----------------------------------------
> (3) make a new list whose first element is 'b' and whose tail is the list constructed in step (2)
> (4) make a new list whose first element is 'a' and whose tail is the list constructed in step (3)
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)`.
+list) -> 'a'::('b'::tail)`. What is the continuation of the 4th step? That is, after we've built up `'a'::('b'::('c'::('d'::[])))`, what more has to happen to that for it to become the list `['a'; 'b'; 'c'; 'd']`? Nothing! Its continuation is the function that does nothing: `fun tail -> tail`.
-This means that we can now represent the unzipped part of our
-zipper as a continuation: a function
-describing how to finish building a list. We'll write a new
-function, `tc` (for task with continuations), that will take an input
-list (not a zipper!) and a continuation `k` (it's conventional to use `k` for continuation variables) and return a processed list.
-The structure and the behavior will follow that of `tz` above, with
-some small but interesting differences. We've included the orginal
-`tz` to facilitate detailed comparison:
+In what follows, we'll be thinking about the result list that we're building up in this procedural way. We'll treat our input list just as a plain old static list data structure, that we recurse through in the normal way we're accustomed to. We won't need a zipper data structure, because the continuation-based representation of our result list will take over the same role.
+
+So our new function `tc` (for task with continuations) takes an input list (not a zipper) and a also takes a continuation `k` (it's conventional to use `k` for continuation variables). `k` is a function that represents how the result list is going to continue being built up after this invocation of `tc` delivers up a value. When we invoke `tc` for the first time, we expect it to deliver as a value the very de-S'd list we're seeking, so the way for the list to continue being built up is for nothing to happen to it. That is, our initial invocation of `tc` will supply `fun tail -> tail` as the value for `k`. Here is the whole `tc` function. Its structure and behavior follows `tz` from above, which we've repeated here to facilitate detailed comparison:
let rec tz (z : char list_zipper) =
match z with
the first `match` clause will fire, so the the variable `zipped` will
not be instantiated).
-We have not named the functional argument `unzipped`, although that is
+We have not named the continuation argument `unzipped`, although that is
what the parallel would suggest. The reason is that `unzipped` (in
-`tz`) is a
-list, but `k` (in `tc`) is a function. That's the most crucial
+`tz`) is a list, but `k` (in `tc`) is a function. That's the most crucial
difference between the solutions---it's 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
In the `tc` version of the task, we simply compose `k` with itself:
`k o k = fun tail -> k (k tail)`.
-A call `tc ['a'; 'b'; 'S'; 'd']` yields a partially-applied function; it still waits for another argument, a continuation of type `char list -> char list`. We have to give it an "initial continuation" to get started. Here we supply *the identity function* as the initial continuation. Why did we choose that? Well, if
-you have already constructed the initial list `"abSd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"abSd"`? Clearly, the identity function.
+A call `tc ['a'; 'b'; 'S'; 'd']` would yield a partially-applied function; it would still wait for another argument, a continuation of type `char list -> char list`. So we have to give it an "initial continuation" to get started. As mentioned above, we supply *the identity function* as the initial continuation. Why did we choose that? Again, if
+you have already constructed the result list `"ababd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"ababd"`? Clearly, the identity function.
A good way to test your understanding is to figure out what the
continuation function `k` must be at the point in the computation when
`tc` is applied to the argument `"Sd"`. Two choices: is it
-`fun tail -> 'a'::'b'::tail`, or it is `fun tail -> 'b'::'a'::tail`? The way to see if
-you're right is to execute the following command and see what happens:
+`fun tail -> 'a'::'b'::tail`, or it is `fun tail -> 'b'::'a'::tail`? The way to see if you're right is to execute the following command and see what happens:
tc ['S'; 'd'] (fun tail -> 'a'::'b'::tail);;
continuations with embedded `prompt`s (also called `reset`s).
The reason the task is well-suited to the list zipper is in part
-because the list monad has an intimate connection with continuations.
+because the List monad has an intimate connection with continuations.
We'll explore this next.