+t1 "abSe" ~~> "ababe" ++ + +In linguistic terms, this is a kind of anaphora +resolution, where `'S'` is functioning like an anaphoric element, and +the preceding string portion is the antecedent. + +This deceptively simple task gives rise to some mind-bending complexity. +Note that it matters which 'S' you target first (the position of the * +indicates the targeted 'S'): + +

+ t1 "aSbS" + * +~~> t1 "aabS" + * +~~> "aabaab" ++ +versus + +

+ t1 "aSbS" + * +~~> t1 "aSbaSb" + * +~~> t1 "aabaSb" + * +~~> "aabaaabab" ++ +versus + +

+ t1 "aSbS" + * +~~> t1 "aSbaSb" + * +~~> t1 "aSbaaSbab" + * +~~> t1 "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 +behavior. + +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) (* 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'] + +# t1 ([], ['a'; 'S'; 'b'; 'S']);; +- : char list = ['a'; 'a'; 'b'; 'a'; 'a'; 'b'] ++ +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. +