From: Chris Barker <barker@kappa.linguistics.fas.nyu.edu>
Date: Mon, 29 Nov 2010 19:37:49 +0000 (-0500)
Subject: edits
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=d30463cb5a4ac07600f4b587249edde28270dfcf

edits
---

diff --git a/zipper-lists-continuations.mdwn b/zipper-lists-continuations.mdwn
index 958d61d0..267015d3 100644
--- a/zipper-lists-continuations.mdwn
+++ b/zipper-lists-continuations.mdwn
@@ -768,3 +768,96 @@ called a
 [SearchTree](http://hackage.haskell.org/packages/archive/tree-monad/0.2.1/doc/html/src/Control-Monad-SearchTree.html#SearchTree)
 that is intended to 
 represent non-deterministic computations as a tree.
+
+
+Lists, zippers, 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
+list `['a'; 'b'; 'c']`.
+
+Task 1: replace each occurrence of 'S' with a copy of the string up to
+that point.  
+
+Expected behavior:
+
+<pre>
+t1 "abSe" ~~> "ababe"
+</pre>   
+
+
+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'):
+
+<pre>
+    t1 "aSbS" 
+         *
+~~> t1 "aabS" 
+           *
+~~> "aabaab"
+<pre>
+
+versus
+
+<pre>
+    t1 "aSbS"
+           *
+~~> t1 "aSbaSb" 
+         *
+~~> t1 "aabaSb"
+            *
+~~> "aabaaabab"
+</pre>   
+
+versus
+
+<pre>
+    t1 "aSbS"
+           *
+~~> t1 "aSbaSb"
+            *
+~~> t1 "aSbaaSbab"
+             *
+~~> t1 "aSbaaaSbaabab"
+              *
+~~> ...
+</pre>
+
+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.  
+
+<pre>
+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);;
+
+# 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']
+</pre>
+
+Note that this implementation enforces the evaluate-leftmost rule.
+Task 1 completed.
+
+
+
+
+
+
+