Homework 2

Problems

1. Using the Y-combinator and Church encodings for pairs to define a lists encoding that includes cons, first, and rest.
2. Using your lists encoding define a map operator that applies a function to every element of a list and returns the result.
3. Using your lists encoding define a search operator that searches a list of natural numbers for a value and returns it.
4. Using your lists encodings create a list [1,2,3] and calculate the result of mapping an increment function over the list
5. Using your lists encodings create a list [1,2,3] and calculate the result of searching for 2.
6. Using your lists encodings create a list [1,2,3] and calculate the result of searching for 4.

Hints

• Assume that you have traditional natural numbers and associated operations. Do not use Chruch Numbers unless you enjoy by-hand beta-reduction
• Assume that you have an if expression similar to the one we’ve used in class examples.
• Assume call-by-name evaluation to take advantage of the lazy Y we developed in class.
• You are free to modify the Church encodings in any way you choose, but pairs is a good place to start.