This will be an open book exam. It will cover chapters 3-7 and 9-10 of Thompson. You should be prepared to do the following kinds of things.
Perform β-reductions on terms of λ-calculus.
Write functions that work on lists and integers using correct Haskell syntax.
Be able to carry out simple evaluations of Haskell expressions by hand.
Know basic Haskell operators and functions, such as :, ++, and length. Be able to use lists, including list comprehensions.
Understand curried and higher order functions, including their types. Understand fundamental higher order functions, including map, foldl and foldr.
Sample problems are the following from Thompson. 3.9, 4.1, 4.5, 5.6, 5.10, 5.11, 7.2, 7.5, 7.7, 7.20, 9.1, 9.2, 9.4, 9.5, 9.11, 9.16, 10.4, 10.5, 10.9.
For λ-calculus, here are some sample problems.
Suppose that fix = λ f.(λ x.f(x x))(λ x.f(x x)). Perform a single β reduction on expression fix fix. What do you get?
Without performing further β-reductions, can you argue that fix fix = fix(fix fix)? How?
Suppose that I = λ x.x, K = λ x.λ y.x and S = λ x.λ y.λ z. x z (y z). It is known that every term of λ-calculus that has no free variables is equivalent to a term that is formed from only S, K and applications. (No λs are needed.) Show that I is the same as SKK by performing β-reductions (and possibly α-conversions) on SKK so that you reach I.