Eric Lippert of the Visual C# compiler team at Microsoft wrote a

fascinating series of five blog posts about graph coloring. The articles develop a C# program with 20 lines of code devoted to defining the problem (coloring the planar graph of borders between 13 South American countries) followed by another 200 lines of C# code to solve the graph coloring problem. In

the fourth article, this culminates in the solution 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 2, 1, 3 that uses just three colors to solve the problem.

Let's solve the same problem using the F# programming language instead. We begin by defining the problem using a union type to represent the countries and nested lists to represent the adjacencies:

type Country =
| Brazil | FrenchGuiana | Suriname | Guyana | Venezuala | Colombia
| Ecuador | Peru | Chile | Bolivia | Paraguay | Uruguay | Argentina
let countries =
[|Brazil; FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;
Ecuador; Peru; Chile; Bolivia; Paraguay; Uruguay; Argentina|]
let edges =
[
Brazil, [ FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;

Peru; Bolivia; Paraguay; Uruguay; Argentina ]
FrenchGuiana, [ Brazil; Suriname ]
Suriname, [ Brazil; FrenchGuiana; Guyana ]
Guyana, [ Brazil; Suriname; Venezuala ]
Venezuala, [ Brazil; Guyana; Colombia ]
Colombia, [ Brazil; Venezuala; Peru; Ecuador ]
Ecuador, [ Colombia; Peru ]
Peru, [ Brazil; Colombia; Ecuador; Bolivia; Chile ]
Chile, [ Peru; Bolivia; Argentina ]
Bolivia, [ Chile; Peru; Brazil; Paraguay; Argentina ]
Paraguay, [ Bolivia; Brazil; Argentina ]
Argentina, [ Chile; Bolivia; Paraguay; Brazil; Uruguay ]
Uruguay, [ Brazil; Argentina ]

]
These are the vertices and edges of our graph.

The countries of South America are, of course, a planar graph so we know they can be assigned colors with no two adjacent countries having the same color using a total of no more than four different colors. Let us define the set of all four possible colors as follows:

let allColors = set[0..3]

The graph coloring problem may then be solved by adding our vertices and edges to an empty graph, generating a sequence of possible colorings at each step:

let solve (V, E) =
((Set.empty, seq[Map.empty]), V)
||> Seq.fold (fun (vertices, solutions) vertex ->
let neighbors =
[|for src, dsts in E do
if src = vertex then yield! Set.intersect vertices (set dsts) else
for dst in dsts do
if dst = vertex && Set.contains src vertices then
yield src|]
Set.add vertex vertices,
seq { for color in solutions do
for newColor in allColors do
if Seq.forall (fun u -> color.[u] <> newColor) neighbors then
yield Map.add vertex newColor color })

Eric's result may then be obtained by taking the first of the valid colorings and using it to enumerate the colors of each country in turn:

let answer =
let _, colors = solve (countries, edges)
let color = Seq.head colors
[ for country in countries -> color.[country] ]

Remarkably, we have solved the same problem in just 19 lines of F# code! One can only imagine how much simpler Microsoft's Roslyn compiler could have been had it been written in F#...