index 745cf29..7687e65 100644 (file)
@@ -373,9 +373,6 @@ and that this monad can reproduce the behavior of the standard list
to monads that can be understood in terms of continuations?

-Refunctionalizing zippers
--------------------------
-
------------------------------

@@ -770,8 +767,8 @@ that is intended to
represent non-deterministic computations as a tree.

-Lists, zippers, continuations
------------------------------
+Refunctionalizing zippers: from lists to continuations
+------------------------------------------------------

Let's work with lists of chars for a change.  To maximize readability, we'll
indulge in an abbreviatory convention that "abc" abbreviates the
@@ -833,7 +830,7 @@ 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
behavior.

-For now, as usual, we'll agree to always ``evaluate'' the leftmost `'S'`.
+For now, as usual, we'll agree to always evaluate the leftmost `'S'`.

This is a task well-suited to using a zipper.

@@ -841,9 +838,9 @@ This is a task well-suited to using a zipper.
type 'a list_zipper = ('a list) * ('a list);;

let rec t1 (z:char list_zipper) =
-    match z with (sofar, []) -> List.rev(sofar)
-               | (sofar, 'S'::rest) -> t1 ((List.append sofar sofar), rest)
-               | (sofar, fst::rest) -> t1 (fst::sofar, rest);;
+    match z with (sofar, []) -> List.rev(sofar) (* Done! *)
+               | (sofar, 'S'::rest) -> t1 ((List.append sofar sofar), rest)
+               | (sofar, fst::rest) -> t1 (fst::sofar, rest);; (* Move zipper *)

# t1 ([], ['a'; 'b'; 'S'; 'e']);;
- : char list = ['a'; 'b'; 'a'; 'b'; 'e']
@@ -855,9 +852,64 @@ let rec t1 (z:char list_zipper) =
Note that this implementation enforces the evaluate-leftmost rule.

+One way to see exactly what is going on is to watch the zipper in
+action by tracing the execution of `t1`.  By using the `#trace`
+directive in the Ocaml interpreter, the system will print out the
+arguments to `t1` each time it is (recurcively) called:

+<pre>
+# #trace t1;;
+t1 is now traced.
+# t1 ([], ['a'; 'b'; 'S'; 'e']);;
+t1 <-- ([], ['a'; 'b'; 'S'; 'e'])
+t1 <-- (['a'], ['b'; 'S'; 'e'])
+t1 <-- (['b'; 'a'], ['S'; 'e'])
+t1 <-- (['b'; 'a'; 'b'; 'a'], ['e'])
+t1 <-- (['e'; 'b'; 'a'; 'b'; 'a'], [])
+t1 --> ['a'; 'b'; 'a'; 'b'; 'e']
+t1 --> ['a'; 'b'; 'a'; 'b'; 'e']
+t1 --> ['a'; 'b'; 'a'; 'b'; 'e']
+t1 --> ['a'; 'b'; 'a'; 'b'; 'e']
+t1 --> ['a'; 'b'; 'a'; 'b'; 'e']
+- : char list = ['a'; 'b'; 'a'; 'b'; 'e']
+</pre>

+The nice thing about computations involving lists is that it's so easy
+to visualize them as a data structure.  Eventually, we want to get to
+a place where we can talk about more abstract computations.  In order
+to get there, we'll first do the exact same thing we just did with
+concrete zipper using procedures.
+
+Think of a list as a procedural recipe: `['a'; 'b'; 'c']` means (1)
+start with the empty list `[]`; (2) make a new list whose first
+element is 'c' and whose tail is the list construted in the previous
+step; (3) make a new list whose first element is 'b' and whose tail is
+the list constructed in the previous step; and (4) make a new list
+whose first element is 'a' and whose tail is the list constructed in
+the previous step.
+
+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`.
+
+This means that we can now represent the sofar part of our zipper--the
+part we've already unzipped--as a continuation, a function describing
+how to finish building the list:

+<pre>
+let rec t1c (l: char list) (c: (char list) -> (char list)) =
+  match l with [] -> c []
+             | 'S'::rest -> t1c rest (fun x -> c (c x))
+             | a::rest -> t1c rest (fun x -> List.append (c x) [a]);;
+
+# t1c ['a'; 'b'; 'S'] (fun x -> x);;
+- : char list = ['a'; 'b'; 'a'; 'b']
+
+# t1c ['a'; 'S'; 'b'; 'S'] (fun x -> x);;
+- : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b']
+</pre>

+Note that we don't need to do any reversing.

-