You have 90 minutes to complete this exam. You may use the Substitution Model quick reference, but no other resources, including notes, books, calculators, computers, etc. Please write all answers in an exam booklet. Be sure to put your name on the front of the book.

1. Evaluate each of the following ML expressions and say what value (if any) is produced by the code. You need not justify each and every step of the evaluation, but if you get the wrong answer, then we are likely to give partial credit if we can follow your reasoning using the Substitution Model.

a.letval(x,y) = (2+4, 8-1)iny*xendb. (((fnx => (fny => y*x)) (2*3)) (5+2))c.letvalf = (fnx => (fny => (fnz => x*z+y)))valg = f(2)in(g(3))(5)endd.datatype'a option = NONE | SOMEof'aletfunf(x:string option, y:string option):string =case(y, x)of(NONE, NONE) => "foo" | (SOME x, NONE) => x | (_, SOME y) => yinf(NONE, "zardoz")ende.letvalf =letvalx = (fnx => (fny => x))valy = (fnx => (fny => (fnz => ((x z) (y z)))))in(y x) xendinfendf.letfunf (g: 'a -> 'b -> 'b) (x: 'a) (y: 'b list): 'a =caseyofnil => y | h::t => f g (g h x) tvalr = f (fnx => (fny => (x+1)::y)) nilinr (1::2::3::nil)endg.let funf(x:int):int =let fung(y:int):int = if (y > 0) then f(y-1) else ying(x+1)end in f(~1)end

2. Complete each of the following **let**-expressions by replacing
"* ???*" with a

a.letfunzardoz(x: int list):intcasexofnil => 0 | x::nil => 41 | x::y::nil => x | _ => 3inzardoz()???endb.letfunzardoz(x: int list, y: int list, z:int list):intcase(x, y, z)of(x1::nil, _, c) => 0 | (a, 3::b::c, d) => 1 | (nil, nil, nil) => 2 | (a, b, 2::d::e) => 3 | (a::_, b::_, _) => a+binzardoz()???endc.typet = {foo:(int*real), bar:(real*int)}let funzardoz(x:t) =let valp = #bar xvalq = #foo xin(#2 p) - (#1 q)endinzardoz()???endd. let valx = (2,5)valy = (3,7)valf = (fn(x:int*int,y:int*int) => (#2 x)*(#2 y)valg = (fn(x:int,y:int) => (y,x))valh = (fn(x:int,y:int) => x)funzardoz(f:int*int->int*int, g:int*int->int):int = g(h(f(y)), g(f(x),f(y)))inzardoz()???end

3. Recall the definition of foldl:

fun foldl (f: ('a*'b) -> 'b) (base:'b) (x:'a list):'b = case x of nil => base | hd::tl => foldl f (f (hd,base)) tl

For each of the following tasks, show how foldl can be used to do that task in one line of code.

a. Sum the elements of a list of integers x.

b. Count the number of elements in a list x.

c. Find the minimum element (if any) of a list of integers x. (Hint, you might have to use something besides "int" for the return type.)

d. Filter out all of the numbers less than zero in a list of integers x.

4. A *priority queue* is an extremely useful data structure.
It is similar to a normal queue in that items are conceptually inserted into the
rear of the queue and removed from the front of the queue in a First-In
First-Out (FIFO) order. However, items are also assigned a *priority*
and higher-priority items are always removed before lower-priority items.
For example, your operating system uses a priority queue to determine which
process should get the CPU next---higher priority jobs get to run before
lower-priority jobs. As another example, airline checkin counters are priority
queues where frequent flyers get served before infrequent flyers.

The following signature defines an ML interface polymorphic priority queues:

signaturePRIO_QUEUE =sig(* the type of priority queues containing items of type 'a *)type'a prio_queue(* create a new priority queue, where the argument can be used to * determine the priority of items. *)valempty : ('a -> int) -> 'a pqueue(* insert a new item into the rear of the queue *)valinsert : 'a pqueue -> 'a -> 'a pqueue(* get the first element with highest priority from the front of the queue *)valfront : 'a queue -> 'a option(* return the rest of the queue after removing the front *)valrest : 'a queue -> ('a queue) optionend

Write a structure PrioQueue satisfying the signature above that has the intended behavior. Make sure you comment your code well so that we can understand what you intend to do. You need not worry about an efficient implementation --- just convince us that you can program well in ML.