ML Quiz

Name: Solution Set

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

int * int -> int

fun foo(x,y) = x::y;

'a * 'a list -> 'a list

fun bar(x,y) = x;

'a * 'b -> 'a

fun mult3 (x,y,z) = x*y*z;

Error: * is overloaded; ML can't determine which version to use

fun combine(nil, nil) = []
  | combine(x::xs, y::ys) = (x,y)::combine(xs, ys);

'a list * 'b list -> ('a * 'b) list

fun flattenTups(nil) = nil
  | flattenTups((x,y)::rest) = x::y::flattenTups(rest);

('a * 'a) list -> 'a list

fun baz((x,y), (p,q)) = [x,y,p,q];

('a * 'a) * ('a * 'a) -> 'a list

fun twice f x = f (f x);

('a -> 'a) -> 'a -> 'a

fun ugly f1 f2 L = ((f1 L), (f2 L));

('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c

(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)]

fun tupleify(nil) = nil
  | tupleify(x::y::ys) = (x,y)::tupleify(ys);

'a list -> ('a * 'a) list

(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?

She cannot. Since ML is statically typed, it doesn't have predicates to determine whether a variable is an element or a list (as there were in Lisp). This makes the base case very tough to write. She can't write the base case using pattern matching, because if some of her patterns are in the form of lists (e.g. nil or x::xs), ML will conclude that the function takes a 'a list as its argument, and she won't be able to pass an element in to the function.

(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."

fun pretty(s) = 
  let
    fun pretty_help(nil)          = nil
      | pretty_help(" "::" "::xs) = pretty_help(" "::xs)
      | pretty_help(" "::","::xs) = ","::pretty_help(xs)
      | pretty_help(" "::"."::xs) = "."::pretty_help(xs)
      | pretty_help(x::xs)        = x::pretty_help(xs)
  in
    implode(pretty_help(explode(s)))
  end;

string -> string

(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

fun SetDifference(L1,nil)   = y;
  | SetDifference(L1,y::ys) = SetDifference(filter((fn(a) => a=y),L1),ys);

''a list * ''a list -> ''a list

or using currying:

fun member List e = reduce(fn(x,y) => x=e orelse y, false, List);

''a list -> ''a -> boolean

fun SetDifference(L1,L2) = filter((member L2), L1);

''a list * ''a list -> ''a list

datatype 'a Queue = Queue of 'a list

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)

fun newQueue = Queue(nil);

unit -> 'a Queue

fun enQueue(e,Queue(q)) = Queue(q @ [e]);

'a * 'a Queue -> 'a Queue

fun deQueue(Queue(x::xs)) = Queue(xs);

'a Queue -> 'a Queue

fun peek(Queue(x::xs)) = x;

'a Queue -> 'a