CPSC 425 Spring 2004
Final Exam (Take home portion)

1. Write a Prolog predicate mergesort(list1,list2) that uses the mergesort algorithm and succeeds when list2 is a sorted version of list1. I recommend an approach similar to the one we used when we did mergesort in ML (Chapter 7). In particular, when dividing the list in half, it's convenient to split it so that one list contains the odd-numbered elements, and the other contains the even-numbered elements. This is what the halve function does in the ML example. Note that predicates <, >, and = behave as you would expect in Prolog.

2. We talked in class about representing objects using functions of type message -> response. Using this model, we discussed the following representation for a node in a linked list of strings:

   datatype message = 
       IsNull
     | GetData
     | GetLink
   
   datatype response =
       Pred of bool
     | Data of string
     | Object of message -> response
   
   fun root msg = Pred false;
   
   fun null IsNull = Pred true
     | null message = root message
   
   fun node data link GetData = Data data
     | node data link GetLink = Object link
     | node data link other = root other
   

   Using this model, write the following functions:
   • makeList: string list -> message -> response. Takes an ML list of strings and returns a linked list of nodes containing those same strings using the model above (that is, returns the node at the front of the list).
   • isLast: (message -> response) -> bool. Takes a node and returns true if it is the last node in the list, that is, if its "next" element is null. You may assume that the node itself is not null.
   • last: (message -> response) -> response. Takes a node and returns the data stored in the last node in the list trailing from this node. You may assume that the node itself is not null.

   Examples:

   - val list1 = makeList ["1"];
   val list1 = fn : message -> response
   - isLast list1;
   val it = true : bool
   - last list1;
   val it = Data "1" : response
   - val list2 = makeList["a", "b", "c"];
   val list2 = fn : message -> response
   - isLast list2;
   val it = false : bool
   - last list2;
   val it = Data "c" : response