CMPT 340

Assignment 1

Simple Haskell Programming and Lambda Calculus

Total: 100 Points

[Note: For each of the problems 2 through 5 (a) you must explicitly include the function type signature.]

Problem 1. (5 + 5 + 5 + 5 Points) What are the types of the following functions?

a) swap (x, y) = (y, x)

b) pair x y = (x, y)

c) double x = x*2

d) twice f x = f (f (x))

Problem 2. (5 + 5 + 5 Points) Computing the exponent of a number (i.e., n^k) can take O(n) time if done by

simply multiplying by n, k number of times. A logarithmic way for computing exponents is by using the idea of

successive squaring. For instance, rather than computing n^8 as: n * n * n * n * n * n * n * n, we can compute

it by repeatedly squaring, beginning with n, computing n^2, n^4 and finally n^8. In general, the algorithm

would do the following:

n^k = (n^(k/2))^2 if k is even

n^k = n * n^(k-1) if k is odd

Implement functions in Haskell to do this in each of the following ways:

a) fastExp1: a conditional expression (i.e., using if-then-else)

b) fastExp2: guarded equations (i.e., using | to separate cases)

c) fastExp3: pattern matching

Problem 3. (5 + 10 Points) The Luhn algorithm is used to check bank card numbers for simple errors such as

mistyping a digit, and proceeds as follows:

– Consider each digit as a separate number

– Moving right-to-left and beginning at the second last digit, double every other number

– Subtract 9 from each number that is now greater than 9

– Add all the resulting numbers together

– If the total is divisible by 10, the card number is valid

a) Define a function luhnDouble that doubles a digit and subtracts 9 if the result is greater than 9. For

example:

luhnDouble 3

6

luhnDouble 6

3

b) Using luhnDouble, define a function luhn which decides if a four-digit bank card number is valid. For

example:

luhn 1 7 8 4

True

luhn 4 7 8 3

False

Problem 4. (8 + 2 + 10 Points)

a) Implement a function averageThree to return the average of three integers.

Next, use averageThree to define another function howManyAboveAverage which returns how many of its

three inputs are larger than their average value.

b) Use your averageThree function from above to write another function averageThreeInOne which receives

the three input values as a triple rather than separately.

c) Implement a function orderTriple which accept a triple of integers as input, and evaluates to a triple with the

three integers appearing in ascending order. Use functions written for (a) and/or (b) as helper functions

scoped inside the main function to do this.

Problem 5. (10 + 10 Points)

a) Implement a function compose3, which takes three functions f(x), g(x) and h(x) (each of type Double –

Double) and evaluates to a function (also of type Double – Double) to compute f(g(h(x))). Do NOT use the

built-in composition function for this.

b) Show how the meaning of compose3 can be formalized in terms of a lambda expression. Use the

backslash character (i.e., ‘\’) to represent lambda.

Submission:

Create a directory with your nsid as its name. Inside this directory:

– For a problem not involving programming, include a file named like problem1.txt, under the top-level folder.

– For each problem with a programming component, create a separate sub-directory with names like

problem2, problem3, etc. Under each of these folders, for each programming problem, include a separate

file with your program, as well as a text file showing a transcript of your testing of the program. For

non-programming components, include text files named after the problem part (such as problem5b.txt).

Once you have everything in your directory, create a zip file for the entire directory. If your nsid is <your_nsid

name the zip file <your_nsid.zip. When opened, it should create a directory called <your_nsid.

You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit

your assignment to avoid system slowdown. You are encouraged to submit completed parts of the

assignment early. Late submissions will not be accepted.

Sale!