X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2F_assignment2_answers.mdwn;fp=exercises%2F_assignment2_answers.mdwn;h=0000000000000000000000000000000000000000;hp=3eaaa1566c4791f3116b7c2fcb5bb32e8b6d74a6;hb=7e3abd34b5cf0f3d986e986bad3d4eadae298939;hpb=0da178367cda4feaf08df9a101b7d36eedee9f58 diff --git a/exercises/_assignment2_answers.mdwn b/exercises/_assignment2_answers.mdwn deleted file mode 100644 index 3eaaa156..00000000 --- a/exercises/_assignment2_answers.mdwn +++ /dev/null @@ -1,257 +0,0 @@ -Syntax ------- - -Insert all the implicit `( )`s and λ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` - (((x x) ((x x) x)) x) -2. `v w (\x y. v x)` - ((v w) (\x (\y (v x)))) -3. `(\x y. x) u v` - (((\x (\y x)) u) v) -4. `w (\x y z. x z (y z)) u v` - (((w (\x (\y (\z ((x z) (y z)))))) u) v) - -Mark all occurrences of `(x y)` in the following terms: - -5. (\x y. x y) x y -6. (\x y. x y) (x y) -7. \x y. x y (x y) - -Reduction ---------- - -Find "normal forms" for the following---that is, reduce them until no more reductions are possible. As mentioned in the notes, we'll write λx as `\x`. If we ever say "reduce" without qualifications, we mean just "beta-reduce" (as opposed to "(beta + eta)-reduce"). - -8. `(\x \y. y x) z` ~~> `\y. y z` -9. `(\x (x x)) z` ~~> `z z` -10. `(\x (\x x)) z` ~~> `\x x` -11. `(\x (\z x)) z` ~~> `\y z`, be sure to change `\z` to a different variable so as not to "capture" `z` -12. `(\x (x (\y y))) (\z (z z))` ~~> `\y y` -13. `(\x (x x)) (\x (x x))` umm..., reductions will forever be possible, they just don't "do" much -14. `(\x (x x x)) (\x (x x x))` that's just mean - - - -Booleans --------- - -For these questions, and the ones on triples below, we're setting them up so as to encourage you to experiment with Racket and to formulate your answer in Scheme/Racket syntax. But you can answer in Lambda Calculus syntax if you prefer. - -Recall our definitions of true and false. - -> **true** is defined to be `\t f. t` -> **false** is defined to be `\t f. f` - -In Racket, these functions can be defined like this: - - (define true (lambda (t) (lambda (f) t))) - (define false (lambda (t) (lambda (f) f))) - -(Note that they are different from Racket's *primitive* boolean values `#t` and `#f`.) - - -15. Define a `neg` operator that negates `true` and `false`. - - Expected behavior: - - (((neg true) 10) 20) - - evaluates to `20`, and - - (((neg false) 10) 20) - - evaluates to `10`. - - (define neg (lambda (p) ((p false) true))) - -16. Define an `or` operator. - - (define or (lambda (p) (lambda (q) ((p p) q)))) - - or: - - (define or (lambda (p) (lambda (q) ((p true) q)))) - - -17. Define an `xor` operator. If you haven't seen this term before, here's a truth table: - - true xor true == false - true xor false == true - false xor true == true - false xor false == false - - - - (define xor (lambda (p) (lambda (q) ((p (neg q)) q)))) - - -Triples -------- - -Recall our definitions of ordered triples. - -> the triple **(**a**, **b**, **c**)** is defined to be `\f. f a b c` - -To extract the first element of a triple `t`, you write: - - t (\fst snd trd. fst) - -Here are some definitions in Racket: - - (define make-triple (lambda (fst) (lambda (snd) (lambda (trd) (lambda (f) (((f fst) snd) trd)))))) - (define fst_of_three (lambda (fst) (lambda (snd) (lambda (trd) fst)))) - (define snd_of_three (lambda (fst) (lambda (snd) (lambda (trd) snd)))) - -Now we can write: - - (define t (((make-triple 10) 20) 30)) - (t fst_of_three) ; will evaluate to 10 - (t snd_of_three) ; will evaluate to 20 - -If you're puzzled by having the triple to the left and the function that -operates on it come second, think about why it's being done this way: the triple -is a package that takes a function for operating on its elements *as an -argument*, and returns *the result of* operating on its elements with that -function. In other words, the triple is a higher-order function. - - -18. Define the `swap12` function that permutes the elements of a triple. Expected behavior: - - (define t (((make-triple 10) 20) 30)) - ((t swap12) fst_of_three) ; evaluates to 20 - ((t swap12) snd_of_three) ; evaluates to 10 - - Write out the definition of `swap12` in Racket. - - (define swap12 (lambda (x) (lambda (y) (lambda (z) - (lambda (f) (((f y) x) z)))))) - - -19. Define a `dup3` function that duplicates its argument to form a triple -whose elements are the same. Expected behavior: - - ((dup3 10) fst_of_three) ; evaluates to 10 - ((dup3 10) snd_of_three) ; evaluates to 10 - - - - (define dup3 (lambda (x) - (lambda (f) (((f x) x) x)))) - -20. Define a `dup27` function that makes -twenty-seven copies of its argument (and stores them in a data structure of -your choice). - - OK, then we will store them in a triply-nested triple: - - (define dup27 (lambda (x) (dup3 (dup3 (dup3 x))))) - -Folds and Lists ---------------- - -21. Using Kapulet syntax, define `fold_left`. - - # fold_left (f, z) [a, b, c] == f (f (f z a) b) c - letrec - fold_left (f, z) xs = case xs of - [] then z; - x' & xs' then fold_left (f, f (z, x')) xs' - end - in fold_left - - -22. Using Kapulet syntax, define `filter` (problem 7 in last week's homework) in terms of `fold_right` and other primitive syntax like `lambda`, `&`, and `[]`. Don't use `letrec`! All the `letrec`-ing that happens should come from the one inside the definition of `fold_right`. - - let - filter (p, xs) = fold_right ((lambda (y, ys). if p y then y & ys else ys), []) xs - in filter - -23. Using Kapulet syntax, define `&&` in terms of `fold_right`. (To avoid trickiness about the infix syntax, just call it `append`.) As with problem 22 (the previous problem), don't use `letrec`! - - let - xs && ys = fold_right ((&), ys) xs - # or append (xs, ys) = ... - in (&&) - -24. Using Kapulet syntax, define `head` in terms of `fold_right`. When applied to a non-empty list, it should give us the first element of that list. When applied to an empty list, let's say it should give us `'err`. As with problem 22, don't use `letrec`! - - let - head xs = fold_right ((lambda (y, _). y), 'err) xs - in head - -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`! - - *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 - - *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 `[]`? - - let - f (y, prev) = lambda x. prev (y & x); - id match lambda y. y; - reverse xs = (fold_right (f, id) xs) [] - in reverse - -Numbers -------- - -26. Given that we've agreed to Church's encoding of the numbers: - - 0 ≡ \f z. z - 1 ≡ \f z. f z - 2 ≡ \f z. f (f z) - 3 ≡ \f z. f (f (f z)) - ... - - How would you express the `succ` function in the Lambda Calculus? - - let succ = \n. \f z. f (n f z) in ... - - Compare the definition of `cons`, which has an additional element: - - let cons = \d ds. \f z. f d (ds f z) in ...