X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment3_answers.mdwn;h=08375b6986cb512ab7bfb0998019a6ee9b5fa4e2;hp=6aa5d7503467a77a8359fdd7df23ba1c39628f71;hb=e90eacbc70fb086d60ed0523c184f27160919792;hpb=8950982eae04ec4ca70862e23122256b526b591b diff --git a/exercises/assignment3_answers.mdwn b/exercises/assignment3_answers.mdwn index 6aa5d750..08375b69 100644 --- a/exercises/assignment3_answers.mdwn +++ b/exercises/assignment3_answers.mdwn @@ -119,17 +119,18 @@ > Here is another solution, due to Martin Bunder and F. Urbanek: - > let pred = \n. \s z. n (\u v. v (u s)) (K z) I in + > let box = \a. \v. v a in + > let pred = \n. \s z. n (\b. box (b s)) (K z) I in > ... - > That can be hard to wrap your head around. If you trace it through, you'll see that: + > That can be hard to wrap your head around. If you trace this expression through, you'll see that: - > * when `n == 0`, it reduces to `\s z. (\v. z) I`, or `\s z. z` - > * when `n == 1`, it reduces to `\s z. (\v. v z) I`, or `\s z. z` - > * when `n == 2`, it reduces to `\s z. (\v. v (s z)) I`, or `\s z. s z` - > * when `n == 3`, it reduces to `\s z. (\v. v (s (s z))) I`, or `\s z. s (s z)` + > * when `n == 0`, it reduces to `\s z. (K z) I`, or `\s z. z` + > * when `n == 1`, it reduces to `\s z. (box z) I`, or `\s z. z` + > * when `n == 2`, it reduces to `\s z. (box (s z)) I`, or `\s z. s z` + > * when `n == 3`, it reduces to `\s z. (box (s (s z))) I`, or `\s z. s (s z)` - > The technique used here is akin to that used in [[the hint for last week's `reverse`|assignment2_answers#cps-reverse]]. + > `box a` is `\v. v a`; this stands to `pair a b` as one stands to two. Since boxes (like pairs) are really just functions, the technique used in this definition of `pred` is akin to that used in [[the hint for last week's `reverse`|assignment2_answers#cps-reverse]]. (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.) @@ -167,7 +168,7 @@ where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`. > let leq? = \l r. zero? (sub l r) in > ... - > Here is another solution. Jim crafted this particular implementation, but like a great deal of the CS knowledge he's gained over the past eight years, Oleg Kiselyov pointed the way. + > Here is another solution. Jim crafted this particular implementation, but like a great deal of the CS knowledge he's gained over the past eight years, Oleg Kiselyov pointed the way. > let leq? = (\base build consume. \l r. r consume (l build base) fst) > ; where base is @@ -267,6 +268,12 @@ S (S (KS) (S (KK) (S (KS) K))) (KI); this is the B combinator, whi 25. 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. + This generalization depends on you omitting the translation rule: + + 6. @a(Xa) = X if a is not in X + + > With that shortcut rule omitted, then there turn out to be one `I` in the result corresponding to each occurrence of a bound variable in the original term. + Evaluation strategies in Combinatory Logic ------------------------------------------ @@ -306,8 +313,8 @@ Reduce to beta-normal forms:
  1. (\x. x (\y. y x)) (v w) ~~> v w (\y. y (v w))
  2. (\x. x (\x. y x)) (v w) ~~> v w (\x. y x) -
  3. (\x. x (\y. y x)) (v x) ~~> v w (\y. y (v x)) -
  4. (\x. x (\y. y x)) (v y) ~~> v w (\u. u (v y)) +
  5. (\x. x (\y. y x)) (v x) ~~> v x (\y. y (v x)) +
  6. (\x. x (\y. y x)) (v y) ~~> v y (\u. u (v y))
  7. (\x y. x y y) u v ~~> u v v
  8. (\x y. y x) (u v) z w ~~> z (u v) w