
\documentclass[9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}
%\documentclass[handout,9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}
\usepackage{graphicx}
\input{../Common/common}




\subtitle{Disjoint Unions and Higher-order list functions}
\date {MRH 26/09/2024}





\begin{document}

\begin{frame}
  \titlepage


\end{frame}



\begin{frame}{Overview}

\begin{itemize}

\item About F\#

\medskip

\item Disjoint union (or Tagged Values)\\

\begin{itemize}

\item Groups different kinds of values into a single set.
\end{itemize}

\bigskip

\item Higher-order functions on lists\\

\begin{itemize}

\item many list functions follow ``standard'' schemes
\medskip

\item avoid (almost) identical code fragments by
parameterizing functions with functions
\medskip

\item higher-order list functions based on natural concepts
\medskip

\item succinct declarations achievable using higher-order functions
\end{itemize}

%\medskip

\item On types for functions briefly
\end{itemize}

\end{frame}



\begin{frame}[fragile]\frametitle{Precedence and associativity rules for expressions}


\begin{table}[h]
	\begin{center}
		\begin{tabular}{|c|c|c|} \hline
			Operator           &  Association & Precedence\\ \hline
			\texttt{**}       & Associates to the right & highest\\ \hline
			\texttt{* / \%}    & Associates to the left & \\ \hline
			\texttt{+ -}       & Associates to the left &\\ \hline
			\texttt{= <> > >= < <=} & No association & \\ \hline
			\texttt{\&\&} & Associates to the left & \\ \hline
			\texttt{||} & Associates to the left & lowest \\ \hline
		\end{tabular}
	\end{center}
%	\caption{Operator precedence and association \label{Table:assoc.prec}}
\end{table}

\begin{itemize}
\item  a monadic operator has higher precedence than any dyadic

\item higher (larger) precedence means earlier evaluation

\item<2-> function application associates to the left

\item<3-> abstraction \verb!fun x -> e! extends as far to the right as possible 
\end{itemize} 
For example:
\begin{itemize}
\item $\blue \texttt{- 2 - 5 * 7 > 3 - 1}
	\mbox{\ \  means\   \ }
	\texttt{((-2)-(5*7)) > (3-1)}$ 
\item $\blue\texttt{fact 2 - 4} \mbox{\ \ means\ \ }  \texttt{(fact 2) - 4}$

\item<2-> $\blue e_1\ e_2\ e_3\ e_4 \mbox{\ \ means\ \ } ((e_1\ e_2)\ e_3)\ e_4$ 	

\item<3-> $\blue \verb!fun x -> x 2! \mbox{\ \ means\ \ }$ {\redbrown ????}
\end{itemize}


\end{frame}

\begin{frame}[fragile]\frametitle{Precedence and associativity rules for types}

\begin{itemize}
\item  infix type operators: \verb|*| and \verb|->| 
\item suffix type operator:  \verb|list|
\end{itemize}

\pause
\medskip

Association rules:
\begin{itemize}
\item \verb|*| has NO association 
\item \verb|->| associates to the right
\end{itemize}

\pause
\medskip
Precedence rules:
\begin{itemize}
\item The suffix operator \verb|list| has highest precedence
\item  \verb|*| has higher precedence than \verb|->|	
\end{itemize}

\bigskip

For example:
\begin{itemize}
	\item<4-> $\blue \texttt{int*int*int list}
	\mbox{\ \  means\   \ }
	\texttt{(int*int*(int list))}$ 
	\item<5-> $\blue\texttt{int->int->int->int} \mbox{\ \ means\ \ }  \texttt{int->(int->(int->int))}$
	
	\item<6-> $\blue  \texttt{'a*'b->'a*'b list}
	 \mbox{\ \ means\ \ } \texttt{('a*'b)->('a*('b list))}$ 	
	
\end{itemize}

\end{frame}




