CSE 341, ML Quiz, Spring 1997

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.

Quiz 1, April 24, 1997

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.

Problem 1 (16 points)


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;

Problem 2 (15 points)

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.

Problem 3 (10 points)

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.

Problem 4 (14 points)


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);

Problem 5 (10 points)


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

Problem 6 (15 points)


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.