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);
  1. 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) = ...
  2. 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 = ...
  3. 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) = ...
  4. Following a coup the first shall be last but the second in line shall be first, everyone else shuffles up one place. Define coup,
  5. Define the function nthq which returns the first n items from a queue. fun nthq(q, 0) = ... | nthq(q, n) = ...
  6. Write functions l2q to convert a list to a queue and q2l to convert a q to a list.
  7. 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