```+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. +