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=e131311c7d2913bab89028656380da66c8642162;hp=0000000000000000000000000000000000000000;hb=2b7fba878488efb4de5bc4f3d8f895691ebfec34;hpb=ccb65934b58c91f5bf06f6172e6877050d05d214
diff --git a/exercises/_assignment2_answers.mdwn b/exercises/_assignment2_answers.mdwn
new file mode 100644
index 00000000..e131311c
--- /dev/null
+++ b/exercises/_assignment2_answers.mdwn
@@ -0,0 +1,205 @@
+Syntax
+------
+
+Insert all the implicit `( )`s and λs into the following abbreviated expressions.
+
+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`!
+
+ See the [[hint|assignment2 hint]].
+
+
+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 ...