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