X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment3.mdwn;h=f80fe71c355912c10431fde30ba34c20571ac691;hp=e4ccfe204b84177c6d29467ab47e5e87b4705840;hb=d5cba23aa951e51ec1f54058e9501b145f489fb2;hpb=020566910974049e4cd9cbc9279a781768e1817c diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index e4ccfe20..f80fe71c 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -1,15 +1,12 @@ ** *Work In Progress* ** -## Comprehensions +## Lists and List Comprehensions 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? -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 hints]], if you need it. - - -## Lists +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 the Lambda Calculus, using our proposed encoding for lists. Now define `empty?` (It should require only small modifications to your solution for `head`.) @@ -17,39 +14,102 @@ 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 hint|assignment3 hints]], if you need it. +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. ## Numbers -8. 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. In last week's homework, you defined `succ` for numbers so encoded. Can you now define `pred` in the Lambca Calculus? Let `pred 0` result in whatever `err` is bound to. This is challenging. For some time theorists weren't sure it could be done. 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. +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.) -9. Define `leq` for numbers (that is, ≤) in the Lambda Calculus. -## Combinatorial Logic + +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: -10. `Kxy` -11. `KKxy` -12. `KKKxy` -13. `SKKxy` -14. `SIII` -15. `SII(SII)` +
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)
+