CS312 Prelim I

---

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. let val (x,y) = (2+4, 8-1) in y*x end
 
Answer: 42
 
b. (((fn x => (fn y => y*x)) (2*3)) (5+2))
 
Answer: 42
 
c. let val f = (fn x => (fn y => (fn z => x*z+y)))
 val g = f(2)
 in
 (g(3))(5)
 end
 
Answer: 13
 
d. datatype 'a option = NONE | SOME of 'a
 
 let fun f(x:string option, y:string option):string = 
 case (y, x) of
 (NONE, NONE) => "foo"
 | (SOME x, NONE) => x
 | (_, SOME y) => y
 in
 f(NONE, SOME "zardoz")
 end
 
Answer: "zardoz"
 
e. let val f = 
 let val x = (fn x => (fn y => x))
 val y = (fn x => (fn y => (fn z => ((x z) (y z)))))
 in
  (y x) x
 end
 in
 f
 end
 
Answer: fn z => (((fn x => (fn y => x)) z) ((fn x => (fn y => x)) z)))
 
f. let fun f (g: 'a -> 'b -> 'b) (x: 'b) (y: 'a list): 'b = 
 case y of
 nil => x
 | h::t => f g (g h x) t
 val r = f (fn x => (fn y => (x+1)::y)) nil
 in
 r (1::2::3::nil)
 end
 
Answer: 4::3::2::nil = [4,3,2]
 
g. let fun f(x:int):int = 
 let fun g(y:int):int = if (y > 0) then f(y-1) else y
 in
  g(x+1)
 end
 in
 f(~1)
 end
 
Answer: 0

---

2.  Complete each of the following let-expressions by replacing "???" with a value that causes the whole thing to evaluate to the integer 42.   Again, you can simply write down an answer, but to receive partial credit for the wrong answer, you should justify your choice using the Substitution Model.

a. let fun zardoz(x: int list):int =
 case x of
 nil => 0
 | x::nil => 41
 | x::y::nil => x
  | _ => 3
 in
 zardoz(???)
 end
 
Sample Answer: 42::1::nil = [42,1] (any value other than 1 will work too)
 
b. let fun zardoz(x: int list, y: int list, z:int list):int =
 case (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+b
 | _ => 43
 in
 zardoz(???)
 end
 
Sample Answer: (42::1::nil, 0::nil, nil)
 
c. type t = {foo:(int*real), bar:(real*int)}
 
 let fun zardoz(x:t) = 
 let val p = #bar x
 val q = #foo x
 in
 (#2 p) - (#1 q)
 end
 in
 zardoz(???)
 end
 
Sample Answer: {foo=(0,3.14), bar=(2.17,42)}
 
d. let val x = (2,5)
 val y = (3,7)
 val f = (fn (x:int*int,y:int*int) => (#1 x,(#2 x)*(#2 y)))
 val g = (fn (x:int,y:int) => (y,x))
 val h = (fn (x:int,y:int) => x)
 fun zardoz(f:int*int->int*int, g:(int*int)*(int*int)->int*int):int =
 h(f(g(g(f(x),f(y)),y)))
 in
 zardoz(???)
 end
 
Sample Answer: zardoz(g, f) – hint, look at the type of zardoz

---

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.

Sample Answer: foldl (op +) 0 x

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

Sample Answer: foldl (fn (_,i) => i+1) 0 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.)

Sample Answer:
foldl (fn (i,minopt) =>
(case minopt of NONE => SOME(i) | SOME(j) => SOME(min(i,j))) NONE x

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

Sample Answer:
foldl (fn (i,xs) => if i < 0 then xs else i::xs) [] 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:

 signature PRIO_QUEUE =
 sig
 (* the type of priority queues containing items of type 'a *)
 type 'a pqueue
 
 (* create a new priority queue, where the argument can be used to
 * determine the priority of items. *)
 val empty : ('a -> int) -> 'a pqueue 
 
 (* insert a new item into the rear of the queue *)
 val insert : 'a pqueue -> 'a -> 'a pqueue
 
 (* get the first element with highest priority from the front of the queue *)
 val front : 'a pqueue -> 'a option
 
 (* return the rest of the queue after removing the front *)
 val rest : 'a pqueue -> ('a pqueue) option
 end

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.

Sample Answer:

structure PrioQueue :> PRIO_QUEUE = struct
(* invariant: the list is sorted in decreasing order of priority *)
type 'a pqueue = { priority : 'a -> int, elts: 'a list }

fun empty (p_fn:'a -> int) : 'a pqueue = { priority = p_fn, elts = [] }

fun insert ({priority, elts}:'a pqueue, e:'a):'a pqueue =
let fun ins(elts:'a list):'a list =
case elts of
[] => [e]
| hd::tl => if (priority e) >= (priority hd) then e::elts
else hd::(ins tl)
in
{ priority = p_fn, elts = ins(elts) }
end

fun front ({priority, elts}:'a pqueue): 'a option =
case elts of
[] => NONE
| hd::_ => SOME(hd)

fun rest ({priority, elts}: 'a pqueue): 'a option =
case elts of
[] => NONE
| _::tl => SOME({priority = priority, elts = tl})
end

---