\documentclass[9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}
%\documentclass[handout,9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}

\input{../Common/common}




\subtitle{Collections: Finite Sets and Maps}
\date {MRH 11/10/2024}% (optional)



\begin{document}

\begin{frame}
  \titlepage


\end{frame}


\begin{frame}[fragile]\frametitle{Overview}


\begin{itemize}
	
\item Conventions and tradition\\
-- example with higher-order list functions

%\bigskip	
	
%\item Types, higher-order functions and evaluations: an example \\
%-- fundamental and useful concepts \hfill recap
\end{itemize}

\bigskip \pause

\begin{itemize}
	
\item Sets and Maps as abstract data types
\begin{itemize}
\item Useful when modelling and  when programming

\item Many similarities with the list library
\end{itemize}

\end{itemize}
\end{frame}


\begin{frame}
	\begin{center}\darkgreen\Large Conventions and tradition
	\end{center}	
	
	\bigskip
	
	\begin{itemize}
		\item<2-> type names are descriptive and start with capital letters
		\item<3-> function names are descriptive and start with small letters
		\item<4-> variable names are short and consistently used
		\item<5-> function types are stated in comments
		\item<6-> types are avoided in function declarations -- unless needed
		\item<7-> self-check that wanted type is an instance of inferred type	
		\item<7-> ....
	\end{itemize}
	
	\bigskip
	\ \hfill exemplified using the Flights and Luggage problem\\ 
	\ \hfill from Week 4\\
	\ \hfill -- an old exam question
	
\end{frame}


\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (1)}
	
	\begin{itemize}
		\item Type names are descriptive and 
		\item start with capital letters
	\end{itemize}
	
\begin{alltt}\blue 
type Lid     = string    
type Flight  = string   
type Airport = string   
		
type Route   = (Flight * Airport) list   
		
type LuggageCatalogue = (Lid * Route) list  
		
let lc1 = 
   [("DL 016-914", 
       [("DL 189","ALT");("DL 124","BRU");("SN 733","CPH")]);
    ("SK 222-142", 
       [("SK 208","ALT");("DL 124","BRU");("SK 122","JFK")])]
		
	\end{alltt}
\end{frame}

\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (2)}
	
	\begin{itemize}
		\item function names are descriptive and start with small letters
		\item variable names are short and consistently used
		\item function types are stated in comments
		\item types are avoided in function declarations -- unless needed
		\item self-check that wanted type is an instance of inferred type	
	\end{itemize}
	
\begin{alltt}\blue 
// Lid * LuggageCatalogue -> Route
let rec findRoute(lid, lc) = 
   match lc with 
   | (lid1,r1)::_ when lid1=lid -> r1
   | _::lcrest        -> findRoute(lid,lcrest)
   | _                -> failwith (lid + " is not found")
\end{alltt}	
	
\pause
Notice that further comments are not needed and that
	\begin{itemize}
		\item  lid, lid', lid1 .... denote luggage identifiers
		\item f, f', f1, ... denote flights
		\item lc, lc', lc1, lcrest denote luggage catalogues
		\item r, r', r1, .. denote routes	
	\end{itemize}
\end{frame}

\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (3)}
	
\begin{alltt}\blue 
// inRoute: Flight -> Route -> bool
let rec inRoute f = 
   function
   | (f1,_)::r -> f=f1 || inRoute f r
   | []        -> false
\end{alltt}
	
	\bigskip
	
	\pause
	{\blue \verb|List.exists|} is the natural choice \\
	-- the existence of an element with a certain property is questioned
	
\begin{alltt}\blue
let inRoute f r = List.exists (fun (f1,_) -> f=f1) r
\end{alltt}	
\end{frame}


\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (4)}
	
	\begin{itemize}
		\item the function \verb|inRoute| is handy to use
	\end{itemize}
	
\begin{alltt}\blue 
// withFlight: Flight -> LuggageCatalogue -> Lid list 
let rec withFlight f = 
   function
   | []                           -> []
   | (lid,r)::lc when inRoute f r -> lid::withFlight f lc
   | _::lc                        -> withFlight f lc
\end{alltt}
	
	\bigskip
	
	\pause
	\begin{itemize}
		\item It is natural to use a fold function due to the "non-trivial" processing of elements in luggage catalogues.
		\item Since there is no restriction on the sequence of the luggage identifiers, \verb|fold| and \verb|foldBack| are both natural choices.
	\end{itemize}
	
\begin{alltt}\blue
let withFlight f lc = 
   List.fold 
     (fun lids (lid,r) -> if inRoute f r 
                          then lid::lids else lids) 
     [] 
     lc
\end{alltt}	
\end{frame}


\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (5)}
\begin{alltt}\blue
type ArrivalCatalogue = (Airport * Lid list) list	
\end{alltt}	
The task:% $\mathrm{extend: Lid*Route*ArrivalCatalogue -> ArrivalCatalogue}$
	\[\blue
	\mathrm{extend: Lid * Route * ArrivalCatalogue} \to \mathrm{ArrivalCatalogue}
	\]
	\pause
