This is the quiz that I used last spring. I will probably have to dream up a few new questions, and disguise the other ones, but this should give you the idea of what to expect.

- Open Book, Open Notes
- Time limit: 50 minutes
- Answer the problems on the exam paper.
- If you need extra space use the back of a page
- Problems are not of equal difficulty, if you get stuck on a problem, move on.

Evaluate the following ML expressions (you do not need to give the types). If the expression is erroneous, explain what is wrong. tl (hd [1, 2] :: [3, 4, 5]); #1(nil, [1, 2]) @ ["A", "B"]; map (fn(x) => x + 1) [ "A", "B", "C"]; map (fn(x) => x + 1) (1, 2, 3); map rev [[1, 2], [3, 4]]; length [1, 1.0, "one"]; [1,2,3,4] = 1::2::3::4; nil::nil::nil;

Give ML expressions that do the following: For an integer x, determines the largest even integer that is less than or equal to x. Removes the last element from a list L. For a list L of tuples, determines the list consisting of the first elements of the tuples of L. For a string S, create a string with is the same as S except that all of the a's have been removed. (You may use the function filter). For a list L of lists of integers, create a list of lists of the squares of the integers.

A 2-3 tree is a search tree, where each internal node has two or three children. An internal node with two children, contains a single key, and an internal node with three children has two keys. The data is stored in the leaves of the tree. Write a datatype for 2-3 trees. Assume that the keys are integer, and the data is some arbitrary type 'a.

Rewrite the following functions using patterns fun everyOther L = if L = nil then nil else if tl L = nil then L else hd L :: everyOther (tl (tl L)); fun f(i, j) = if i = 0 then j else if j = 0 then 2*i else f(i-1, j) + f(i, j-1) + f(i-1, j-1);

Give short answers to the following questions: \begin{enumerate} Describe two important differences between the type system of ML and the type system of C++ (or C). Why does the function fun pair x y = (x, y); have type 'a -> 'b -> 'a * 'b Why does the test L = nil require that L is a list of elements that are an equality type What is an advantage of Functional Programming What is a disadvantage of Functional Programming

Write an insertion sort function, which sorts a list of integers. Begin by writing a function insert, which inserts an integer x into a list L of integers so that the resulting list is in increasing order, assuming that the list L was in increasing order.