# GIML: Tutorial Seven

Enter the queue definition as shown before:
infixr 5 ++;
datatype 'a queue = P | ++ of 'a * 'a queue;
fun front(x++P) = x
| front(x++q) = front q;
fun remove(x++P) = P
| remove(x++q) = x++(remove q);
- Define the function
**unfair** which takes two queues and returns a single queue with the first queue behind the second queue. An example call follows:
unfair("boris"++"tanya"++P,"ivan"++"olga"++P)
= "boris"++"tanya"++"ivan"++"olga"++P
The definition is partially given
fun unfair(P,r) = ...
| unfair(x++q,r) = ...
- At Armageddon the first shall be last and the last shall be first. Define the
**doomsday** function which reverses the order of a queue.
fun doomsday P =...
| doomsday q = ...
- The function
**rude** is used by ill mannered people to push to the front of a queue.
Define the function **rude** based on the following:
fun rude(pushy, P) = ...
| rude(pushy, x++q) = ...
- Following a coup the first shall be last but the second in line shall be first, everyone else shuffles up one place. Define
**coup**,
- Define the function
**nthq** which returns the first n items from a queue.
fun nthq(q, 0) = ...
| nthq(q, n) = ...
- Write functions
**l2q** to convert a list to a queue and **q2l** to convert a q to a list.
- At road works, where two lanes of traffic converge, the two queues are combined fairly. That is cars from each lane alternate.
fair("Rolls"++"Jag"++"BMW"++P,"Lada"++"Robin"++"Mini"++P)
= "Rolls"++"Lada"++"Jag"++"Robin"++"BMW"++"Mini"++P
Define the function
**fair** - you will need to use pattern matching to deal with the cases where one of the queues is empty and the functions front, remove and unfair to deal with the general case.
fun fair(q, P) = ...
| fair(P, q) = ...
| fair(q,q') = ...

Answers