## CPSC 425 Spring 2004 Final Exam (Take home portion)

Each of the two questions below constitutes 10% of the final exam grade. You may use your textbook for this course (Webber), your class notes, and the ML and Prolog interpreters on cs.roanoke.edu, but you may not use any other print or electronic resources and you may not discuss these problems with anyone. Electronic versions should be e-mailed to me before you come to the in-class portion of the exam, and hardcopy is due at that time.
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

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 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
```