monad. But what about other list implementations? Do they give rise
to monads that can be understood in terms of continuations?
-Refunctionalizing zippers
--------------------------
-
Manipulating trees with monads
------------------------------
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
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.
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']
Note that this implementation enforces the evaluate-leftmost rule.
Task 1 completed.
+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.
-