From 020566910974049e4cd9cbc9279a781768e1817c Mon Sep 17 00:00:00 2001 From: jim Date: Sun, 8 Feb 2015 18:42:17 -0500 Subject: [PATCH] fix previous overwrite --- exercises/assignment3.mdwn | 50 ++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 44 insertions(+), 6 deletions(-) diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index f593f4d7..e4ccfe20 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -1,17 +1,55 @@ -## 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]`. +## 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 hints]], if you need it. ## Lists -7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. +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`.) + +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. + +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. + + +## 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. Define `leq` for numbers (that is, ≤) in the Lambda Calculus. + +## Combinatorial Logic + +Reduce the following forms, if possible: + +10. `Kxy` +11. `KKxy` +12. `KKKxy` +13. `SKKxy` +14. `SIII` +15. `SII(SII)` + + + +16. Give Combinatorial Logic combinators (that is, expressed in terms of `S`, `K`, and `I`) that behave like our boolean functions. You'll need combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`. + +Using the mapping specified in this week's notes, translate the following lambda terms into combinatory logic: -*Here is a hint* +17. `\x x` +18. `\x y. x` +19. `\x y. y` +20. `\x y. y x` +21. `\x. x x` +22. `\x y z. x (y z)` + +23. 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. -- 2.11.0