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

b.  (((fn x => (fn y => y*x)) (2*3)) (5+2))

c.  let val f = (fn x => (fn y => (fn z => x*z+y)))
        val g = f(2)
    in
        (g(3))(5)
    end

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

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

f.  let fun f (g: 'a -> 'b -> 'b) (x: 'a) (y: 'b list): 'a = 
               case y of
                 nil => y
               | 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

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

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

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
    in
       zardoz(???)
    end

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

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 =
              g(h(f(y)), g(f(x),f(y)))
    in
       zardoz(???)
    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:

   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.