Hey! need help with the implementation for this program for F#. Thank You!

tells us to use the example to implement the map coloring algorithm in F#

Example: Map Coloring. A map should be colored so that neighbouring countries get different colors "d" "b" "a" The types for country and map are straightforward": type country = string Symbols: C, C1, C2, c'; Examples: "a", "b", ... type map= (country*country) list Symbols: m; Example: val exMap = [("a","b"); ("c","d"); ("d","a")] How many ways could above map be colored? 32 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Abstract models for color and coloring type color = country list Symbols: col; Example: ["c"; "a"] type coloring = color list Symbols: cols; Example: [["c"; "a"); ["b"; "d"]] Be conscious about symbols and examples colMap: map -> coloring Meta symbol: Type Definition Sample value C: country string m: map (country+country) list["a", "b");"C", "d"); ("d","a")] col: color country list ["a";"0"] cols: coloring color list [["a"; "C"];["b";"0"]] Figure: A Data model for map coloring problem 33 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Algorithmic idea "d" "b" "a" Insert repeatedly countries in a coloring. Fai country | old coloring new coloring [] [["a"]] [["a"]] [["a"] ; ["b"]] [["a"] ; ["b"]] [["a";"C"] ; ["6"]] | [["a"; "C"] ; ["b"]] | [["a";"C"] ; ["b"; "d"]] OODS Figure: Algorithmic idea 34 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional decomposition (1) To make things easy Are two countries neighbours? areNb: map + country country bool let areNb m cl c2 = isMember (c1, c2) m || isMember (c2,cl) m;; Can a color be extended? canBeExtBy: map color country bool let rec canBeExtBymcol c = match col with -> true | c'::col' -> not (areNb mc' c) && canBeExtBy m col' c;; canBeExtBy exMap ["0"] "a";; val it : bool = true canBeExtBy exMap ["a"; "C"] "b";; val it : bool = false 35 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional composition (1) Combining functions make things easy Extend a coloring by a country: extColoring: map coloring + country coloring Examples: extColoring exMap [] "a" extColoring exMap [["b"]] "a" extColoring exMap [["C"]] "a" = = = [["a"]] [["b"] ; ["a"]] [["a"; "C"]] let rec extColoring m cols c = match cols with | [] -> [[c]] | col::cols' -> if canBeExtBy m col c then (c::col):: cols' else col::ext Coloring m cols' c;; Function types, consistent use of symbols, and examples make program easy to comprehend 36 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional decomposition (II) To color a neighbour relation: Get a list of countries from the neighbour relation. Color these countries Get a list of countries without duplicates: let addElem x ys = if isMember x ys then ys else x::ys;;. let rec countries = function | [] -> [] 1 (c1, c2)::m -> addElem cl (addElem c2 (countries m)) ;; Color a country list: let rec colcntrs m = function | [] -> [] TC::cs -> extColoring m (colcntrs mcs) C;; Functional composition (III) The problem can now be solved by combining well-understood pieces Create a coloring from a neighbour relation: colMap: map coloring let colMap m = colcntrs m (countries m) ;; colMap exMap;; val it : string list list = [["C"; "a"); ["b"; "d"]] Example: Map Coloring. A map should be colored so that neighbouring countries get different colors "d" "b" "a" The types for country and map are straightforward": type country = string Symbols: C, C1, C2, c'; Examples: "a", "b", ... type map= (country*country) list Symbols: m; Example: val exMap = [("a","b"); ("c","d"); ("d","a")] How many ways could above map be colored? 32 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Abstract models for color and coloring type color = country list Symbols: col; Example: ["c"; "a"] type coloring = color list Symbols: cols; Example: [["c"; "a"); ["b"; "d"]] Be conscious about symbols and examples colMap: map -> coloring Meta symbol: Type Definition Sample value C: country string m: map (country+country) list["a", "b");"C", "d"); ("d","a")] col: color country list ["a";"0"] cols: coloring color list [["a"; "C"];["b";"0"]] Figure: A Data model for map coloring problem 33 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Algorithmic idea "d" "b" "a" Insert repeatedly countries in a coloring. Fai country | old coloring new coloring [] [["a"]] [["a"]] [["a"] ; ["b"]] [["a"] ; ["b"]] [["a";"C"] ; ["6"]] | [["a"; "C"] ; ["b"]] | [["a";"C"] ; ["b"; "d"]] OODS Figure: Algorithmic idea 34 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional decomposition (1) To make things easy Are two countries neighbours? areNb: map + country country bool let areNb m cl c2 = isMember (c1, c2) m || isMember (c2,cl) m;; Can a color be extended? canBeExtBy: map color country bool let rec canBeExtBymcol c = match col with -> true | c'::col' -> not (areNb mc' c) && canBeExtBy m col' c;; canBeExtBy exMap ["0"] "a";; val it : bool = true canBeExtBy exMap ["a"; "C"] "b";; val it : bool = false 35 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional composition (1) Combining functions make things easy Extend a coloring by a country: extColoring: map coloring + country coloring Examples: extColoring exMap [] "a" extColoring exMap [["b"]] "a" extColoring exMap [["C"]] "a" = = = [["a"]] [["b"] ; ["a"]] [["a"; "C"]] let rec extColoring m cols c = match cols with | [] -> [[c]] | col::cols' -> if canBeExtBy m col c then (c::col):: cols' else col::ext Coloring m cols' c;; Function types, consistent use of symbols, and examples make program easy to comprehend 36 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013 Functional decomposition (II) To color a neighbour relation: Get a list of countries from the neighbour relation. Color these countries Get a list of countries without duplicates: let addElem x ys = if isMember x ys then ys else x::ys;;. let rec countries = function | [] -> [] 1 (c1, c2)::m -> addElem cl (addElem c2 (countries m)) ;; Color a country list: let rec colcntrs m = function | [] -> [] TC::cs -> extColoring m (colcntrs mcs) C;; Functional composition (III) The problem can now be solved by combining well-understood pieces Create a coloring from a neighbour relation: colMap: map coloring let colMap m = colcntrs m (countries m) ;; colMap exMap;; val it : string list list = [["C"; "a"); ["b"; "d"]]