\begin{frame}[fragile]{Overview: Syntactical constructs in ``our part of'' F\# }

\begin{itemize}
	\item Constants: {\blue 0, 1.1, true, ...}
	
	\medskip
	
	\item<2-> Patterns: $\blue x \quad \_  \quad (p_1, \ldots, p_n) \quad p_1\!::\!p_2 \quad [p_1; \ldots; p_n]$\\ 
	$\blue p_1 | p_2 \quad p\ \mathtt{when}\ e \quad p\ \mathtt{as}\ x \quad  p\!:\!t  \ldots$   
	
	\medskip
	
	\item<3-> Expressions: $\blue x \quad (e_1,\ldots,e_n) \quad e_1\!::\!e_2 \quad [p_1; \ldots; p_n] $\\[2mm]
	$\blue e_1 e_2 \quad  e_1\! \oplus\! e_2 \quad (\oplus) \quad \mathtt{let}\ p_1 = e_1\ \mathtt{in}\ e_2$ \\[2mm]
	$\blue  e\!:\!t \quad  \mathtt{if}\ e\ \mathtt{then}\ e_1\  \mathtt{then}\ e_2 \qquad \mathtt{match}\ e\ \mathtt{with}\ clauses$\\[2mm] 
	$\blue \mathtt{fun}\ p_1 \cdots p_n \verb!->! e \qquad \mathtt{function}\ clauses \quad \ldots$   
	
	\medskip
	
	\item<4-> Declarations $\blue \mathtt{let}\ f\  p_1 \ldots p_n = e \quad \mathtt{let\ rec}\ f\  p_1 \ldots p_n = e$, \hfill $\blue n\ge 0$  
	
	\medskip
	
	\item<5-> Types\\ $\blue \mathtt{int}  \quad \blue \mathtt{float}  \quad \mathtt{bool}  \quad \mathtt{string}  \quad 'a \quad  T\texttt{<}t_1, \ldots , t_n \texttt{>} \quad \ldots$\\
	$\blue t_1\!*\!t_2\!*\!\cdots\!*\!t_n  \quad  t\ \mathtt{list}  \quad t_1 \verb|->| t_2 \quad  \ldots$   
	
	\medskip
	
	\item<6-> Type abbreviations $\blue \mathtt{type}\  T\texttt{<}'a_1,\ldots, 'a_n\texttt{>} = t$
	
	\medskip	
	
	\item<7-> Type declarations	
	$\redbrown \mathtt{type}\ T\texttt{<}'a_1,\ldots, 'a_n\texttt{>} = C_1\ |\ \cdots  |\ C_i\ \texttt{of}\ t_i\ |\ \cdots$
\end{itemize}

\medskip

\onslide<3->{where the construct $\blue clauses$ has the form:
	\begin{alltt}\blue 
		| p\(\sb{1}\) -> e\(\sb{1}\)
		| \(\ldots\)
		| p\(\sb{n}\) -> e\(\sb{n}\)
	\end{alltt} 
}
\end{frame}

\begin{frame}

\begin{center}
	\Large\darkgreen Disjoint Sets -- Tagged Values
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{Part I: Disjoint Sets -- An Example}

A {\em\blue shape} is either a {\redbrown circle}, a {\redbrown
square}, or a {\redbrown triangle}

\begin{itemize}
\item %\fromSlide{2}{
the union of {\redbrown three disjoint} sets%}
\end{itemize}


%\medskip
\pause

%Syntax:
\begin{alltt}\blue
type Shape =
  | Circle of float                     (* 1 *)
  | Square of float                     (* 2 *)
  | Triangle of float*float*float;;     (* 3 *)  
\end{alltt}

\bigskip
\pause

This declaration provides three {\darkgreen rules} for generating {\blue shapes}:
% of type {\redbrown \verb-Shape-}:
\begin{itemize}
\item 
if $\blue r:\verb!float!$, then $\blue \verb!Circle!\ r :\verb!Shape!$ 
\hfill \verb!(* 1 *)!
\medskip
	  
\item if $\blue s: \mathtt{float}$, then $\blue \mathtt{Square}\ s : \mathtt{Shape}$ \hfill \verb!(* 2 *)!	 
\medskip

\item if $\blue \blue (a,b,c): \verb!float*float*float!$,\\ then $\blue \mathtt{Triangle}(a,b,c) :\mathtt{Shape}$ \hfill \verb!(* 3 *)!
\end{itemize}

\bigskip
\pause
A type like {\blue Shape} is also called an {\redbrown algebraic data type}

\end{frame}

\begin{frame}[fragile]\frametitle{Part I: Disjoint Sets -- An Example (II)}


The tags \texttt{\normalsize\blue Circle},
\texttt{\normalsize\blue Square} and
\texttt{\normalsize\blue Triangle} are called 
{\redbrown
constructors}:
\[\blue 
\begin{array}{lcl}
\mathtt{Circle} & : &  \mathtt{float} \to \mathtt{Shape}\\
\mathtt{Square} & : &  \mathtt{float} \to \mathtt{Shape}\\
\mathtt{Triangle} & : &  \mathtt{float*float*float} \to \mathtt{Shape}\\
\end{array}
\]

\pause 
\bigskip

\begin{alltt}
- 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
\end{alltt}

\bigskip
\pause


\begin{center}
$\blue \mathtt{Circle}$, $\blue \mathtt{Square}$ and $\blue \mathtt{Triangle}$ are used\\ to construct values of type  $\redbrown \mathtt{Shape}$,
\end{center}

\end{frame}


\begin{frame}[fragile]\frametitle{Constructors in Patterns}

A shape-area function is declared

{\blue
\begin{verbatim}
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 -> float
\end{verbatim}}
following the structure of shapes. \hfill {\redbrown using Heron's formula}


\pause
\bigskip
\begin{itemize}
\item a constructor only matches itself
\end{itemize}

\pause

\[\blue
\begin{array}{ll}
     & \verb?area (Circle 1.2)?\\
\lto & (\verb/System.Math.PI * r * r/,\ \  [\mathtt{r} \mapsto \verb-1.2-]) \\
\lto & \ldots
\end{array}
\]
\end{frame}



\begin{frame}[fragile]\frametitle{Enumeration types -- the months}

Months are naturally defined using tagged values::
\begin{alltt}\blue
type Month = | January | February | March | April
             | May | June | July | August | September
             | October | November | December;;
\end{alltt}

\pause
\medskip

The days-in-a-month function is declared by
\begin{alltt}\blue
let daysOfMonth = 
  function
  | February                            -> 28
  | April | June | September | November -> 30
  | _                                   -> 31;;
\ett{val daysOfMonth : Month -> int}
\end{alltt}

\pause
\medskip
\begin{center}
Observe: Constructors need not have arguments
\end{center}

\end{frame}


\begin{frame}[fragile]\frametitle{The \texttt{\Large\redbrown option} type}

{\blue
\begin{alltt}
type 'a option = None | Some of 'a
\end{alltt}
}

Distinguishes the cases "nothing" and "something".\\
    \hfill {\redbrown predefined}


\bigskip
\pause

The constructor \verb/Some/ and \verb-None- are polymorphic:
\begin{alltt}\blue
Some false;;
\ett{val it : bool option = Some false}

Some (1, "a");;
\ett{val it : (int * string) option = Some (1, "a")}

None;;
\ett{val it : 'a option = None}
\end{alltt}

\pause
\medskip
\begin{center}
	Observe: type variables are allowed in declarations of algebraic types 
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{Example: Find first position of element in a list}

\begin{alltt}\blue
let rec findPosA p x = 
   function
   | y::_ when x=y -> Some p
   | _::ys         -> findPosA (p+1) x ys
   | []            -> None;;
\ett{val findPosA : int -> 'a -> 'a list -> int option when ...}
\pause

let findPos x ys = findPosA 0 x ys;;
\ett{val findPos : 'a -> 'a list -> int option when ...}
\end{alltt}

\pause
\medskip
Examples
\begin{alltt}\blue
findPos 4 [2 .. 6];;
\ett{val it : int option = Some 2}

findPos 7 [2 .. 6];;
\ett{val it : int option = None}

\redbrown{Option.get}(findPos 4 [2 .. 6]);;
\ett{val it : int = 2}
\end{alltt}

\end{frame}


\begin{frame}[fragile]
\frametitle{Declaration of Algebraic data types yield {\redbrown new} types}

%Consider the example:

\begin{alltt}\blue 
	type T = A of int;;
	
	let v = A 1;;
	\ett{val v: T = A 1}
	
	\pause
	type T = A of int;;     // declaration of a new type
	
	let v' = A 1;;
	\ett{val v': T = A 1}
	
	v=v';;\pause
	\ett{\redbrown{error FS0001: This expression was expected to have}} 
	\ett{\redbrown{type 'FSI_0011.T'   but here has type 'FSI_0013.T'}} 
\end{alltt}
The second declaration do indeed yield a {\redbrown genuine new type}. 

\end{frame}


\begin{frame}
	\frametitle{Exercise}

A (teaching) room at DTU is either an auditorium or a databar:
\begin{itemize}
	\item  an auditorium is characterized by a location and a number of seats.
	\item a databar is characterized by a location, a number of computers and a number of seats. 
\end{itemize} 

\bigskip
Declare a type $\blue Room$.

\pause
\bigskip

Declare a function:
\[\blue seatCapacity: Room \to int\]

\pause
\bigskip

Declare a function 
\[\blue computerCapacity: Room \to int\ option\]
\end{frame}


\begin{frame}[fragile]\frametitle{Declaration of monomorphic and polymorphic types}

A declaration of a {\redbrown monomorphic} type has the form:

\[\blue 
\mathtt{type}\ T = t
\] 
where $\blue t$ {\redbrown does not contain type variables}.

\bigskip 
\pause

A declaration of a {\redbrown polymorphic type} has the form:
\[\blue 
\mathtt{type}\ T<'a_0, 'a_1, \ldots, 'a_n> = t
\]
where  $\blue t$ may {\redbrown contain type variables $\blue 'a_0, 'a_1, \ldots, 'a_n$}.

\bigskip
\pause 
A declaration of a polymorphic type
\begin{itemize}
\item $\blue \verb|type Map<'c> = ('c * 'c) list|$
\end{itemize}

\bigskip \pause
Declarations of monomorphic types:
\begin{itemize}
\item $\blue \verb!type Country  = A | B | C | D | E | F!$
\item $\blue \verb|type SmallMap = Map<Country>|$
\end{itemize}

\end{frame}


\begin{frame}

\begin{center}
	\Large\darkgreen Higher-order list functions
\end{center}

\end{frame}


\begin{frame}{Part 2:Motivation}

Higher-order functions are

\begin{itemize}

\item everywhere\\[3mm]
\qquad $\blue \Sigma_{i=a}^b {\darkgreen f}(i),\ \frac{d {\darkgreen f}}{d x},\ \{x \in A\ |
\ {\darkgreen P}(x) \}, \ldots $

\item<2-> powerful\\[3mm]
\qquad Parameterized modules, succinct code
$\blue \ldots$

\end{itemize}

\pause[3]
\bigskip
\begin{center}\large\redbrown HIGHER-ORDER FUNCTIONS ARE USEFUL \end{center}

\end{frame}


\begin{frame}[fragile]


\ \hfill{\blue now down to earth}

\pause

\begin{itemize}
\item Many recursive declarations follows the same schema.
\end{itemize}

For example:

{\blue
\begin{verbatim}
let rec f = function
            | []    ->   ...
            | x::xs ->   ... f(xs) ...
\end{verbatim}
}
\bigskip
\pause

\begin{center}\redbrown
Succinct declarations achievable using higher-order functions
\end{center}

Contents

\begin{itemize}

\item Higher-order list functions (in the library)
\begin{itemize}
\item map
\item contains, exists, forall, filter, tryFind
\item foldBack, fold
\end{itemize}

\end{itemize}

\pause
\bigskip

\begin{center}\blue
Avoid (almost) identical code fragments by\\
\redbrown parameterizing functions with functions
\end{center}


\end{frame}



\begin{frame}[fragile]\frametitle{A simple declaration of a list function}

A typical declaration following the structure of lists:
\begin{alltt}
let rec posList = function
                  | []    -> []
                  | x::xs -> (x > 0)::posList xs;;
\ett{val posList : int list -> bool list}

posList [4; -5; 6];;
\ett{val it : bool list = [true; false; true]}
\end{alltt}

\bigskip
\pause

{\redbrown Applies the function  {\blue \texttt{fun\
x\ ->\ x\
>\ 0}} to each element in a list}

\end{frame}


\begin{frame}[fragile]\frametitle{Another declaration with the same structure}

\begin{alltt}
let rec addElems = function
                   | []        -> []
                   | (x,y)::zs -> (x+y)::addElems zs;;
\ett{val addElems : (int * int) list -> int list}

addElems [(1,2) ;(3,4)];;
\ett{val it : int list = [3; 7]}
\end{alltt}

\bigskip
\pause
{\redbrown Applies the addition function} {\blue
\texttt{+}} {\redbrown to each pair of integers in a list}

\end{frame}


\begin{frame}[fragile]\frametitle{The function:\ \ {\Large\tt\redbrown map}}

{\redbrown Applies a function to each element in a list} {\blue \[
\mathtt{map}\ f\ [v_1; v_2; \ldots; v_n ]\ =\ [f(v_1); f(v_2);
\ldots; f(v_n)]
\]}

{\redbrown Declaration} \hfill {\darkgreen Library function}
\begin{alltt}
let rec map f = function
                | []    -> []
                | x::xs -> f x :: map f xs;;
\ett{val map : ('a -> 'b) -> 'a list -> 'b list}
\end{alltt}

\bigskip
\pause

{\redbrown Succinct declarations can be achieved using map, e.g.}
\begin{alltt}
let posList = map (fun x -> x > 0);;
\ett{val posList : int list -> bool list}

let addElems = map (fun (x,y) -> x+y);;
\ett{val addElems : (int * int) list -> int list}
\end{alltt}

\end{frame}


\begin{frame}{Exercise}

Declare a function {\blue \[ \mathtt{g}\ [x_1, \ldots, x_n] =
[x_1^2+1, \ldots, x_n^2+1]
\]}

\bigskip

\bigskip

Remember {\blue \[ \mathtt{map}\ f\ [v_1; v_2; \ldots; v_n ]\ =\
[f(v_1); f(v_2); \ldots; f(v_n)]
\]}
where
\begin{alltt}\blue
map: ('a -> 'b) -> 'a list -> 'b list
\end{alltt}


\end{frame}


\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown exists}}


{\redbrown Predicate: \blue For some $x$ in $xs: p(x)$.}

\pause

{\blue
\[
\mathtt{exists}\;p\;\mathit{xs} = \left\{
\begin{array}{ll}
\mathrm{true} & \mbox{if $p(x) =  \mathtt{true}$ for some $x$ in $\mathit{xs}$}\\
\mathrm{false} & \mbox{otherwise}
\end{array}
\right.
\]
}

\pause

{\redbrown Declaration}\hfill {\darkgreen Library function}
\begin{alltt}
let rec exists p = function
                   | []    -> false
                   | x::xs -> p x || exists p xs;;
\ett{val exists : ('a -> bool) -> 'a list -> bool}
\end{alltt}

\bigskip
\pause

{\redbrown Example}
\begin{alltt}
exists (fun x -> x>=2) [1; 3; 1; 4];;
\ett{val it : bool = true}
\end{alltt}

\end{frame}

\begin{frame}{Exercise}

Declare \texttt{\blue contains} function using \texttt{\blue
exists}.

\bigskip

\begin{alltt}
let contains x ys = exists  {\redbrown ?????} ;;\\
\ett{val contains : 'a -> 'a list -> bool  when 'a : equality}
\end{alltt}

\bigskip

\bigskip

Remember {\blue
\[
\mathtt{exists}\;p\;\mathit{xs} = \left\{
\begin{array}{ll}
\mathrm{true} & \mbox{if $p(x) =  \mathtt{true}$ for some $x$ in $\mathit{xs}$}\\
\mathrm{false} & \mbox{otherwise}
\end{array}
\right.
\]
}
where
\begin{alltt}\blue
exists: ('a -> bool) -> 'a list -> bool
\end{alltt}

\bigskip
 {\darkgreen {\blue contains} is a Library function}


\end{frame}



\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown forall}}


{\redbrown Predicate: \blue For every $x$ in $xs: p(x)$.}

\pause

{\blue
\[
\mathtt{forall}\;p\;\mathit{xs} = \left\{
\begin{array}{ll}
\mathrm{true} & \mbox{if $p(x) =  \mathrm{true}$, for all elements
$x$ in
\textit{xs}}\\
\mathrm{false} & \mbox{otherwise}
\end{array}
\right.
\]}

\bigskip
\pause

{\redbrown Declaration}\hfill {\darkgreen Library function}
\begin{alltt}
let rec forall p = function
                   | []    -> true
                   | x::xs -> p x && forall p xs;;
\ett{val forall : ('a -> bool) -> 'a list -> bool}
\end{alltt}

\bigskip
\pause

{\redbrown Example}
\begin{alltt}
forall (fun x -> x>=2) [1; 3; 1; 4];;
\ett{val it : bool = false}
\end{alltt}

\end{frame}

\begin{frame}{Exercises}

\onslide<1>{
Declare a function
\[{\blue
\mathtt{disjoint}\ \mathit{xs}\ \mathit{ys}}
\]
which is true when there are no common elements in the lists
{\blue $\mathit{xs}$} and {\blue $\mathit{ys}$}, and false
otherwise.
}



\bigskip

Remember {\blue
\[
\mathtt{forall}\;p\;\mathit{xs} = \left\{
\begin{array}{ll}
\mathrm{true} & \mbox{if $p(x) =  \mathrm{true}$, for all elements
$x$ in
\textit{xs}}\\
\mathrm{false} & \mbox{otherwise}
\end{array}
\right.
\]}
where
\begin{alltt}\blue
forall : ('a -> bool) -> 'a list -> bool
\end{alltt}

\end{frame}


\begin{frame}[fragile]\frametitle{Validating properties of map-coloring programs (I)}

Remember: \hfill {\redbrown Script available on Learn}
\begin{alltt}\blue 
	type Map<'c>      = ('c * 'c) list
	type Color<'c>    = 'c list
	type Coloring<'c> = Color<'c> list
\end{alltt}

\bigskip 

An auxiliary function in the script:
\begin{alltt}\blue 
	countries: Map<'c> -> 'c list
\end{alltt}
should give a list containing all elements in a map.

\bigskip
\pause
The function should satisfy the property $\blue prop_1(m)$:  \\
\qquad      every country in map $\blue m$ must be in  $\blue \texttt{countries}\ m$. 

\bigskip
\pause

\begin{center}\redbrown
	How to declare a function that can check this property?
\end{center}



\end{frame}


\begin{frame}[fragile]\frametitle{Validating properties of map-coloring programs (II)}

We restrict our attention to a small number of countries when using FsCheck to validate $\blue \mathtt{prop}_1$. \hfill {\redbrown Why?} 

\pause 
\bigskip

\begin{alltt}\blue 
#r "nuget: FsCheck";;
open FsCheck;;

type Country  = A | B | C | D | E | F
type SmallMap = Map<Country>

let prop1({\redbrown{m:SmallMap}}) = 
   let cs = countries m
   List.forall (fun (c1,c2) ->  List.contains c1 cs && 
                                List.contains c2 cs   ) m;;                        
let _ = Check.Verbose prop1;;
\ett{...} 
\ett{9:}
\ett{[(A, B); (D, B); (D, A)]}
\ett{...}
\ett{Ok, passed 100 tests.}                                                  	
\end{alltt}
\pause
\ \hfill {Properties should be {\redbrown monomorphic}}

\end{frame}








\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown filter}}


{\redbrown Set comprehension: \blue ${\{ x \in xs: p(x) \}}$}

\pause
\bigskip

{\blue $\mathtt{filter}\;p\;\mathit{xs}$} is the list of those
elements {\blue $x$} of {\blue \textit{xs}} where {\redbrown $p(x)
= \mathtt{true}$}.

\bigskip
\pause

{\redbrown Declaration}\hfill {\darkgreen Library function}
\begin{alltt}
let rec filter p = 
  function
  | []    -> []
  | x::xs -> if p x then x :: filter p xs
             else filter p xs;;
\ett{val filter : ('a -> bool) -> 'a list -> 'a list}
\end{alltt}

\bigskip
\pause

{\redbrown Example}
\begin{alltt}
filter System.Char.IsLetter ['1'; 'p'; 'F'; '-'];;
\ett{val it : char list = ['p'; 'F']}
\end{alltt}

\bigskip

where
 \verb-System.Char.IsLetter- $c$ is true
iff $c \in \{\mathtt{'A'}, \ldots, \mathtt{'Z'} \} \cup \{
\mathtt{'a'}, \ldots, \mathtt{'z'} \}$


\end{frame}


\begin{frame}{Exercise}

Declare a function
\[
{\blue \mathtt{inter}\ \mathit{xs}\ \mathit{ys}}
\]
which contains the common elements of the lists {\blue
$\mathit{xs}$} and {\blue $\mathit{ys}$}  --- i.e.\ their
intersection.

\bigskip

Order and repetition of elements are of no concern 

\bigskip

\bigskip

Remember:\\
{\blue $\mathtt{filter}\;p\;\mathit{xs}$} is the list of
those elements {\blue $x$} of {\blue \textit{xs}} where {\redbrown
$p(x) = \mathtt{true}$}.
where
\begin{alltt}\blue
filter: ('a -> bool) -> 'a list -> 'a list
\end{alltt}

\end{frame}

\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown tryFind}}

\[
{\blue \mathtt{tryFind}\;p\;\mathit{xs}} = \left\{ \begin{array}{lcl}
{\blue \mathtt{Some}\;x} & & \text{for an element $\blue x$ of \textit{\blue xs} with $\blue p(x) =
  \mathrm{true}$}\\
  {\blue \mathtt{None}} & & \text{if no such element exists}
  \end{array} \right.
\]

\bigskip
\pause

\begin{alltt}
let rec tryFind p = 
  function
  | x::xs when p x -> Some x
  | _::xs          -> tryFind p xs
  | _              -> None;;
\ett{val tryFind : ('a -> bool) -> 'a list -> 'a option}
\pause

tryFind (fun x -> x>3) [1;5;-2;8];;
\ett{val it : int option = Some 5}
\end{alltt}
\end{frame}


\begin{frame}[fragile]\frametitle{Folding a function over a list (I)}

Example: sum of absolute values: 

\begin{alltt}\blue
let rec absSum = function
                 | []    -> 0
                 | x::xs -> abs x + absSum xs;;
\ett{val absSum : int list -> int}

absSum [-2; 2; -1; 1; 0];;
\ett{val it : int = 6}
\end{alltt}



\end{frame}

\begin{frame}[fragile]\frametitle{Folding a function over a list (II)}

\begin{alltt}
\blue
let rec absSum = function
                 | []    -> 0
                 | x::xs -> abs x + absSum xs;;
\end{alltt}

Let $\blue f\ x\ a$ abbreviate $\blue \mathtt{abs}\ x + a$ in the evaluation:

\[\begin{array}{cl}
       & \mathtt{absSum}\ [x_0; x_1; \ldots; x_{n-1}]\\
\lto   & \mathtt{abs}\ x_0 + (\mathtt{absSum}\ [x_1; \ldots; x_{n-1}]) \\
=      & f\ x_0\ (\mathtt{absSum}\ [x_1; \ldots; x_{n-1}])\\
\lto   & f\ x_0\ (f\ x_1\ (\mathtt{absSum} [x_2; \ldots; x_{n-1}]))\\
\vdots & \\
\lto   & {\darkgreen f}\ x_0\ ({\darkgreen f}\ x_1\ ( \cdots ({\darkgreen f}\ x_{n-1}\ 0) \cdots ))
\end{array}
\]

\pause

This repeated application of $\darkgreen f$ is also called a {\redbrown folding} of $\darkgreen f$.

\pause
\medskip

\begin{center}\redbrown
Many functions follow such recursion and evaluation schemes
\end{center}

\end{frame}


\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown foldBack} (1)}

Suppose that  $\blue \otimes$ is an infix function. Then

\bigskip

{\blue
\begin{tabular}{lcl}
\multicolumn{3}{l}
 {\tt foldBack ($\otimes$) [$a_0$; $a_1$; $\ldots$ ; $a_{n-2}$; $a_{n-1}$] $e_b$}
\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & = & $  a_{0} \otimes ( a_{1} \otimes (  \ldots ( a_{n-2} \otimes ( a_{n-1} \otimes e_b )) \ldots ))$
\end{tabular}
}

\bigskip
\pause

\[\blue
\begin{array}{rclcc}
\verb!List.foldBack (+) [1; 2; 3] 0! & = & 1 + (2+(3+0))  & = & 6\\
\verb!List.foldBack (-) [1; 2; 3] 0! & = & 1 - (2-(3-0)) & = & 2
\end{array}
\]



\end{frame}



\begin{frame}[fragile]\frametitle{Declaration of {\Large\tt\redbrown foldBack}}

\begin{alltt}\blue
let rec foldBack f xlst e =
  match xlst with
  | x::xs -> f x (foldBack f xs e)
  | []    -> e;;
\ett{val foldBack : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b}
\end{alltt}

\pause
\bigskip

\begin{verbatim}
let absSum xs = foldBack (fun x a -> abs x + a)  xs 0;;

let length xs = foldBack (fun _ n -> n+1) xs 0;;

let map f xs = foldBack (fun x rs -> f x :: rs) xs [];;

\end{verbatim}

\end{frame}


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

Let an insertion function be declared by

{\blue
\begin{alltt}
let insert x ys = if List.contains x ys then ys 
                  else x::ys;;
\end{alltt}
}

\bigskip

Declare a function $\blue \verb|distinct|\ xs$, that returns a list having same elements as $\blue xs$ but without duplicated element. 

\bigskip

\bigskip

Remember:
\[
{\blue \verb?foldBack?\ (\oplus)\,
\mathtt{[}x_1\mathtt{;} x_2\mathtt{;} \ldots\mathtt{;}
x_n\mathtt{]}\ b\ \lto\
 x_1 \oplus (x_2 \oplus \cdots \oplus (x_n \oplus
       b) \cdots )}
\]
where
\begin{alltt}\blue
foldBack: ('a -> 'state -> 'state) 
             -> 'a list -> 'state -> 'state
\end{alltt}

\end{frame}


\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown fold} (1)}

Suppose that $\oplus$ is an infix function.

\medskip

Then the {\redbrown\tt fold} function is defined by:

\medskip

{\blue
\begin{tabular}{lcl}
\multicolumn{3}{l}
 {\tt fold ($\oplus$) $e_a$ [$b_0$; $b_1$; $\ldots$ ; $b_{n-2}$; $b_{n-1}$ ]}
\\
 & = & $ (( \ldots (( e_a \oplus b_0) \oplus b_1 ) \ldots ) \oplus b_{n-2} ) \oplus b_{n-1} $
\end{tabular}
}

\medskip

i.e. it applies $\blue \oplus$ from left to right.

\bigskip
\pause
Examples:
\[\blue
\begin{array}{rcccc}
\verb!List.fold (-) 0 [1; 2; 3]!     & = & ((0-1) -2)-3 & = & -6\\
\pause[3]
\verb!List.foldBack (-) [1; 2; 3] 0! & \pause[3] = & \pause[3] 1 -(2-(3-0)) & \pause[3] = & \pause[3] 2
\end{array}
\]




\end{frame}

\begin{frame}[fragile]\frametitle{Higher-order list functions: {\Large\tt\redbrown fold} (2)}

\begin{alltt}\blue
let rec fold f e = 
  function
  | x::xs -> fold f (f e x) xs
  | []    -> e;;
\ett{val fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a}
\end{alltt}

\bigskip
\pause

Using cons in connection with {\blue fold} gives the reverse function:

\begin{alltt}
let rev xs  = fold (fun rs x -> x::rs) [] xs;;
\end{alltt}

This function has a linear execution time:
\pause
\medskip

{\blue
\begin{tabular}{lllll}
       &  \multicolumn{3}{l}{\tt rev [1;2;3]}    \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & {\redbrown []} & {\tt [1;2;3]} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & ({\redbrown 1::[]}) & {\tt [2;3]} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & {\redbrown [1]}  &{\tt [2;3]} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & ({\redbrown 2::[1]}) & {\tt [3]} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & {\redbrown [2\,;\,1]} & {\tt [3]} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & ({\redbrown 3::[2\,;\,1]}) & {\tt []} \\
$\lto$ & {\tt fold} & {\tt (fun ...)} & {\redbrown [3\,;\,2\,;\,1]} & {\tt []} \\
$\lto$ & [3;2;1]
\end{tabular}
}
\end{frame}


\begin{frame}[fragile]\frametitle{Summary}
	
	Part I: Disjoint union (Algebraic data types) \\
\qquad 	-- types containing different kinds of values
	
	\medskip\pause
	We will later extend the notion with recursive definitions\\
	\qquad -- provides a mean to declare types for finite trees
	
	\bigskip
	\pause
	
	
	Part II: Higher-order list functions
	
	\begin{itemize}
		\item Many recursive declarations follows the same schema.
	\end{itemize}
	
	
	
	\begin{center}\redbrown
		Succinct declarations achievable using higher-order functions
	\end{center}
	
%	Contents
\medskip \pause	
	\begin{itemize}
		
		\item Higher-order list functions (in the library)
		\begin{itemize}
			\item map \item contains, exists, forall, filter, tryFind  \item foldBack, fold
		\end{itemize}
	\end{itemize}
	
	\pause
	\bigskip
	
	\begin{center}\blue
		Avoid (almost) identical code fragments by\\
		\redbrown parameterizing functions with functions
	\end{center}
\end{frame}


\begin{frame}
	\begin{center}\Large\darkgreen
		On the design of types for functions --- briefly
	\end{center}
\end{frame}

\begin{frame}{Design of (Higher-order) functions}
Some consideration
\begin{itemize}
\item Is partial function application envisioned?
\item Conventions
\item Make functions fit together
\item ``nice'' declaration	
\item ``safe parentheses''
\item ...
\end{itemize}	
\end{frame}

\begin{frame}[fragile]{Design of (Higher-order) functions}
	
	Suppose a function can take two arguments. Possible types:
	\[\blue 
	\begin{array}{l}
		\tau_1 * \tau_2 \to \tau\\
		\tau_1 \to \tau_2 \to \tau\\
		\tau_2 * \tau_1 \to \tau\\
		\tau_2 \to \tau_1 \to \tau		 		
	\end{array}
	\]
	The number of possibilities becomes huge when there are more types and when types have a structure. 
	
	\bigskip
	\pause 
	Types of some library functions folding from right:
	\begin{itemize}
		\item $\mathtt{('a\ \to\ 'b\ \to\ 'b) \to\ 'a\ list \to\ 'b\ \to\ 'b)}$ \hfill {\darkgreen  OCAML: fold\_right}
		\item $\mathtt{('a\ \to\ 'b\ \to\ 'b) \to\ 'b\ \to\ 'a\ list\ \to\ 'b)}$ \hfill {\darkgreen  Haskell: foldr}
		\item $\mathtt{('a\ *\ 'b\ \to\ 'b) \to\ 'b\ \to\ 'a\ list\ \to\ 'b)}$ \hfill {\darkgreen  SML: foldr}
		\item {\redbrown $\cdots$}
	\end{itemize}
	
	\pause
	\bigskip
	It does not may sense to discuss what is best
	
	\pause
	\bigskip
	An observation about {\blue foldBack} ({\darkgreen F\# and OCAML}): 
	\[\blue 
	\begin{array}{ll}
		& \mathtt{foldBack}\ (\oplus)\ [x_1; \ldots; x_n]\ e\\ 	
		\leadsto & \qquad \qquad  \qquad \quad \ x_1 \oplus (\cdots (x_n \oplus e) \cdots ) 	
	\end{array}	
	\]
	insert $\blue \oplus$ between ``all arguments'' and evaluate from right
	
\end{frame}



\begin{frame}[fragile]{Piecewise linear curve with Bounding Box}

\begin{alltt}\blue
type Point       = float * float
type Curve       = Point * Point list // (p0,[p1;..;pn])
type BoundingBox = Point * Point      // ((x0,y0),(xm,ym))

extBB:{\redbrown ?}             // extend a bounding box by a point
findBB: Curve -> BoundingBox
\end{alltt}

\vspace*{-1mm}
\includegraphics[scale=0.3]{curve2.png}

%\pause
%lternative type for {\blue Curve}?

\end{frame}

\begin{frame}[fragile]{Computing bounding box}
Could be done by repeated extension of a bounding box by a point. 

Example: Extending 
\begin{itemize}
\item bounding box ((1,1.5), (3,2))
\item with the point (4,4)	
\end{itemize}
gives the bounding box ((1,1.5), (4,4)) 

\pause 
\bigskip
Possible (natural) types:
\begin{alltt}\blue
extBB1: Point -> BoundingBox -> BoundingBox
extBB2: Point * BoundingBox  -> BoundingBox	
extBB3: BoundingBox -> Point -> BoundingBox
extBB4: BoundingBox * Point  -> BoundingBox	
\end{alltt}

\pause 
\bigskip

Which one should be chosen?

\pause 
\bigskip

\begin{itemize}
\item if {\blue findBB} is declared using recursion,\\
it is hard to have a preference 
\end{itemize}

\end{frame}

\begin{frame}[fragile]{Declare {\blue findBB} using higher-order functions (I)}
The type of {\blue List.fold}
\begin{alltt}\blue
fold: ('bb -> 'p -> 'bb) -> 'bb -> 'p list -> 'bb)
\end{alltt}

Remember
\begin{alltt}\blue
extBB1: Point -> BoundingBox -> BoundingBox
extBB2: Point * BoundingBox  -> BoundingBox	
extBB3: BoundingBox -> Point -> BoundingBox
extBB4: BoundingBox * Point  -> BoundingBox	
\end{alltt}

\pause
\bigskip
Four versions using {\blue fold}:
\begin{alltt}\blue
let findBB1(p0,ps) = 
   fold (fun bb p -> extBB1 p bb) (p0,p0) ps \pause
   
let findBB2(p0,ps) = 
   fold (fun bb p -> extBB2(p,bb)) (p0,p0) ps   \pause
{\darkgreen
let findBB3(p0,ps) = fold extBB3 (p0,p0) ps}   \pause

let findBB4(p0,ps) = 
   fold (fun bb p -> extBB4(bb,p)) (p0,p0) ps
\end{alltt}

\end{frame}

\begin{frame}[fragile]{Declare {\blue findBB} using higher-order functions (II)}
The type of {\blue List.foldBack} 
\begin{alltt}\blue
foldBack: ('p -> 'bb -> 'bb) -> 'p list -> 'bb -> 'bb
\end{alltt}
	
Remember
\begin{alltt}\blue
extBB1: Point -> BoundingBox -> BoundingBox
extBB2: Point * BoundingBox  -> BoundingBox	
extBB3: BoundingBox -> Point -> BoundingBox
extBB4: BoundingBox * Point  -> BoundingBox	
\end{alltt}
	
\pause
\bigskip
Just one version fits {\blue foldBack}:
\begin{alltt}\darkgreen
let findBB'(p0,ps) = foldBack extBB1 ps (p0,p0)
\end{alltt}
	
	
	
\end{frame}


\begin{frame}
Design functions so that they {\darkgreen compose} nicely\\ \pause
\ \hfill {\redbrown whatever this means} 


\pause 
\bigskip
\begin{itemize}
\item {\blue extBB1} fits nicely with {\blue foldBack}
\item {\blue extBB3} fits nicely with {\blue fold}
\end{itemize}

\pause
\bigskip

What about functions to move and join curves?

\bigskip
Let us have a look at some programs

\pause
\bigskip
Alternative type for {\blue Curve}?


\end{frame}


\end{document}


