F# map coloring algorithm
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
BFNP – Functional Programming Lecture 3: Records, tagged values and lists
Niels Hallenberg
These slides are based on original slides by Michael R. Hansen, DTU. Thanks!!!
The original slides has been used at a course in functional programming at DTU.
1 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Disjoint Sets – An Example
A shape is either a circle, a square, or a triangle • the union of three disjoint sets
type shape = Circle of float
| Square of float | Triangle of float*float*float;;
The tags Circle, Square and Triangle are constructors:
> Circle;; val it : float -> shape = <fun:clo@3>
- Circle 2.0;; > val it : shape = Circle 2.0
- Triangle(1.0, 2.0, 3.0);; > val it : shape = Triangle(1.0, 2.0, 3.0)
- Square 4.0;; > val it : shape = Square 4.0
2 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Constructors in Patterns
A shape-area function is declared
let area = function | Circle r -> System.Math.PI * r * r | Square a -> a * a | Triangle(a,b,c) ->
let s = (a + b + c)/2.0 sqrt(s*(s-a)*(s-b)*(s-c)) ;;
> val area : shape -> real
following the structure of shapes.
• a constructor only matches itself
area (Circle 1.2) (System.Math.PI * r * r, [r 7→ 1.2]) . . .
How would you structure a program for this in C#?
3 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Enumeration types – the months
Months are naturally defined using tagged values::
type month = January | February | March | April | May | June | July | August | September | October | November | December ;;
The days-in-a-month function is declared by
let daysOfMonth = function | February -> 28 | April | June | September | November -> 30 | _ -> 31 ;;
val daysOfMonth : month -> int
4 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
The option type
type ’a option = None | Some of ’a
Distinguishes the cases ”nothing” and ”something”. predefined
The constructor Some and None are polymorphic:
Some false;; val it : bool option = Some false
Some (1, "a");; val it : (int * string) option = Some (1, "a")
None;; val it : ’a option = None
5 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
TypesLISTs
6 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Example
Find first position of element in a list:
let rec findPosI p x = function | y::_ when x=y -> Some p | _::ys -> findPosI (p+1) x ys | [] -> None;;
val findPosI : int -> ’a -> ’a list -> int option when ...
let findPos x ys = findPosI 0 x ys;; val findPos : ’a -> ’a list -> int option when ...
Examples
findPos 4 [2 .. 6];; val it : int option = Some 2
findPos 7 [2 .. 6];; val it : int option = None
Option.get(findPos 4 [2 .. 6]);; val it : int = 2
7 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Lists
A list is a finite sequence of elements having the same type:
[v1; . . . ; vn] ([ ] is called the empty list)
[2;3;6];; val it : int list = [2; 3; 6]
["a"; "ab"; "abc"; ""];; val it : string list = ["a"; "ab"; "abc"; ""]
[sin; cos];; val it : (float->float) list = [<fun:...>; <fun:...>]
[(1,true); (3,true)];; val it : (int * bool) list = [(1, true); (3, true)]
[[]; [1]; [1;2]];; val it : int list list = [[]; [1]; [1; 2]]
8 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Trees for lists
A non-empty list [x1; x2; . . . ; xn], n ≥ 1, consists of • a head x1 and • a tail [x2; . . . ; xn]
::
� � �
@ @ @
2 ::
� � �
@ @ @
3 ::
� � �
@ @ @
2 []
Graph for [2;3;2]
::
� � �
@ @ @
2 []
Graph for [2]
9 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
List constructors: [] and ::
Lists are generated as follows: • the empty list is a list, designated [] • if x is an element and xs is a list,
then so is x :: xs (type consistency)
:: associate to the right, i.e. x1::x2::xs means x1::(x2::xs)
::
� � �
@ @ @
x1 ::
� � �
@ @ @
x2 xs
Graph for x1::x2::xs
10 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Range expressions (1)
A simple range expression [b .. e], where e ≥ b, generates the list:
[b; b + 1; b + 2; . . . ; b + n]
where n is chosen such that b + n ≤ e < b + n + 1.
Example
[ -3 .. 5 ];; val it : int list = [-3; -2; -1; 0; 1; 2; 3; 4; 5]
[2.4 .. 3.0 ** 1.7];; val it : float list = [2.4; 3.4; 4.4; 5.4; 6.4]
Note that 3.0 ** 1.7 = 6.47300784.
The range expression generates the empty list when e < b:
[7 .. 4];; val it : int list = []
11 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Range expressions (2)
The range expression [b .. s .. e] generates either an ascending or a descending list:
[b .. s .. e]
=
{ [b; b + s; b + 2s; . . . ; b + ns] if s > 0 and b + ns ≤ e < b + (n + 1)s [b; b − s; b − 2s; . . . ; b − ns] if s < 0 and b − ns ≥ e > b − (n + 1)s
depending on the sign of s.
Examples:
[6 .. -1 .. 2];; val it : int list = [6; 5; 4; 3; 2]
and the float representation of 0,π/2,π, 32 π, 2π is generated by:
[0.0 .. System.Math.PI/2.0 .. 2.0*System.Math.PI];; val it : float list =
[0.0; 1.570796327; 3.141592654; 4.71238898; 6.283185307]
12 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Simple recursion on lists
We consider now three simple functions: • append • reverse • isMember
whose declarations follow the structure of lists
let rec f ... xs ... = | [] -> v | x::xs -> .... f xs ...
using just two clauses.
13 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Append
The infix operator @ (called ‘append’) joins two lists:
[x1;x2; . . .;xm] @ [y1;y2; . . .;yn] = [x1;x2; . . .;xm;y1;y2; . . .;yn]
Properties
[] @ ys = ys [x1;x2; . . .;xm] @ ys = x1::([x2; . . .;xm] @ ys)
Declaration
let rec (@) xs ys = match xs with | [] -> ys | x::xs’ -> x::(xs’ @ ys);;
val (@) : ’a list -> ’a list -> ’a list
14 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Append: evaluation
let rec (@) xs ys = match xs with | [] -> ys | x::xs’ -> x::(xs’ @ ys);;
Evaluation
[1;2] @ [3;4] 1::([2] @ [3;4]) (x 7→ 1, xs′ 7→ [2], ys 7→ [3; 4]) 1::(2::([] @ [3;4])) (x 7→ 2, xs′ 7→ [ ], ys 7→ [3; 4]) 1::(2::[3;4]) (ys 7→ [3; 4]) 1::[2;3;4] [1;2;3;4]
• Execution time is linear in the size of the first list
15 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Append: polymorphic type
The answer from the system is:
> val (@) : ’a list -> ’a list -> ’a list
• ’a is a type variable • The type of @ is polymorphic — it has many forms
’a = int: Appending integer lists
[1;2] @ [3;4];; val it : int list = [1;2;3;4]
’a = int list: Appending lists of integer list
[[1];[2;3]] @ [[4]];; val it : int list list = [[1]; [2; 3]; [4]]
@ is a built-in function
16 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Reverse rev [x1; x2; . . . ; xn] = [xn; . . . ; x2; x1]
let rec naive_rev = function | [] -> [] | x::xs -> naive_rev xs @ [x]
val naive_rev : ’a list -> ’a list
An evaluation: naive_rev[1;2;3]
naive_rev[2;3] @ [1] (naive_rev[3] @ [2]) @ [1] ((naive_rev[] @ [3]) @ [2]) @ [1] (([] @ [3]) @ [2]) @ [1] ([3] @ [2]) @ [1] (3::([] @ [2])) @ [1] (3::[2]) @ [1] [3;2] @ [1] 3::([2] @ [1]) . . . [3;2;1]
Takes O(n2) time — Built-in version (List.rev) is efficient O(n) We consider efficiency later.
17 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Membership — equality types
isMember x [y1;y2; . . .;yn] = (x = y1) ∨ (x = y2)∨ ·· · ∨ (x = yn) = (x = y1) ∨ (member x [y2, . . .,yn])
Declaration
let rec isMember x = function | [] -> false | y::ys -> x=y || isMember x ys;; val isMember : ’a -> ’a list -> bool when ’a : equality
• ’a is an equality type variable no function types • isMember (1,true) [(2,true); (1,false)] false • isMember [1;2;3] [[1]; []; [1;2;3]] true
18 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Example: sumProd
sumProd [x0;x1; . . .;xn−1] = ( x0 + x1 + . . . + xn−1 , x0 * x1 * . . . * xn−1 )
The declaration is based on the recursion formula:
sumProd [x0;x1; . . .;xn−1] = (x0 + rSum,x0 * rProd) where (rSum,rProd) = sumProd [x1; . . .;xn−1]
This gives the declaration
let rec sumProd = function | [] -> (0,1) | x::rest ->
let (rSum,rProd) = sumProd rest (x+rSum,x*rProd);;
val sumProd : int list -> int * int
sumProd [2;5];; val it : int * int = (7, 10)
19 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Example: split
Declare an F# function split such that:
split [x0;x1;x2;x3; . . .;xn−1] = ([x0;x2; . . .],[x1;x3; . . .])
The declaration is
let rec split = function | [] -> ([],[]) | [x] -> ([x],[]) | x::y::xs -> let (xs1,xs2) = split xs
in (x::xs1,y::xs2);;
Notice • a convenient division into three cases, and • the recursion formula
split [x0;x1;x2; . . .;xn−1] = (x0 :: xs1,x1 :: xs2) where (xs1,xs2) = split [x2; . . .;xn−1]
20 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
An exercise
From list of pairs to pair of lists:
unzip [(x1, y1); (x2, y2); . . . ; (xn, yn)] = ([x1; x2; . . . ; xn], [y1; y2; . . . ; yn])
Many functions on lists are predefined, e.g. @, List.length, List.rev, List.zip and many more.
21 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Match on results of recursive call
We consider declarations on the form:
let rec f ... xs ... = .... let pat(y) = f xs e(y)
Recall unzip and split from above.
22 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
The problem
An electronic cash register contains a data register associating the name of the article and its price to each valid article code. A purchase comprises a sequence of items, where each item describes the purchase of one or several pieces of a specific article.
The task is to construct a program which makes a bill of a purchase. For each item the bill must contain the name of the article, the number of pieces, and the total price, and the bill must also contain the grand total of the entire purchase.
23 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Goal and approach
Goal: the main concepts of the problem formulation are traceable in the program.
Approach: to name the important concepts of the problem and associate types with the names.
• This model should facilitate discussions about whether it fits the problem formulation.
Aim: A succinct, elegant program reflecting the model.
24 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
The problem
An electronic cash register contains a data register associating the name of the article and its price to each valid article code. A purchase comprises a sequence of items, where each item describes the purchase of one or several pieces of a specific article.
The task is to construct a program which makes a bill of a purchase. For each item the bill must contain the name of the article, the number of pieces, and the total price, and the bill must also contain the grand total of the entire purchase.
25 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
A Functional Model
• Name key concepts and give them a type
A signature for the cash register:
type articleCode = string type articleName = string type price = int type register = (articleCode * (articleName*price)) list type noPieces = int type item = noPieces * articleCode type purchase = item list type info = noPieces * articleName * price type infoseq = info list type bill = infoseq * price
exception FindArticle makeBill: register -> purchase -> bill
26 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Example
The following declaration names a register:
let reg = [("a1",("cheese",25)); ("a2",("herring",4)); ("a3",("soft drink",5)) ];;
The following declaration names a purchase:
let pur = [(3,"a2"); (1,"a1")];;
A bill is computed as follows:
makeBill reg pur;; val it : (int * string * int) list * int =
([(3, "herring", 12); (1, "cheese", 25)], 37)
27 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Functional decomposition (1)
Type: findArticle: articleCode → register → articleName * price
exception FindArticle;;
let rec findArticle ac = function | (ac’,adesc)::reg -> if ac=ac’ then adesc
else findArticle ac reg | _ -> raise FindArticle;;
The specified type is an instance of the inferred type:
val findArticle : ’a -> (’a * ’b) list -> ’b when ’a : equality
An article description is found as follows:
findArticle "a2" reg;; val it : string * int = ("herring", 4)
28 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Functional decomposition (2)
Type: makeBill: register → purchase → bill let rec makeBill reg = function
| [] -> ([],0) | (np,ac)::pur ->
let (aname,aprice) = findArticle ac reg let tprice = np*aprice let (billtl,sumtl) = makeBill reg pur ((np,aname,tprice)::billtl, tprice+sumtl);;
The specified type is an instance of the inferred type:
val makeBill : (’a * (’b * int)) list -> (int * ’a) list
-> (int * ’b * int) list * int when ’a : equality
makeBill reg pur;; val it : (int * string * int) list * int = ([(3, "herring", 12); (1, "cheese", 25)], 37)
29 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Patterns with guards: Three versions of findArticle
The if-then-else expression in
let rec findArticle ac = function | (ac’,adesc)::reg -> if ac=ac’ then adesc
else findArticle ac reg | _ -> raise FindArticle;;
may be avoided using clauses with guards:
let rec findArticle ac = function | (ac’,adesc)::reg when ac=ac’ -> adesc | (ac’,adesc)::reg -> findArticle ac reg | _ -> raise FindArticle;;
This may be simplified using wildcards:
let rec findArticle ac = function | (ac’,adesc)::_ when ac=ac’ -> adesc | _::reg -> findArticle ac reg | _ -> raise FindArticle;;
30 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Summary
• A succinct model is achieved using type declarations. • Easy to check whether it fits the problem. • Conscious choice of variables (on the basis of the model)
increases readability of the program. • Standard recursions over lists solve the problem.
31 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Example: Map Coloring.
A map should be colored so that neighbouring countries get different colors
"b" "a"
"d"
"c"
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
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
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 "a" m: map (country*country) list[("a","b");("c","d");("d","a")] col: color country list ["a";"c"] cols: coloring color list [["a";"c"];["b";"d"]]
Figure: A Data model for map coloring problem
33 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Algorithmic idea
"b" "a"
"d"
"c"
Insert repeatedly countries in a coloring.
country old coloring new coloring 1. "a" [] [["a"]] 2. "b" [["a"]] [["a"] ; ["b"]] 3. "c" [["a"] ; ["b"]] [["a";"c"] ; ["b"]] 4. "d" [["a";"c"] ; ["b"]] [["a";"c"] ; ["b";"d"]]
Figure: Algorithmic idea
34 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Functional decomposition (I)
To make things easy Are two countries neighbours?
areNb: map → country → country → bool
let areNb m c1 c2 = isMember (c1,c2) m || isMember (c2,c1) m;;
Can a color be extended?
canBeExtBy: map → color → country → bool
let rec canBeExtBy m col c = match col with | [] -> true | c’::col’ -> not (areNb m c’ c) && canBeExtBy m col’ c;;
canBeExtBy exMap ["c"] "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
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
Functional composition (I)
Combining functions make things easy Extend a coloring by a country:
extColoring: map → coloring → country → coloring
Examples: extColoring exMap [] "a" = [["a"]] extColoring exMap [["b"]] "a" = [["b"] ; ["a"]] extColoring exMap [["c"]] "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::extColoring 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
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
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 | [] -> [] | (c1,c2)::m -> addElem c1 (addElem c2 (countries m));;
Color a country list:
let rec colCntrs m = function | [] -> [] | c::cs -> extColoring m (colCntrs m cs) c;;
37 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
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"]]
38 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
BFNP – Functional Program-
ming
Niels Hallenberg
Tagged values. Construc- tors Values
Types
On modelling and problem solving
• Types are useful in the specification of concepts and operations. • Conscious and consistent use of symbols enhances readability. • Examples may help understanding the problem and its solution. • Functional paradigm is powerful.
Problem solving by combination of well-understood pieces
These points are not programming language specific
39 IT University of Copenhagen Lecture 3: Records, tagged values and lists NH 09/02/2013
- Tagged values. Constructors
- Values
- Types