+versus @@ -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. 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: +

+# #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'] ++ +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: + +

+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'] ++Note that we don't need to do any reversing. -