Invent a function to make things easy	
\begin{alltt}\blue
// insert: Lid -> Airport 
               -> ArrivalCatalogue->ArrivalCatalogue
let rec insert lid airp = 
   function
   | []               -> [(airp, [lid])] 
   | (airp1,ls)::rest when airp1=airp 
                      -> (airp1,lid::ls)::rest
   | pair::rest       -> pair::insert lid airp rest
\end{alltt}
	
	\bigskip
	\pause
	
\begin{alltt}\blue
let rec extend(lid, r, ac) = 
   match r with
   | []           -> ac
   | (f,airp)::r1 -> extend (lid, r1, insert lid airp ac)
\end{alltt}
\end{frame}



\begin{frame}[fragile]\frametitle{Example: Flights and Luggage (6)}
\begin{alltt}\blue
type LuggageCatalogue = (Lid * Route) list
type ArrivalCatalogue = (Airport * Lid list) list	
\end{alltt}
	
The task:% $\mathrm{extend: Lid*Route*ArrivalCatalogue -> ArrivalCatalogue}$
	\[\blue
	\mathrm{toArrivalCatalogue}: \mathrm{LuggageCatalogue} \to \mathrm{ArrivalCatalogue}
	\]
should be solved using a fold function and
	\[\blue
	\mathrm{extend: Lid * Route * ArrivalCatalogue} \to \mathrm{ArrivalCatalogue}
	\]
	
	\pause
	\bigskip
	
\begin{alltt}\blue
let toArrivalCatalogue lc = 
   List.foldBack (fun (lid,r) ac -> extend(lid,r,ac)) lc []
\end{alltt}
	
	\pause
	\bigskip
	\begin{center}\Large\redbrown
		
		Naming conventions and tradition support readability\\
		
		\pause
		\bigskip
		
		-- and so does functional decomposition 
		
	\end{center}
	
	
\end{frame}



\begin{frame}
\begin{center}\redbrown\Large\darkgreen 
FSharp's {\redbrown immutable} collections\\[5mm]
Sets and Maps	
\end{center}
\end{frame}

