From: Jim
Date: Tue, 10 Feb 2015 11:12:22 +0000 (-0500)
Subject: Merge branch 'master' into working
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=07ebc9292a8db8b98707232d2d01717293f473e9;hp=-c
Merge branch 'master' into working
* master: (22 commits)
rename exercises/assignment2_answers.mdwn to exercises/_assignment2_answers.mdwn
just link to hint for `reverse`
compare `cons`
create page
link to answers1
formatting, code style
link to answers to week1 homework
create solutions
redo hint links
removed
create page
create page
reorganize, add some (as-yet-unlinked) titles for week 3
add anchors
tweak explanation of why `f` is curried
clarify why Lambda Calculus prefers curried functions, thanks for input Kyle
38e98c659e1819ddd4457935508ee12824b50241
edits to combinatory logic
added old CL text
clarify constraints
...
---
07ebc9292a8db8b98707232d2d01717293f473e9
diff --combined exercises/assignment3.mdwn
index d1cec2a9,271d2bfd..e2fd9627
--- a/exercises/assignment3.mdwn
+++ b/exercises/assignment3.mdwn
@@@ -6,7 -6,7 +6,7 @@@
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.
+ 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.
## Lists
@@@ -17,28 -17,14 +17,28 @@@
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.
## 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. (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.
-9. Define `leq` for numbers (that is, ≤) in the Lambda Calculus.
+9. 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.
## Combinatorial Logic
@@@ -67,21 -53,3 +67,21 @@@ Using the mapping specified in this wee
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.
+
+More Lambda Practice
+--------------------
+
+Reduce to beta-normal forms:
+
+
+- `(\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)`
+

+