X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=inline;f=exercises%2Fassignment3.mdwn;h=590bae75b73ade1f7875f409e68ec3adb5ba4d25;hb=4cc3097bf65831e8881b2aa70138609f71cf91a6;hp=f593f4d7bdc89d9af36ac1a68f1336c0880ed9b8;hpb=9794378606926302d83f08b63cc7021bbe9725c5;p=lambda.git diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index f593f4d7..590bae75 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -1,17 +1,117 @@ -## Comprehensions +** *Work In Progress* ** -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]`. +## Lists and List Comprehensions -*Here is a hint* +1. In Kapulet, what does `[ [x, 2*x] | x from [1, 2, 3] ]` evaluate to? -Define a function `dup (n, x)` that creates a list of *n* copies of `x`. Then use list comprehensions to transform `[3, 1, 0, 2]` into `[[3, 3, 3], [1], [], [2, 2]]`. Then use `join` to "flatten" the result. +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. +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`.) -## Lists +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? -7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. +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. -*Here is a hint* +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. + + (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 + +9. Recall our proposed encoding for the numbers, called "Church's encoding". As we explained last week, it's similar to our proposed encoding of lists in terms of their folds. Give a Lambda Calculus definition of `zero?` for numbers so encoded. (It should require only small modifications to your solution for `empty?`, above.) + +10. In last week's homework, you gave a Lambda Calculus definition of `succ` for Church-encoded numbers. Can you now define `pred`? Let `pred 0` result in whatever `err` is bound to. This is challenging. For some time theorists weren't sure it could be done. (Here is [some interesting commentary](http://okmij.org/ftp/Computation/lambda-calc.html#predecessor).) However, in this week's notes we examined one strategy for defining `tail` for our chosen encodings of lists, and given the similarities we explained between lists and numbers, perhaps that will give you some guidance in defining `pred` for numbers. + + (Want a further challenge? Define `map2` in the Lambda Calculus, using our right-fold encoding for lists, where `map2 g [a, b, c] [d, e, f]` should evaluate to `[g a d, g b e, g c f]`. Doing this will require drawing on a number of different tools we've developed, including that same strategy for defining `tail`. Purely extra credit.) + + + +11. Define `leq` for numbers (that is, ≤) in the Lambda Calculus. Here is the expected behavior, +where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`. + + leq zero zero ~~> true + leq zero one ~~> true + leq zero two ~~> true + leq one zero ~~> false + leq one one ~~> true + leq one two ~~> true + leq two zero ~~> false + leq two one ~~> false + leq two two ~~> true + ... + + You'll need to make use of the predecessor function, but it's not essential to understanding this problem that you have successfully implemented it yet. You can treat it as a black box. + +## Combinatory Logic + +Reduce the following forms, if possible: + +
Kxy
+KKxy
+KKKxy
+SKKxy
+SIII
+SII(SII)
+\x x
+\x y. x
+\x y. y
+\x y. y x
+\x. x x
+\x y z. x (y z)
+(\x. x (\y. y x)) (v w)
+(\x. x (\x. y x)) (v w)
+(\x. x (\y. y x)) (v x)
+(\x. x (\y. y x)) (v y)
+
+(\x y. x y y) u v
+(\x y. y x) (u v) z w
+(\x y. x) (\u u)
+(\x y z. x z (y z)) (\u v. u)
+