concreteness and understandability of the zipper provides a way of
understanding and equivalent treatment using continuations.
-Let's work with lists of chars for a change. To maximize readability, we'll
+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']`.
Expected behavior:
-<pre>
-t "abSd" ~~> "ababd"
-</pre>
+ t "abSd" ~~> "ababd"
In linguistic terms, this is a kind of anaphora
Note that it matters which 'S' you target first (the position of the *
indicates the targeted 'S'):
-<pre>
- t "aSbS"
- *
-~~> t "aabS"
- *
-~~> "aabaab"
-</pre>
+ t "aSbS"
+ *
+ ~~> t "aabS"
+ *
+ ~~> "aabaab"
versus
-<pre>
- t "aSbS"
- *
-~~> t "aSbaSb"
- *
-~~> t "aabaSb"
- *
-~~> "aabaaabab"
-</pre>
+ t "aSbS"
+ *
+ ~~> t "aSbaSb"
+ *
+ ~~> t "aabaSb"
+ *
+ ~~> "aabaaabab"
versus
-<pre>
- t "aSbS"
- *
-~~> t "aSbaSb"
- *
-~~> t "aSbaaSbab"
- *
-~~> t "aSbaaaSbaabab"
- *
-~~> ...
-</pre>
+ t "aSbS"
+ *
+ ~~> t "aSbaSb"
+ *
+ ~~> t "aSbaaSbab"
+ *
+ ~~> t "aSbaaaSbaabab"
+ *
+ ~~> ...
Aparently, this task, as simple as it is, is a form of computation,
and the order in which the `'S'`s get evaluated can lead to divergent
This is a task well-suited to using a zipper. We'll define a function
`tz` (for task with zippers), which accomplishes the task by mapping a
-char list zipper to a char list. We'll call the two parts of the
+`char list zipper` to a `char list`. We'll call the two parts of the
zipper `unzipped` and `zipped`; we start with a fully zipped list, and
-move elements to the zipped part by pulling the zipped down until the
+move elements to the zipped part by pulling the zipper down until the
entire list has been unzipped (and so the zipped half of the zipper is empty).
-<pre>
-type 'a list_zipper = ('a list) * ('a list);;
-
-let rec tz (z:char list_zipper) =
- match z with (unzipped, []) -> List.rev(unzipped) (* Done! *)
- | (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped)
- | (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
-
-# tz ([], ['a'; 'b'; 'S'; 'd']);;
-- : char list = ['a'; 'b'; 'a'; 'b'; 'd']
-
-# tz ([], ['a'; 'S'; 'b'; 'S']);;
-- : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
-</pre>
+ type 'a list_zipper = ('a list) * ('a list);;
+
+ let rec tz (z:char list_zipper) =
+ match z with (unzipped, []) -> List.rev(unzipped) (* Done! *)
+ | (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped)
+ | (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
+
+ # tz ([], ['a'; 'b'; 'S'; 'd']);;
+ - : char list = ['a'; 'b'; 'a'; 'b'; 'd']
+
+ # tz ([], ['a'; 'S'; 'b'; 'S']);;
+ - : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
Note that this implementation enforces the evaluate-leftmost rule.
Task completed.
concrete zipper using procedures.
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, `makelist a (makelist b (makelist S (makelist c empty)))`).
+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 recipe for constructing the list goes like this:
<pre>
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)`.
This means that we can now represent the unzipped part of our
-zipper--the part we've already unzipped--as a continuation: a function
+zipper---the part we've already unzipped---as a continuation: a function
describing how to finish building the list. We'll write a new
function, `tc` (for task with continuations), that will take an input
list (not a zipper!) and a continuation and return a processed list.