Description
[Question 1:70 points]
In this question you will implement a simple map colouring problem. We will represent a map
showing countries by describing which countries share a border. A country is just a string. A chart
is simply a map (in the normal sense of the word) of some countries. It is represented as a list
of pairs of countries. If (a, b) is in the list it means that the countries a and b share a border.
This relation is symmetric but we will not put both (a, b) and (b, a) in the list. We want to colour
the chart so that two countries that share a border are not given the same colour. We will not
name the colours; we simply view a colour as a set of countries that share the same colour; such
a set is represented as a list of countries. A colouring is a set of colours; hence a set of sets of
countries: this is represented as a list of lists of countries. The algorithm takes a chart, and an
initially empty colouring and then tries to extend the colouring by adding countries from the chart.
It works by naively checking if a country can be added to a given colour by making sure that it is
not a neighbour of any of the countries already with that colour.
Here are the type definitions and names of functions:
# type country = string
# type chart = (country * country) list
# type colour = country list
# type colouring = colour list
val areNeighbours : country -> country -> chart -> bool =
val canBeExtBy : colour -> country -> chart -> bool =
val extColouring : chart -> colouring -> country -> colour list =
val removeDuplicates : ’a list -> ’a list =
val countriesInChart : chart -> country list =
val colourTheCountries : chart -> colouring =
You are required to implement all these functions. This time you are encouraged to use functions
from the list library. I found List.mem, List.for_all, List.filter and List.fold_left to be
1
useful in my solution. Of course, you can program without these for full credit but you will find
that the solutions using these are short and sweet.
[Question 2:30 points]
This exercise shows you how to do low-level pointer manipulation in OCaml if you ever need to do
that. We can define linked lists as follows:
type cell = { data : int; next : rlist}
and rlist = cell option ref
Notice that this is a mutually recursive definition. Each type mentions the other one. The keyword
and is used for mutually recursive definitions.
Implement an OCaml function insert which inserts an element into a sorted linked list and preserves the sorting. You do not have to worry about checking if the input list is sorted. The type
should be
val insert : comp:(int * int -> bool) -> item:int -> list:rlist -> unit
Insert takes in three arguments: A comparison function of type int * int -> bool, an element
of type int and a linked list l of type rlist. Your function will destructively update the list
l. This means that you will have mutable fields that get updated. Please note the types carefully.
Here is the code I used to test the program.
let c1 = {data = 1; next = ref None}
let c2 = {data = 2; next = ref (Some c1)}
let c3 = {data = 3; next = ref (Some c2)}
let c5 = {data = 5; next = ref (Some c3)}
(* This converts an rlist to an ordinary list. *)
let rec displayList (c : rlist) =
match !c with
| None -> []
| Some { data = d; next = l } -> d :: (displayList l)
(* Useful if you are creating some cells by hand and then converting
them to rlists as I did above. *)
let cell2rlist (c:cell):rlist = ref (Some c)
(* Example comparison function. *)
let bigger(x:int, y:int) = (x > y)
You may find the displayList and cell2rlist functions useful.
Here are examples of the code in action:
# let l5 = cell2rlist c5;;
val l5 : rlist = ….
(* Messy display deleted. *)
2
# displayList l5;;
– : int list = [5; 3; 2; 1]
# displayList l5;;
– : int list = [5; 3; 2; 1]
# insert bigger 4 l5;;
– : unit = ()
# displayList l5;;
– : int list = [5; 4; 3; 2; 1]
# insert bigger 9 l5;;
– : unit = ()
# displayList l5;;
– : int list = [9; 5; 4; 3; 2; 1]
# insert bigger 0 l5;;
– : unit = ()
# displayList l5;;
– : int list = [9; 5; 4; 3; 2; 1; 0]
The program is short (5 lines or fewer) and easy to mess up. Please think carefully about whether
you are creating aliases or not. You can easily write programs that look absolutely correct but
which create infinite loops. It might happen that your insert program looks like it is working
correctly but then displayList crashes. You might then waste hours trying to “fix” displayList
and cursing me for writing incorrect code. Most likely, your insert happily terminated but created
a cycle of pointers which then sends displayList into an infinite loop.
3