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

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;


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

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:
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.