Instructions: You will do this problem set by modifying and submitting these source files: pqueue.sml, map.sml, curry.sml, and sm.sml. You will also solve a written problem that you will submit as a file written.txt. The source files can be found in ps2.zip.
Note: for functions that are not implemented, you should see something of the form "raise Fail "implement me!"". You should remove this text and replace it with the body of the function.
We will test your code using an automated test script. Your submission must compile. Programs that do not compile will receive an automatic zero. If you are having trouble getting your assignment to compile, please visit consulting hours. If you run out of time, it is better to comment out the parts that do not compile and hand in a file that compiles, rather than handing in a more complete file that does not compile.
Do not change variable names. Do not change function names. Do not remove our delimiter comments. Pay scrupulous attention to types. You have been warned.There are FOUR separate parts to this assignment.
Modify pqueue.sml and implement the Priority Queue operations as described in pqueue.sig.
As you learned in CS211, a priority queue is a fundamental abstract data type that efficiently supports finding the item with the highest priority. pqueue.sml contains a partial implementation of a priority queue. For simplicity, our implementation of a priority queue is simply a sorted list of items with their priorities. (Note that we use integers to indicate priority, and the item with the highest priority has the lowest integer value associated with it). dequeue has already been implemented. Use this as a guideline as to how you can implement the rest of the operations. Your priority queue implementation should have the following operations:
(* enqueue q p e = enqueues element e to queue q with priority p. *) val enqueue : 'a pqueue -> int -> 'a -> 'a pqueue (* dequeue q = tuple containing the lowest priority element in q and q * with this element removed. * raise Empty if the queue is empty. *) val dequeue : 'a pqueue -> ('a * 'a pqueue) (* "exists p q" is true iff the predicate p holds for some element in * the queue q. *) val exists : ('a -> bool) -> 'a pqueue -> bool (* priority p q = the highest priority (lowest int) of * any element in queue q for which the predicate p holds. * raise NotFound if no element satisfies the predicate. *) val priority : ('a -> bool) -> 'a pqueue -> int (* "isempty q" is true iff queue q contains no elements. *) val isempty : 'a pqueue -> bool (* tolist q = a list of the elements in queue q sorted in increasing * order according to their respective priorities. *) val tolist : 'a pqueue -> 'a list
Recall that a Map is a data type that provides a mapping from some set of keys to values associated with them. A simple implementation of a map can be built using a list of keys and values, but in this case we will be using a binary search Tree (BST) to implement the map, as it provides faster lookup times. Recall that the nodes of a BST contain a key-value pair, and a left and right subtree, and that the tree is organized such that if a node y is in the left subtree of node x, then the key(y) < key(x), and if y is in the right subtree of x, key(y) > key(x).
In this problem, you will be implementing a BST Map by modifying map.sml following the specification in map.sig. The datatype for the BST is as follows:
datatype 'a tree = EMPTY | NODE of 'a tree * 'a * 'a tree
and the type of the map is:
type ('a,'b) map = ('a * 'a -> order) * (('a * 'b) tree)
Essentially, the BST stores the (key, item) pair based on the ordering of the key as defined in ('a * 'a -> order). And each node of the tree map consists of a left and a right branch of the tree (either of which could be EMPTY) and a (key,item) pair. Remember, the BST map is a tuple, consisting of the ordering function AND a tree. Your BST map should support the following operations:
(* empty order = an empty map *) val empty : ('a * 'a -> order) -> ('a,'b) map (* insert m (k, v) = insert into map m value v with key k *) val insert : ('a,'b) map -> ('a * 'b) -> ('a,'b) map (* remove m k = remove key-value pair from map m if one such pair exists * with key k *) val remove : ('a,'b) map -> 'a -> ('a,'b) map (* lookup m k = find the value with key k * raise NotFound if no such key *) val lookup : ('a,'b) map -> 'a -> 'b (* getone m = remove some key-value pair from the map, returning it along * with the resulting map * raise Empty if empty map *) val getone : ('a,'b) map -> 'a * 'b * ('a,'b) map (* exists m k = true iff k is a key in the map *) val exists : ('a,'b) map -> 'a -> bool (* tolist m = list of key-value tuples sorted by keys in ascending order *) val tolist : ('a,'b) map -> ('a * 'b) list (* isempty m = true iff map is empty *) val isempty : ('a,'b) map -> bool
Note: remove has already been implemented for you in map.sml. Use this example as a guideline as to how you can implement the rest of the operations.
Consider a set M = {m1,...,mn} of n men and set of W = {w1,...,wn} of n women. Each man m in M ranks all the woman, and each woman w in W ranks all the men (there can be no tie in the rankings).
Our goal is to find a perfect stable matching set S: M x W such that each man is paired up (engaged) with exactly one woman and such that
For example, given four people and their preferences:
val men = [("Alan",["Alice","Beatrice"]),("Bob",["Beatrice","Alice"])] val women = [("Alice",["Alan","Bob"]), ("Beatrice", ["Bob","Alan"])]
where the first entry in the tuple is the name of the person and the second entry is the list of their preference. So, Alan prefers Alice over Beatrice.
In this example, {(Alan,Alice),(Bob,Beatrice)} would form a perfect stable matching set, whereas {(Alan,Beatrice),(Bob,Alice)} will not. This is because in the second case, Alan prefers Alice over Beatrice and Alice prefers Alan over Bob. This violates condition 2 above.
An interesting result is that there exist a perfect stable matching set for every set of preference lists. You will learn more about this when you take CS482.
An algorithm for finding a perfect stable matching set is given below: (CS482 2004sp p.5)
Gale-Shapley Algorithm:Initially all m in M and w in W are free While there is a man m who is free and hasn't proposed to every woman Choose such a man m Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed If w is free then (m,w) become engaged Else w is currently engaged to m' If w prefers m' to m then m remains free Else w prefers m to m' (m,w) become engaged m' becomes free Endif
In this problem, you will be required to implement the function sm in sm.sml which takes in a list of men with their preferences and a list of women and their preferences and return a list of engaged couples. Your solution should closely follow the Gale-Shapley Algorithm given above.
You will need to use the Priority Queue and Map data structures implemented in part1 and 2 to do this problem.
A few of the helper functions have already been implemented for you (provided that you have already implemented part1 & 2)
(*createPrio prefl returns a priority queue corresponding to the preference list prefl*) fun createPrio prefl = #2 (foldl (fn(el,(i,q)) => (i+1,PQueue.enqueue q i el)) (0,PQueue.empty) prefl) (*freeM is a mapping of men to his preference priority queue of women*) val freeM = foldl (fn((man,pref),map) => Map.insert map (man, createPrio pref)) Map.empty men (*allW is a mapping of woman to her engagement status (NONE or SOME man) and her preference priority queue of men*) val allW = foldl (fn((wom,pref),map) => Map.insert map (wom, (NONE, createPrio pref))) Map.empty women
Using the above values (along with your priority queue and map implementations) it is possible to solve the stable matching problem in less than 50 lines of code. If you find yourself writing significantly more code, it is a good idea to sit down and think about the problem. Your code should be very similar to the GS algorithm.
Consider the following declarations:
datatype parent = FATHER | MOTHER datatype princess = INGRID of parent*int | ALEXANDRA of parent*string fun gossip (child:princess) = case child of INGRID(MOTHER,_) => "No, she resembles the father" | INGRID(FATHER,0) => "Yes, she resembles the father" | ALEXANDRA(MOTHER,_) => "No, the mother prefers only one name" | ALEXANDRA(FATHER,"Denmark") => "No, she is only partly Danish" | ALEXANDRA(FATHER,"Norway") => "Yes, the father prefers Ingrid Alexandra" | _ => "Did you get these lies from Das Bild?" fun accumulate (n:int) = let fun third(n,s) = (n, s ^ "last") fun second(n,s) = third(n−1, s ^ "am ") fun first(n,s) = second(n−1, s ^ "I ") in first(n, "So ") end fun fib (n:int) = let datatype F = FUNC of int*F −> int fun fib' (x,f as FUNC f'):int = if x<=1 then 1 else f'(x−1,f) + f'(x−2,f) in fib'(n,FUNC fib') end fun foo (n:int) = let fun odd n = n<>0 andalso even(n−1) and even n = n=0 orelse odd(n−1) fun tostr n = if even(n) then "even" else "odd" fun binrep(n:int) = if n=0 then [] else (tostr (n mod 2), n mod 2)::binrep(n div 2) in binrep n end
Write out every step of evaluating each of the following expressions according to the substitution model of evaluation taught in class.
gossip(INGRID(FATHER,0))
accumulate 100
fib 3
foo 3
(fn x => fn y => y + (x y) ) (fn z => z * z) 6would be this sequence:
(fn x => (fn y => y + (x y) )) (fn z => z * z) 6 --> (fn y => y + ((fn z => z * z) y) 6 --> (fn y => y + (y * y)) 6 --> 6 + (6 * 6) --> 42
To do: Hand in the solutions to these problems in a file written.txt. These must be in ASCII text format, and all lines should be shorter than 78 characters.