Quiz 4

Statistics:

mean     26.000 (260.000/10)
stddev   5.273
median   24.500
midrange 22.000-31.000

1   4.8 / 8
2   1.8 / 8
3   3.8 / 8
4   2.6 / 6
 + 13-point bonus

Question 4-1

Suppose we are using an applied lambda calculus which supports the infix arithmetic operators *, +, and -. Reduce the following lambda expression, showing your intermediate steps. It should reduce to a number.

(λa.λb.a (b + 1) - a b) (λx.x * x * x) 2 Use normal (lazy) evaluation order!

Question 4-2

Consider the following Haskell function.

pow2 0 = 1
pow2 n = 2 * pow2 (n - 1)

Convert it into an equivalent tail-recursive Haskell function.

Question 4-3

Suppose we want to define a way to represent pairs (or 2-tuples) in the lambda calculus. We can do this by defining the following function pair, which takes two arguments and generates a representation of a pair of those two values.

pair = λx.λy.λf.f x y For example, to represent the value (2,3), we would call pair 2 3, which would give us λf.f 2 3.

Give a lambda expression for the function first that takes a pair represented as above and extracts the first item of the pair. Using your definition, I should be able to write first (pair 2 3) and get 2.

Question 4-4

What is the type of the following Haskell function?

member _ [] = False
member query (x:xs) = if x == query then True else member query xs

For full credit, describe the type using Haskell syntax.

Solutions

Solution 4-1

(λa.λb.a (b + 1) - a b) (λx.x * x * x) 2
(λb.(λx.x * x * x) (b + 1) - * (λx.x * x * * x) b) 2
(λx.x * x * x) (2 + 1) - (λx.x * x * x) 2
(2 + 1) * (2 + 1) * (2 + 1) - (λx.x * x * x) 2
3 * 3 * 3 - (λx.x * x * x) 2
9 * 3 - (λx.x * x * x) 2
27 - (λx.x * x * x) 2
27 - 2 * 2 * 2
27 - 4 * 2
27 - 8
19

Solution 4-2

pow2 n =
  let
    it 0 ret = ret
    it i ret = pow2 (i - 1) (ret * 2)
  in it n 1

Solution 4-3

first = λp.p (λx.λy.x)

Solution 4-4

(Eq a) => a -> [a] -> Bool