\begin{frame}{FSharp's {\redbrown immutable} collections}

\begin{itemize}
\item List: {\blue a finite} sequence of elements of the same type
\begin{itemize}
\item the sequence in which elements are enumerated is important
\item  repetitions among elements of a list matters
\end{itemize}

\ \\

\bigskip

\item<2-> Set: a {\blue finite} collection of elements of the same type
\begin{itemize}
	\item the sequence in which elements are enumerated is of no concern
	\item  repetitions among members of a set is of no concern
\end{itemize}
\  \hfill Today\\

\bigskip

\item<3-> Map: a {\blue finite} function from a domain of keys to values\\
\begin{itemize}
	\item the uniqueness of keys is an important property
\end{itemize}
\  \hfill Today\\

\bigskip

\item<4-> Sequence: {\blue a possibly infinite} sequence of elements of the same type
\begin{itemize}
	\item the elements of a sequence are computed by demand
\end{itemize}
\ \hfill Covered later in the semester\\

\end{itemize}
\end{frame} 


\begin{frame}[fragile]{Types, data types and abstract data types}

\begin{itemize}
\item A {\redbrown type} is generated from basic types $\texttt{\blue int, float, bool, string, \ldots}$ and type variables $\texttt{\blue 'a, 'b, 'c, \ldots}$  using type operators $\texttt{\blue *, ->, list, \ldots}$   
\end{itemize}

\bigskip
\pause


\begin{itemize}
\item A {\redbrown data type} is characterized by
\begin{itemize}
\item a type \hfill $\mathtt{\blue 'a list}$
\item a set of values \hfill  $\mathtt{\blue [\ ], [v], [v_1; ... v_n] }$
\item a set of operations \hfill $\mathtt{\blue ::}$, $\blue \verb-@-$ , $\mathtt{\blue List.rev, List.fold, ...  }$ 		
\end{itemize}	
\end{itemize}

\bigskip
\pause

\begin{itemize}
	\item A {\redbrown abstract data type} is a data type
	\begin{itemize}
		\item where the representation of values is {\redbrown hidden} 	\hfill {\darkgreen LiskovZilles 1974}
	\end{itemize}	
\end{itemize}

\bigskip

\pause
Examples:

\begin{itemize}
\item \texttt{\blue List} is a data type but not an abstract one\\ 
\qquad --- the representation of list values is visible ($\mathtt{\blue []}$ and $\mathtt{\blue ::}$)


\bigskip
\item \texttt{\blue Set} and \texttt{\blue Map} are abstract data types
\end{itemize}

\end{frame}


\begin{frame}[fragile]\frametitle{The set concept (1)}

A {\em set} (in mathematics) is a collection of element like
\[\blue
\{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \}, \{ 1, 3, 5, 7, 9\}, \Nat, \text{and}\ \Real
\]

\begin{itemize}
\item the sequence in which elements are enumerated is of no concern, and
\item repetitions among members of a set is of no concern either
\end{itemize}

\medskip
\pause

It is possible to decide whether a given value is in the set.
\[\blue \mathrm{Alice} \not \in \{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \}  \qquad \text{and} \qquad 7 \in \{ 1, 3, 5, 7, 9\} \]

\medskip
\pause

The empty set containing no element is written $\blue \{ \}$ or $\blue \emptyset$.


\end{frame}

\begin{frame}[fragile]\frametitle{The sets concept (2)}

A set $A$ is a {\em subset} of a set $B$, written $A \subseteq B$, if all the elements of $A$ are also elements of $B$, for example
\[\blue  \{ \mathrm{Ben}, \mathrm{Bob} \}  \subseteq \{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \}
\qquad \text{and} \qquad \{ 1, 3, 5, 7, 9\} \subseteq \Nat \]

\medskip
\pause

Two sets $A$ and $B$ are equal, if they are both subsets of each other:
\[\blue A=B \qquad \text{if and only if} \qquad A \subseteq B \text{ and } B \subseteq A   \]
i.e.\ two sets are equal if they contain exactly the same elements.

\medskip
\pause

The subset of a set $A$ which consists of those elements satisfying a predicate $p$ can be expressed using a {\em set-comprehension}:
\[
\{\blue x \in A\ |\ p(x) \}
\]

\medskip

For example:
\[\blue  \{ 1, 3, 5, 7, 9\} = \{ x \in \Nat\ |\ \mathrm{odd}(x) \text{ and } x < 11 \} \]

\end{frame}

\begin{frame}[fragile]\frametitle{The set concept (3)}

Some standard operations on sets:
%{\em union}: $A \cup B$, {\em intersection} $A \cap B$ and {\em difference} $A \setminus B$:
\[\blue
\begin{array}{lcll}
A \cup B      & = & \{ x\ |\ x \in A \text{ or } x \in B \}  & \text{union}\\
A \cap B      & = & \{ x\ |\ x \in A \text{ and } x \in B \} \qquad & \text{intersection} \\
A \setminus B & = & \{ x\in A\ |\ x \not \in B \}            & \text{difference}
\end{array}
\]


\begin{figure}
\def\firstcircle{(180:0.65cm) circle(0.9cm)}
\def\secondcircle{(0:0.65cm) circle(0.9cm)}
\begin{tabular}{ccc}
\begin{tikzpicture}
  \begin{scope}
    \fill[gray] \firstcircle;
    \fill[gray] \secondcircle;
  \end{scope}
\draw \firstcircle node[text=black] {$A$};
\draw \secondcircle node [text=black] {$B$};
\end{tikzpicture}
 &
\begin{tikzpicture}
  \begin{scope}
    \clip \firstcircle;
    \fill[gray] \secondcircle;
  \end{scope}
\draw \firstcircle node[text=black] {$A$};
\draw \secondcircle node [text=black] {$B$};
\end{tikzpicture} &
\begin{tikzpicture}
  \begin{scope}
    \fill[gray] \firstcircle;
    \fill[white] \secondcircle;
  \end{scope}
\draw \firstcircle node[text=black] {$A$};
\draw \secondcircle node [text=black] {$B$};
\end{tikzpicture}\\
(a) $A \cup B$ & (b) $A \cap B$ & (c) $A \setminus B$
\end{tabular}

\caption{Venn diagrams for (a) union, (b) intersection and (c) difference}
\label{fig:venn.diagram}
\end{figure}

\pause

For example
\begin{eqnarray*}
\{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \} \cup \{ \mathrm{Alice}, \mathrm{Bill}, \mathrm{Ann} \} & = & \{ \mathrm{Alice}, \mathrm{Ann}, \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \} \\
\{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \} \cap \{ \mathrm{Alice}, \mathrm{Bill}, \mathrm{Ann} \} & = & \{ \mathrm{Bill} \} \\
\{ \mathrm{Bob}, \mathrm{Bill}, \mathrm{Ben} \} \setminus \{ \mathrm{Alice}, \mathrm{Bill}, \mathrm{Ann} \} & = & \{ \mathrm{Bob}, \mathrm{Ben} \}
\end{eqnarray*}
\end{frame}


\begin{frame}[fragile]\frametitle{Abstract Data Types}

An {\redbrown Abstract Data Type}: A type together with a collection of operations, where
\begin{itemize}

\item the representation of values is hidden.

\end{itemize}


\bigskip
\pause

An abstract data type for sets must have:
\begin{itemize}

\item Operations to generate sets from the elements. Why?

\item Operations to extract the elements of a set. Why?

\item Standard operations on sets.

\end{itemize}
\end{frame}


\begin{frame}

\begin{center} 
	\Large\darkgreen
	Immutable Sets in F\#\\[5mm]
\end{center}

\end{frame}


\begin{frame}[fragile]\frametitle{An Abstract Data Type: \texttt{\blue Set<'a>}}

An abstract type for sets should at least support the following:

\begin{alltt}\blue
empty:      Set<'a>
add:        'a -> Set<'a> -> Set<'a>
union:      Set<'a> -> Set<'a> -> Set<'a>
intersect:  Set<'a> -> Set<'a> -> Set<'a>
difference: Set<'a> -> Set<'a> -> Set<'a>
contains:   'a -> Set<'a> -> bool
toList:     Set<'a> -> 'a list
\end{alltt}
where
\begin{itemize}
\item any finite set can be generated by repeatedly {\blue adding} elements to the {\blue empty} set;
\item {\blue union}, {\blue intersection} and {\blue difference} are fundamental set operations;
\item \texttt{\blue contains} and \texttt{\blue toList} are used to inspect the set
\end{itemize}

\medskip\pause
Note:
\begin{itemize}
\item the above operations are supported by the library \texttt{\blue Set}.
\item the representation of sets used by \texttt{\blue Set} is hidden from the user.
\end{itemize}

\end{frame}


\begin{frame}[fragile]\frametitle{Finite sets in F\#}

The \verb-Set- library of F\# supports finite sets. An efficient implementation is based on balanced binary trees.


\medskip

Examples:
\begin{alltt}\blue
set ["Bob"; "Bill"; "Ben"];;
\ett{val it : Set<string> = set ["Ben"; "Bill"; "Bob"]}

set [3; 1; 9; 5; 7; 9; 1];;
\ett{val it : Set<int> = set [1; 3; 5; 7; 9]}
\end{alltt}

\medskip

Equality of two sets is tested in the usual manner:
\begin{alltt}\blue
set["Bob";"Bill";"Ben"] = set["Bill";"Ben";"Bill";"Bob"];;
\ett{val it : bool = true}
\end{alltt}

\medskip
Sets are ordered on the basis of a lexicographical ordering:
\begin{alltt}\blue
compare (set ["Ann";"Jane"]) (set ["Bill";"Ben";"Bob"]);;
\ett{val it : int = -1}
\end{alltt}

\end{frame}


\begin{frame}[fragile]\frametitle{Immutability of \blue \texttt{Set<'a>}}

\begin{alltt}
let s = Set.ofList [3; 2; 0];;
\ett{val s : Set<int> = set [0; 2; 3]}

Set.add 1 s;;
\ett{val it : Set<int> = set [0; 1; 2; 3]}

s;;
\ett{val it : Set<int> = set [0; 2; 3]}	
\end{alltt}

Evaluation of {\blue Set.add 1 s} does not change the value of {\blue s}.


\end{frame} 


\begin{frame}[fragile]\frametitle{Selected further operations (1)}


\begin{itemize}
\item{\blue \verb!ofList: 'a list -> Set<'a>!}, \\
where %\\ \qquad
$\blue \verb!ofList!\ [a_0; \ldots; a_{n-1} ] =  \{a_0; \ldots; a_{n-1} \}$



\item{\blue \verb!remove: 'a -> Set<'a> -> Set<'a>!},\\
where %\\ \qquad
$\blue \verb!remove!\ a\ A = A \setminus \{a\}$



\item{\blue \verb!minElement: Set<'a> -> 'a!}  \\
where $\blue \verb!minElement!\ \{a_0, a_1, \ldots, a_{n-2}, a_{n-1}\} = a_0$ when $\blue n>0$\\
(assuming that the enumeration respect the ordering)

\end{itemize}

\medskip
\pause

Notice that minElement on a non-empty set is well-defined due to the ordering:
\begin{alltt}\blue
Set.minElement (Set.ofList ["Bob"; "Bill"; "Ben"]);;
\ett{val it : string = "Ben"}
\end{alltt}


\end{frame}


\begin{frame}[fragile]\frametitle{Selected further operations (2)}

\begin{itemize}



\item{\blue \verb!filter: ('a -> bool) -> Set<'a> -> Set<'a>!}, where % \\ \qquad
$\blue \verb!filter!\ p\ A = \{ x \in A\ | p(x)\}$\\

\item{\blue \verb!exists: ('a -> bool) -> Set<'a> -> bool!},\\ where % \\ \qquad
$\blue \verb!exists!\ p\ A = \exists x \in A. p(x)$

\item {\blue \verb!forall: ('a -> bool) -> Set<'a> -> bool!},\\ where % \\ \qquad
$\blue \verb!forall!\ p\ A = \forall x \in A. p(x)$



\item{\blue \verb!fold: ('a -> 'b -> 'a) -> 'a -> Set<'b> -> 'a!},\\ where
\[\blue
\begin{array}{ll}
\verb!fold!\ f\ a\ \{b_0, b_1, \ldots, b_{n-2}, b_{n-1}\}\\
= f(f(f (\cdots (f (f\ a\ b_0)\ b_1) \cdots)\ b_{n-2})\ b_{n-1})
\end{array}
\]

\end{itemize}

\pause

These work similar to their List siblings, e.g.
\[\blue
\begin{array}{c}
\verb!Set.fold (-) 0 (set [1; 2; 3])! = ((0-1) -2)-3 = -6
\end{array}
\]
where the ordering is exploited.

\end{frame}


\begin{frame}[fragile]\frametitle{Example: Map Coloring (1)}

Maps and colors are modelled in a natural way using sets:
\begin{alltt}\blue
type Country  = string;;
type Map      = Set<Country*Country>;;
type Color    = Set<Country>;;
type Coloring = Set<Color>;;
\end{alltt}
\ \hfill WHY?

\medskip
\pause

\begin{itemize}
\item repetition of elements is of no concern

\item order of elements is of no concern
\end{itemize}

\medskip
\pause

Function declarations will reveal the adequacy of the model.

\end{frame}

\begin{frame}[fragile]\frametitle{Example: Map Coloring (2)}

%Maps and colors are modelled in a natural way using sets:
\begin{alltt}\blue
	type Country  = string;;
	type Map      = Set<Country*Country>;;
\end{alltt}

The function:
\begin{alltt}\blue
areNb: Country -> Country -> Map -> bool	
\end{alltt}	

Two countries $c_1, c_2$ are neighbors in a map $m$,\\
\qquad if either $(c_1,c_2) \in m$ or $(c_2,c_1) \in m$:
\begin{alltt}\blue
let areNb c1 c2 m = {\redbrown ?}
\end{alltt}
\medskip

Remember:
\begin{alltt}\blue
contains: 'a -> Set<'a> -> bool
exists  : ('a -> bool) -> Set<'a> -> bool
\end{alltt}
\end{frame}

\begin{frame}[fragile]\frametitle{Example: Map Coloring (3)}
	
	\begin{alltt}\blue
		type Country  = string;;
		type Map      = Set<Country*Country>;;
		type Color    = Set<Country>;;
	\end{alltt}
	
	\medskip
The function	
\begin{alltt}\blue
canBeExtBy: Map -> Color -> Country -> bool
\end{alltt}

Color $\mathit{col}$ and be extended by a country $c$ given map $m$,\\
\qquad if for every country $c'$ in  $\mathit{col}$: $c$ and $c'$ are not neighbours in $m$
\begin{alltt}\blue
let canBeExtBy m col c = {\redbrown ?}
\end{alltt}

\pause

Remember
\begin{alltt}\blue
	forall: ('a -> bool) -> Set<'a> -> bool
\end{alltt}
\end{frame}

\begin{frame}[fragile]\frametitle{Example: Map Coloring (4)}
\begin{alltt}\blue
type Coloring = Set<Color>;;
\end{alltt}
The function
\begin{alltt}\blue
extColoring: Map -> Coloring -> Country -> Coloring
\end{alltt}
is declared as a recursive function over the coloring: \hfill WHY?

\pause

\begin{alltt}\blue
let rec extColoring m cols c =
   if Set.isEmpty cols
   then Set.singleton (Set.singleton c)
   else let col = Set.minElement cols
        let cols' = Set.remove col cols
        if canBeExtBy m col c
        then Set.add (Set.add c col) cols'
        else Set.add col (extColoring m cols' c);;
\end{alltt}

\pause
\medskip
Observations
\begin{itemize}
\item {\redbrown Ugly} compared to list version where pattern matching is used

\item List version is  {\redbrown more efficient} 
\end{itemize}

\end{frame}



\begin{frame}[fragile]\frametitle{Example: Map Coloring (5)}

	
Maps and colors are modelled in a more natural way using sets:
\begin{alltt}\blue
type Country  = string;;
type Map      = Set<Country*Country>;;
type Color    = Set<Country>;;
type Coloring = Set<Color>;;     // {\redbrown Color list is better}
\end{alltt}
	
\medskip

A set of countries is obtained from a map by the function:
\begin{alltt}\blue
countries: Map -> Set<Country>
\end{alltt}
that is based on repeated insertion of the countries into a set:
\begin{alltt}\blue
let countries m = {\redbrown ?}
\end{alltt}

\medskip
\pause


Remember
\begin{alltt}\blue
fold:     ('a -> 'b -> 'a) -> 'a -> Set<'b> -> 'a
foldBack: ('a -> 'b -> 'b) -> Set<'a> -> 'b -> 'b
Set.add:  'a -> Set<'a> -> Set<'a>
\end{alltt}
\end{frame}


\begin{frame}[fragile]\frametitle{Example: Map Coloring (6)}	
Maps and colors are modelled in a more natural way using sets:
\begin{alltt}\blue
type Country  = string;;
type Map      = Set<Country*Country>;;
type Color    = Set<Country>;;
type Coloring = Set<Color>;;     // {\redbrown Color list is better}
\end{alltt}
	
\medskip

The function
\begin{alltt}\blue
colCntrs: Map -> Set<Country> -> Coloring
\end{alltt}
is based on repeated extension of colorings by countries using the \verb-extColoring- function:
\begin{alltt}\blue
let colCntrs m cs = {\redbrown ?}
\end{alltt}
Remember
\begin{alltt}\blue
fold:     ('a -> 'b -> 'a) -> 'a -> Set<'b> -> 'a
foldBack: ('a -> 'b -> 'b) -> Set<'a> -> 'b -> 'b

extColoring: Map -> Coloring -> Country -> Coloring
\end{alltt}
\end{frame}

\begin{frame}[fragile]\frametitle{Example: Map Coloring (7)}


The function that creates a coloring from a map is declared using functional composition:

\begin{alltt}\blue
let colMap m = colCntrs m (countries m);;

let exMap = Set.ofList [("a","b"); ("c","d"); ("d","a")];;

colMap exMap;;
\ett{val it : Set<Set<string>> }
\ett{       = set [set ["a"; "c"]; set ["b"; "d"]]}
\end{alltt}
\end{frame}



\begin{frame}

\begin{center} 
	\Large\darkgreen
	Immutable Maps in F\#\\[5mm]
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{The map concept}

A {\em map\/} from a set $A$ to a set $B$ is a {\em finite\/}
subset $A'$ of $A$ together with a {\em function\/} $m$ defined on $A'$: $\blue m: A' \rightarrow B$.

The set $A'$ is called the {\em domain} of $m$:  ${\rm dom}\, m = A'$.

\medskip

A map $m$ can be described in a tabular form:
\[\blue
\begin{array}{l|l}
a_0 & b_0 \\
\hline
a_1 & b_1 \\
\hline
  & \\
\multicolumn{2}{c}{\vdots} \\
  & \\
\hline
a_{n-1} & b_{n-1} \\
\end{array}
\]
%where
%$m(a_0) = b_0, m(a_1) = b_1, \ldots, m(a_{n-1}) = b_{n-1}$
\medskip

\begin{itemize}
\item An element $a_i$ in the set $A'$ is called a \textit{key}

\item  A pair $(a_i,b_i)$ is called an \textit{entry}, and

\item $b_i$ is called the
\textit{value} for the key $a_i$.

\end{itemize}

\medskip

We denote the sets of entries of a map as follows:
\[\blue
\mathrm{entriesOf}(m) = \{ (a_0,b_0), \ldots, (a_{n-1},b_{n-1}) \}
\]
\ \hfill {\redbrown Keys are unique}

\end{frame}

\begin{frame}[fragile]\frametitle{Selected map operations in F\#}

\begin{itemize}

\item \verb!ofList: ('a*'b) list -> Map<'a,'b>!\\
%where \\
$\verb!ofList!\ [(a_0,b_0); \ldots; (a_{n-1},b_{n-1})] = m$
\medskip

%\verb!toList: Map<'a,'b> -> ('a*'b) list!, where \\
%\qquad $\verb!toList!\ m = [(a_0,b_0); \ldots;
%                                            (a_{n-1},b_{n-1})]$\\

\item \verb!add: 'a -> 'b -> Map<'a,'b> -> Map<'a,'b>!\\ %where %\\
$\verb!add!\ a\ b\ m = m'$, where $m'$ is obtained $m$ by overriding $m$ with the entry $(a,b)$
%\verb!containsKey: 'a -> Map<'a,'b> -> bool!, where $\verb!containsKey!\ a\ m = a \in \mathrm{dom}\ m$\\
\medskip

\item \verb!find: 'a -> Map<'a,'b> -> 'b!\\
$\verb!find!\ a\ m = m(a)$, if $a \in \mathrm{dom}\ m$;\\
otherwise an exception is raised
\medskip

\item \verb!tryFind: 'a -> Map<'a,'b> -> 'b option!\\
$\verb!tryFind!\ a\ m = \mathtt{Some}\ (m(a))$, if $a \in \mathrm{dom}\ m$; \texttt{None} otherwise
\medskip

\item \verb!foldBack:('a->'b->'c->'c) -> Map<'a,'b> -> 'c -> 'c!\\
$\verb!foldBack!\ f\ m\ c= f\, a_0\, b_0\, (f\, a_1\, b_1\, (f \ldots (f\, a_{n-1}\, b_{n-1}\, c) \cdots ))$
\end{itemize}

\end{frame}



\begin{frame}[fragile]\frametitle{Example: Cash register (1)}

\begin{alltt}\blue
type ArticleCode = string;;
type ArticleName = string;;
type NoPieces    = int;;
type Price       = int;;

type Info        = NoPieces * ArticleName * Price;;
type Infoseq     = Info list;;
type Bill        = Infoseq * Price;;
\end{alltt}

\medskip
\pause

The natural model of a register is using a map:
\begin{alltt}\darkgreen
type Register    = Map<ArticleCode, ArticleName*Price>;;
\end{alltt}
since an article code is {\em\redbrown a unique identification} of an article.

\medskip

First version:
\begin{alltt}\blue
type Item        = NoPieces * ArticleCode;;
type Purchase    = Item list;;
\end{alltt}

\end{frame}


\begin{frame}[fragile]\frametitle{An example}

\begin{alltt}\blue
let reg1 = Map.ofList [("a1",("cheese",25));
                       ("a2",("herring",4));
                       ("a3",("soft drink",5))];;
\ett{val reg1 : Map<string,(string * int)> =}
\ett{  map [("a1", ("cheese", 25)); ("a2", ("herring", 4)); }
\ett{       ("a3", ("soft drink", 5))]}
\end{alltt}

\medskip

An entry can be added to a map using \verb!add! and the value for a key in a map is retrieved using either \verb!find! or \verb!tryFind!:
\begin{alltt}\blue
let reg2 = Map.add "a4" ("bread", 6) reg1;;
\ett{val reg2 : Map<string,(string * int)> =}
\ett{  map [("a1", ("cheese", 25)); ("a2", ("herring", 4));}
\ett{       ("a3", ("soft drink", 5)); ("a4", ("bread", 6))]}
	
Map.find "a2" reg1;;
\ett{val it : string * int = ("herring", 4)}
	
Map.tryFind "a2" reg1;;
\ett{val it : (string * int) option = Some ("herring", 4)}
\end{alltt}

\end{frame}




\begin{frame}[fragile]\frametitle{Example: Cash register (1) - a recursive program}

\begin{alltt}\blue
exception FindArticle;;

(* makebill: Register -> Purchase -> Bill *)
let rec makeBill reg = function
    | []           -> ([],0)
    | (np,ac)::pur ->
        match Map.tryFind ac reg with
        | None              -> raise FindArticle
        | Some(aname,aprice) ->
            let tprice         = np*aprice
            let (infos,sumbill) = makeBill reg pur
            ((np,aname,tprice)::infos, tprice+sumbill);;

let pur = [(3,"a2"); (1,"a1")];;
makeBill reg1 pur;;
\ett{val it : (int * string * int) list * int =}
\ett{  ([(3, "herring", 12); (1, "cheese", 25)], 37)}
\end{alltt}

\pause

\begin{itemize}

\item the lookup in the register is managed by a \verb!Map.tryFind!

\end{itemize}

\end{frame}

\begin{frame}[fragile]\frametitle{Example: Cash register (2) - using List.foldBack}

\begin{alltt}\blue
let makeBill' reg pur =
   let f (np,ac) (infos,billprice)
          = let (aname, aprice) = Map.find ac reg
            let tprice          = np*aprice
            ((np,aname,tprice)::infos, tprice+billprice)
   List.foldBack f pur ([],0);;

makeBill' reg1 pur;;
\ett{val it : (int * string * int) list * int =}
\ett{  ([(3, "herring", 12); (1, "cheese", 25)], 37)}
\end{alltt}


\begin{itemize}

\item<2-> the recursion is handled by List.foldBack

\item<3-> the exception is handled by \verb!Map.find!

\end{itemize}
\end{frame}


\begin{frame}{Summary}
	
	\begin{itemize}
		\item The concepts of sets and maps.
		
		\item Fundamental operations on sets and maps.
		
		\item Applications of sets and maps.
	\end{itemize}
		
\end{frame}

\end{document}

\begin{frame}

\begin{center}\Large
	\darkgreen Value restriction on polymorphic expressions
\end{center}

\pause
\bigskip
A restriction introduced to make the type system sound
\begin{itemize}
\item needed due to the imperative features of F\#
\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Examples on errors with polymorphic functions (1)}
\begin{alltt}\blue	
let empty = [] @ [];;
\ett{stdin(3,5): error FS0030: Value restriction.} 
\ett{The value 'empty' has been inferred to have generic type}
\ett{val empty : '_a list}   
\pause 
\ett{\redbrown{Either define 'empty' as a simple data term,}} 
\ett{make it a function with explicit arguments or,} 
\ett{if you do not intend for it to be generic,} 
\ett{   add a type annotation.}
\end{alltt}	

\pause
\begin{alltt}\redbrown
let empty = [];;  // WORKS!
\ett{val empty : 'a list}
\end{alltt}

\end{frame}	


\begin{frame}[fragile]\frametitle{Examples on errors with polymorphic functions (2)}
\begin{alltt}\blue	
List.rev [];;
\ett{stdin(5,1): error FS0030: Value restriction.} 
\ett{\darkgreen{The value 'it' has been inferred to have generic type}}
\ett{val it : '_a list}   
\pause 
\ett{Either define 'it' as a simple data term,} 
\ett{make it a function with explicit arguments or,} 
\ett{\redbrown{if you do not intend for it to be generic,}} 
\ett{\redbrown{   add a type annotation.}}
\end{alltt}	

\pause
\bigskip

\begin{alltt}\redbrown
List.rev ([]: int list);;  // WORKS!
\ett{val it : int list = []}
\end{alltt}

\pause
\bigskip

\begin{itemize}
\item a top-level expression is considered a top-level declaration of \texttt{\blue it}:
\end{itemize}
\begin{alltt}\darkgreen
let it = List.rev ([]: int list);;
\ett{val it : int list = []}
\end{alltt}

\end{frame}	

\begin{frame}[fragile]\frametitle{Examples on errors with polymorphic functions (3)}
\begin{alltt}\blue	
let h = (<<) id;;
\ett{stdin(10,5): error FS0030: Value restriction} 
\ett{\darkgreen{The value 'h' has been inferred to have generic type}}
\ett{    val h : (('_a -> '_b) -> '_a -> '_b) }   
\pause 
\ett{\redbrown{Either make the arguments to 'h' explicit or}}  
\ett{if you do not intend for it to be generic,} 
\ett{   add a type annotation.}
\end{alltt}	

\pause
\bigskip

\begin{alltt}\redbrown
let h g = (<<) id g;;  // WORKS!
\ett{val h : g:('a -> 'b) -> ('a -> 'b)}
\end{alltt}

\pause
\bigskip

\begin{itemize}
\item What is the problem solved by this restriction?
\item What is the solution to this problem?
\end{itemize}

\end{frame}	


\begin{frame}[fragile]\frametitle{An "imperative" issue with Polymorphism}

\begin{itemize}
\item A type issue to be addressed in the {\redbrown imperative} fragment of F\#.
\end{itemize}

\bigskip

The following hypothetical code does {\darkgreen NOT} compile:	
\begin{alltt}\blue
let{\redbrown mutable} a = []            // let a = ref []

let f x = a <- x::a
\ett{\darkgreen val f: 'a -> unit} 

f 1;;

f "ab";;

a;;
\ett{val it : {\redbrown ????} list = ["ab";1]} // a BIG type problem
\end{alltt}	
\end{frame}	


\begin{frame}[fragile]\frametitle{A solution: Value Restriction on Polymorphism}

A {\blue value expression} is an expression that is not reduced further by an evaluation, for example:	
\begin{alltt}\blue
[]      Some []    fun g -> (<<) id g 
\end{alltt}	
\pause
\medskip

The following are not value expressions:
\begin{alltt}\blue
[]@[]      List.rev []      (<<) id 
\end{alltt}
as they can be further evaluated.

\pause
\bigskip

Every top-level declarations $\blue \mathtt{let}\ \mathit{id}\ = e$ is subject to the following restriction on $\blue e$:
\begin{itemize}
\item All monomorphic expressions are OK,
\item all value expressions are OK, even polymorphic ones, and
\item at top-level, polymorphic non-value expressions are forbidden
\end{itemize} 	

\pause
\bigskip
\begin{center}
An expression $\blue \mathtt{ref}\ e$ in a declaration of the form\\ 
$\blue \mathtt{let}\ \mathit{id}\ = \mathtt{ref}\ e$ (or equivalently $\blue \mathtt{let\ mutable}\ \mathit{id}\ = e$)  \\ is {\redbrown NOT} considered a value expression (even when $\blue e$ is a constant)
\end{center}

\end{frame}	

\begin{frame}[fragile]
\frametitle{Examples revisited}
A polymorphic value expression:	
\begin{alltt}\redbrown
let empty = [];;  // WORKS!
\ett{val empty : 'a list}
\end{alltt}

\pause
A monomorphic expression, that is not a value expression:
\begin{alltt}\redbrown
List.rev ([]: int list);;  // WORKS!
\ett{val it : int list = []}
\end{alltt}

\pause
\bigskip
A declaration of a function with an explicit parameter
\pause
\bigskip

\begin{alltt}\redbrown
let f g = (<<) id g;;  // WORKS!
\ett{val f : ('a -> 'b) -> ('a -> 'b)}
\end{alltt}

\pause
\medskip
is an abbreviation for
\begin{alltt}\blue
let f = fun g -> (<<) id g;; 
\end{alltt}
and a closure is a value expression
\end{frame}


\begin{frame}

\begin{center}\Large
	\darkgreen Value restriction on polymorphic expressions
\end{center}

\pause
\bigskip
A restriction introduced to make the type system sound
\begin{itemize}
	\item needed due to the imperative features of F\#
\end{itemize}

\pause
\bigskip
\begin{itemize}
\item Annoying - but not a severe restriction
\item Compiler gives good hints to possible solutions	
\end{itemize}


\end{frame}




\end{document}
