edits

[lambda.git] / exercises / assignment2_answers.mdwn

diff --git a/exercises/assignment2_answers.mdwn b/exercises/assignment2_answers.mdwn
index ad017f0..04c103c 100644 (file)
--- a/exercises/assignment2_answers.mdwn
+++ b/exercises/assignment2_answers.mdwn
@@ -1,7 +1,9 @@
 Syntax
 ------
 
 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>
 
 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`.
 
 
 15. Define a `neg` operator that negates `true` and `false`.
 

-    Expected behavior: 
+    Expected behavior:

 
         (((neg true) 10) 20)
 
 
         (((neg true) 10) 20)
 

-    evaluates to `20`, and 
+    evaluates to `20`, and

 
         (((neg false) 10) 20)
 
 
         (((neg false) 10) 20)
 


@@ -182,11 +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`!
 
 
 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`!
 

-    This problem does have an elegant and concise solution, but it may be hard for you to figure it out. We think it will a useful exercise for you to try, anyway. We'll give a [[hint|assignment2 hint]]. Don't look at the hint until you've gotten really worked up about the problem. Before that, it probably will just be baffling. If your mind has really gotten its talons into the problem, though, the hint might be just what you need to break it open.
+    *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 `[]`?

 
 

-    There are also other, less cool answers. Perhaps you'll find one of them first.
+            let
+              f (y, prev) = lambda x. prev (y & x);
+              id match lambda y. y;
+              reverse xs = (fold_right (f, id) xs) []
+            in reverse

 
 

-    Even if you don't get any answer, we think the experience of working on the problem, and then understanding the answer when we reveal it, will be satisfying and worthwhile. It also fits our pedagogical purposes for some of the recurring themes of the class.
+    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
 
 
 Numbers