release gsv discussion
[lambda.git] / exercises / assignment3.mdwn
index e0ecf97..7121fae 100644 (file)
@@ -1,22 +1,22 @@
-** *Work In Progress* **
-
 ## Lists and List Comprehensions
 
-1. In Kapulet, what does `[ [x, 2*x] | x from [1, 2, 3] ]` evaluate to?
+1.  In Kapulet, what does `[ [x, 2*x] | x from [1, 2, 3] ]` evaluate to?
+
+2.  What does `[ 10*x + y | y from [4], x from [1, 2, 3] ]` evalaute to?
 
-2. What does `[ 10*x + y | y from [4], x from [1, 2, 3] ]` evalaute to?
+3.  Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hint1]], if you need it.
 
-3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hint1]], if you need it.
+4.  Last week you defined `head` in terms of `fold_right`. Your solution should be straightforwardly translatable into one that uses our proposed right-fold encoding of lists in the Lambda Calculus. Now define `empty?` in the Lambda Calculus. (It should require only small modifications to your solution for `head`.)
 
-4. Last week you defined `head` in terms of `fold_right`. Your solution should be straightforwardly translatable into one that uses our proposed right-fold encoding of lists in the Lambda Calculus. Now define `empty?` in the Lambda Calculus. (It should require only small modifications to your solution for `head`.)
+5.  If we encode lists in terms of their *left*-folds, instead, `[a, b, c]` would be encoded as `\f z. f (f (f z a) b) c`. The empty list `[]` would still be encoded as `\f z. z`. What should `cons` be, for this encoding?
 
-5. If we encode lists in terms of their *left*-folds, instead, `[a, b, c]` would be encoded as `\f z. f (f (f z a) b) c`. The empty list `[]` would still be encoded as `\f z. z`. What should `cons` be, for this encoding?
+6.  Continuing to encode lists in terms of their left-folds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
 
-6. Continuing to encode lists in terms of their left-folds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
+7.  Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a solution|assignment3 hint2]], if you need help.
 
-7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a solution|assignment3 hint2]], if you need help.
+8.  Suppose you have two lists of integers, `left` and `right`. You want to determine whether those lists are equal, that is, whether they have all the same members in the same order. How would you implement such a list comparison? You can write it in Scheme or Kapulet using `letrec`, or if you want more of a challenge, in the Lambda Calculus using your preferred encoding for lists. If you write it in Scheme, don't rely on applying the built-in comparison operator `equal?` to the lists themselves. (Nor on the operator `eqv?`, which might not do what you expect.) You can however rely on the comparison operator `=` which accepts only number arguments. If you write it in the Lambda Calculus, you can use your implementation of `leq`, requested below, to write an equality operator for Church-encoded numbers. [[Here is a hint|assignment3 hint3]], if you need it.
 
-8. Suppose you have two lists of integers, `left` and `right`. You want to determine whether those lists are equal, that is, whether they have all the same members in the same order. How would you implement such a list comparison? You can write it in Scheme or Kapulet using `letrec`, or if you want more of a challenge, in the Lambda Calculus using your preferred encoding for lists. If you write it in Scheme, don't rely on applying the built-in comparison operator `equal?` to the lists themselves. (Nor on the operator `eqv?`, which might not do what you expect.) You can however rely on the comparison operator `=` which accepts only number arguments. If you write it in the Lambda Calculus, you can use your implementation of `leq`, requested below, to write an equality operator for Church-encoded numbers. [[Here is a hint|assignment3 hint3]], if you need it.
+    (The function you're trying to define here is like `eqlist?` in Chapter 5 of *The Little Schemer*, though you are only concerned with lists of numbers, whereas the function from *The Little Schemer* also works on lists containing symbolic atoms --- and in the final version from that Chapter, also on lists that contain other, embedded lists.)
 
 
 ## Numbers
@@ -77,6 +77,11 @@ Using the mapping specified in this week's notes, translate the following lambda
 
 25. For each of the above translations, how many `I`s are there? Give a rule for describing what each `I` corresponds to in the original lambda term.
 
+    This generalization depends on you omitting the translation rule:
+
+        6. @a(Xa)       =   X            if a is not in X
+
+
 Evaluation strategies in Combinatory Logic
 ------------------------------------------