X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment2_answers.mdwn;h=04c103c47aada473c00873f21eba7c69d90db46e;hp=e131311c7d2913bab89028656380da66c8642162;hb=a7f15a6a8100c10bde1cf7b97a02660a3d00b9d9;hpb=ccb65934b58c91f5bf06f6172e6877050d05d214

diff --git a/exercises/assignment2_answers.mdwn b/exercises/assignment2_answers.mdwn
index e131311c..04c103c4 100644
--- a/exercises/assignment2_answers.mdwn
+++ b/exercises/assignment2_answers.mdwn
@@ -1,7 +1,9 @@
 Syntax
 ------
 
-Insert all the implicit `( )`s and <code>&lambda;</code>s into the following abbreviated expressions.
+Insert all the implicit `( )`s and <code>&lambda;</code>s into the following abbreviated expressions. Don't just insert them *freely*; rather, provide the official expression, without any notational shortcuts, that is syntactically identical to the form presented.
+
+*In response to your feedback and questions, we refined the explanation of the conventions governing the use of the `.` shorthand. Thanks!*
 
 1.  `x x (x x x) x`  
      <code><b>(((</b>x x<b>)</b> (<b>(</b>x x<b>)</b> x)<b>)</b> x<b>)</b></code>
@@ -53,11 +55,11 @@ In Racket, these functions can be defined like this:
 
 15. Define a `neg` operator that negates `true` and `false`.
 
-    Expected behavior: 
+    Expected behavior:
 
         (((neg true) 10) 20)
 
-    evaluates to `20`, and 
+    evaluates to `20`, and
 
         (((neg false) 10) 20)
 
@@ -182,7 +184,61 @@ Folds and Lists
 
 25. We mentioned in the Encoding notes that `fold_left (flipped_cons, []) xs` would give us the elements of `xs` but in the reverse order. So that's how we can express `reverse` in terms of `fold_left`. How would you express `reverse` in terms of `fold_right`? As with problem 22, don't use `letrec`!
 
-    See the [[hint|assignment2 hint]].
+    *Here is a boring, inefficient answer*
+
+        let
+          append (ys, zs) = fold_right ((&), zs) ys;  # aka (&&)
+          f (y, prev) = append (prev, [y]);
+          reverse xs = fold_right (f, []) xs
+        in reverse
+
+    or (same basic idea, just written differently):
+
+        let
+          f (y, prev) = fold_right ((&), [y]) prev;
+          reverse xs = fold_right (f, []) xs
+        in reverse
+
+    <a id=cps-reverse></a>
+    *Here is an elegant, efficient answer following the [[hint|assignment2 hint]]*
+
+    Suppose the list we want to reverse is `[10, 20, 30]`. Applying `fold_right` to this will begin by computing `f (30, z)` for some `f` and `z` that we specify. If we made the result of that be something like `30 & blah`, or any larger structure that contained something of that form, it's not clear how we could, using just the resources of `fold_right`, reach down into that structure and replace the `blah` with some other element, as we'd evidently need to, since after the next step we should get `30 & (20 & blah)`. What we'd like instead is something like this:
+
+        30 & < >
+
+    Where `< >` isn't some *value* but rather a *hole*. Then with the next step, we want to plug into that hole `20 & < >`, which contains its own hole. Getting:
+
+        30 & (20 & < >)
+
+    And so on. That is the key to the solution. The questions you need to answer, to turn this into something executable, are:
+
+    1.  What is a hole? How can we implement it?
+
+        A hole is a bound variable. `30 & < >` is `lambda x. 30 & x`.
+
+    2.  What should `f` be, so that the result of the second step, namely `f (20, 30 & < >)`, is `30 & (20 & < >)`?
+
+            let
+              f (y, prev) = lambda x. prev (y & x)
+            in ...
+
+    3.  Given that choice of `f`, what should `z` be, so that the result of the first step, namely `f (30, z)` is `30 & < >`?
+
+        The identity function: `f (30, (lambda y. y))` will reduce to `lambda x. (lambda y. y) (30 & x)`, which will reduce to `lambda x. 30 & x`.
+
+    4.  At the end of the `fold_right`, we're going to end with something like `30 & (20 & (10 & < >))`. But what we want is `[30, 20, 10]`. How can we turn what we've gotten into what we want?
+
+        Supply it with `[]` as an argument.
+
+    5.  So now put it all together, and explain how to express `reverse xs` using `fold_right` and primitive syntax like `lambda`, `&`, and `[]`?
+
+            let
+              f (y, prev) = lambda x. prev (y & x);
+              id match lambda y. y;
+              reverse xs = (fold_right (f, id) xs) []
+            in reverse
+
+    The ideas here are explored further in Chapter 8 of *The Little Schemer*. There they first introduce the idea of passing function as arguments to other functions, and having functions be the return values from functions. Then the `multirember&co` function discussed on pp. 137--140 (and the other `...&co` functions discussed in that chapter) are more complex examples of the kind of strategy used here to define `reverse`. We will be returning to these ideas and considering them more carefully later in the term.
 
 
 Numbers