This Quiz is worth 50 points. Each point represents a minute of time. Use the point totals as a guide for budgeting your time. The exam is closed-book, closed-notes, open-mind.
For every question that asks you to define a function, you should also tell us the type profile of your function. Also, for full credit, you should avoid using tuple accessors (#1, #2, etc.), list accessors (hd, tl), or the if expression if you can achieve the same effect through pattern matching!
(1.) [1 pt each (9 points total)] Write the type profiles for the following ML function definitions. If the function definition causes a type error, say why (your answer should be less cryptic than the answer ML would give!).
fun dist(vel, seconds) = vel * (seconds div 3600);
fun foo(x,y) = x::y;
fun bar(x,y) = x;
fun mult3 (x,y,z) = x*y*z;
fun combine(nil, nil) = [] | combine(x::xs, y::ys) = (x,y)::combine(xs, ys);
fun flattenTups(nil) = nil | flattenTups((x,y)::rest) = x::y::flattenTups(rest);
fun baz((x,y), (p,q)) = [x,y,p,q];
fun twice f x = f (f x);
fun ugly f1 f2 L = ((f1 L), (f2 L));
(2.) [3 pt each (9 points total)] Perform pattern matching for each of the following pairs of ML expressions. Show the expression trees that result, and how the corresponding nodes of the trees match (or don't match, if there is a mismatch). For example, for x::y::zs and [1,2] I would answer:
2.1) (x::xs, (a,b)) and ([1], ("e", 3))
2.2) [x]::xs and [[1,2]]
2.3) (x, y::ys) and ([1], ["a"])
(3.) [5 pt] Write a polymorphic function (and its type profile) called tupleify, that takes a list and turns it into a list of 2-tuples. Assume that the argument is even in length. Example:
tupleify([4,3,2,1]) => [(4,3), (2,1)]
(4.) [5 pt] Susan Hacker wants to write an ML function that recursively flattens all lists contained within a list. Can she do this in ML? Why or why not?
(5.) [7 pt] Write a function (and its type profile) called pretty, which takes a string and returns a "pretty" version of that string. By pretty we mean that it is formatted like nicely typewritten text. In particular, sequences of multiple spaces should only be one space and all spaces before periods and commas should be removed. Hint: you should use built-in functions explode (break a string into a list of strings of length 1) and implode (append a list of strings together) to transform the string into usable form before and after processing. Example:
pretty("The dogs , cats , and fish bite . Oh well.") =>
"The dogs, cats, and fish bite. Oh well."
(6.) [7 pt] Write the polymorphic function (and its type profile) called setDifference, which takes two lists as arguments and returns the list of elements which are in the first list but not in the second list. For full credit, make use of the higher order functions filter, reduce, and map as necessary (assume that they have been defined and have the following type profiles).
val map = fn : ('a -> 'b) * 'a list -> 'b list
val reduce = fn : ('a * 'b -> 'b) * 'b * 'a list -> 'b
val filter = fn : ('a -> bool) * 'a list -> 'a list
(7.) [2 pt] Define a polymorphic queue datatype which uses a list to represent the queue.
(8.) [6 pt] Write the following four operations (and their type profiles) on the polymorphic queue datatype you defined above. You don't have to worry about error checking! For partial credit, if you can't write functions that take user-defined datatypes, just assume that queues are lists and write the operations that way.
1. newQueue (return a new, empty queue)
2. enqueue (takes an element and a queue, and returns the new queue that results from adding the element to the rear of the queue)
3. dequeue (takes a queue and returns the queue that results from removing the first element of the queue)
4. peek (takes a queue and returns the first element of the queue)