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

\input{../Common/common}



\title % (optional, use only with long paper titles)
{02157 Functional Programming}

\subtitle
{Finite Trees (I)} % (optional)
\date {MRH 31/10/2024}% (optional)



\begin{document}

\begin{frame}
  \titlepage


\end{frame}




\begin{frame}
\begin{itemize}


\item Finite trees


\bigskip


\item Functional, Structural and Property tests\\ 
by example \hfill {\blue using xUnit}\\

\end{itemize}

\end{frame}






\begin{frame}
\begin{center}\darkgreen\Large Finite trees
\end{center}

\pause
\bigskip

\begin{itemize}
	\item<2-> {\redbrown recursive} declarations of algebraic types
	
	\item<2-> {\redbrown meaning} of type declarations: rules generating values
	
	\item<3-> typical recursions following the structure of trees
	
	\item<4-> trees with a {\redbrown fixed branching structure}
	
	\item<5-> trees with a {\redbrown variable number of sub-trees}   
	
	\item<6-> illustrative examples 
\end{itemize}

\bigskip
\pause[7]

{\redbrown Mutually recursive} type and function declarations 


\end{frame}




\begin{frame}[fragile]\frametitle{Finite trees}

A {\em\blue finite
  tree\/} is a value containing sub-components of the {\darkgreen same
type}

\bigskip
\pause
Example: A {\redbrown\em binary tree}

\medskip

\begin{center}
\setlength{\unitlength}{2500sp}%
%\setlength{\unitlength}{3947sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(7287,2835)(1126,-2761)
\thinlines \put(4801,-61){\line( 0,-1){675}}
%\put(4801,-61){\line( 5,-2){1810.345}}
\put(4801,-61){\line( 5,-2){1700.000}}
%\put(4801,-61){\makebox(1.6667,11.6667){\SetFigFont{5}{6}{\rmdefault}{\mddefault}{\updefault}.}}
%\put(4801,-61){\line(-5,-2){1810.345}}
\put(4801,-61){\line(-5,-2){1700.000}}

%\put(3001,-961){\line( 0,-1){750}}
\put(3001,-961){\line( 0,-1){710}}

%\put(3001,-961){\line(-5,-3){1213.235}}
\put(3001,-961){\line(-5,-3){1100.000}}

%\put(3001,-961){\line( 5,-3){1213.235}}
\put(3001,-961){\line( 5,-3){1100.000}}



\put(1801,-1861){\line(-4,-5){600}} \put(1801,-1936){\line(
0,-1){600}} \put(1801,-1861){\line( 4,-5){600}}

%\put(6601,-961){\line(-5,-3){1180.147}}
\put(6601,-961){\line(-5,-3){1100.000}}

\put(6601,-961){\line( 0,-1){675}}

%\put(6601,-961){\line( 5,-3){1213.235}}
\put(6601,-961){\line( 5,-3){1100.000}}

\put(5401,-1861){\line(-5,-6){577.869}} \put(5401,-1861){\line(
0,-1){675}} \put(5401,-1861){\line( 4,-5){600}}
\put(7801,-1861){\line(-5,-6){577.869}} \put(7801,-1861){\line(
0,-1){750}} \put(7801,-1861){\line( 4,-5){600}}

\put(4650,-35){\makebox(0,0)[lb]{{\tt Br}}}

%\put(2926,-961){\makebox(0,0)[lb]{Br}}
%\put(6526,-961){\makebox(0,0)[lb]{Br}}
\put(2926,-930){\makebox(0,0)[lb]{{\tt Br}}}
\put(6526,-930){\makebox(0,0)[lb]{{\tt Br}}}

\put(1726,-1800){\makebox(0,0)[lb]{{\tt Br}}}
\put(4126,-1800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(5326,-1800){\makebox(0,0)[lb]{{\tt Br}}}
\put(7726,-1800){\makebox(0,0)[lb]{{\tt Br}}}

%
\put(1126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(1726,-2800){\makebox(0,0)[lb]{2}}
\put(2326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}

\put(2926,-1861){\makebox(0,0)[lb]{7}}

\put(4726,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(5251,-2800){\makebox(0,0)[lb]{13}}
\put(5926,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(7126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(7651,-2800){\makebox(0,0)[lb]{25}}
\put(8326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}

\put(6466,-1861){\makebox(0,0)[lb]{21}}
\put(4726,-961){\makebox(0,0)[lb]{9}}

%\put(4726,-61){\makebox(0,0)[lb]{ \smash{\SetFigFont{10}{14.4}{rm}Br}}}
%\put(2926,-961){\makebox(0,0)[lb]{Br}}
%\put(6526,-961){\makebox(0,0)[lb]{Br}}
%\put(1726,-1861){\makebox(0,0)[lb]{Br}}
%\put(4126,-1861){\makebox(0,0)[lb]{Lf}}
%\put(5326,-1861){\makebox(0,0)[lb]{Br}}
%\put(7726,-1861){\makebox(0,0)[lb]{Br}}
%\put(1126,-2761){\makebox(0,0)[lb]{Lf}}
%\put(1726,-2761){\makebox(0,0)[lb]{2}}
%\put(2326,-2761){\makebox(0,0)[lb]{Lf}}
%\put(2926,-1861){\makebox(0,0)[lb]{7}}
%\put(4726,-2761){\makebox(0,0)[lb]{Lf}}
%\put(5251,-2761){\makebox(0,0)[lb]{13}}
%\put(5926,-2761){\makebox(0,0)[lb]{Lf}}
%\put(7126,-2761){\makebox(0,0)[lb]{Lf}}
%\put(7651,-2761){\makebox(0,0)[lb]{25}}
%\put(8326,-2761){\makebox(0,0)[lb]{Lf}}
%\put(6526,-1861){\makebox(0,0)[lb]{21}}
%\put(4726,-961){\makebox(0,0)[lb]{9}}
\end{picture}

\end{center}

\bigskip
\pause

A tree is a connected, acyclic, undirected graph, where
\begin{itemize}

\item the top node (carrying value 9) is called the {\redbrown root}

\item a {\redbrown branch node} has two {\redbrown children} \hfill constructor {\blue Br}

\item a node without children is called a {\redbrown leaf} \hfill constructor {\blue Lf}

\end{itemize}





%{\redbrown Condition:} for every node containing the value $x$:
%every value in the left subtree is smaller then $x$, and every
%value in the right subtree is greater than $x$.

\end{frame}



\begin{frame}[fragile]\frametitle{Example: Binary Trees}

A {\em\blue recursive datatype} is used to represent values that
are trees.

\medskip

\begin{alltt}
type{\blue Tree} = | Lf
            | Br of{\blue Tree}*int*\blue{Tree};;
\end{alltt}

\medskip
\pause

The declaration provides {\redbrown rules} for generating trees:
\begin{enumerate}
\item \mbox{}{\tt\blue Lf} is a tree \item if $\blue t_1, t_2$ are
trees and $\blue n$ is an integer, then ${\blue {\tt Br}(t_1, n,
t_2)}$ is a tree.
\item the type {\blue Tree} contains no other values than those generated by repeated use of Rules 1. and 2.
\end{enumerate}
\medskip



\bigskip
\pause
The tags {\redbrown Lf} and {\redbrown Br} are called {\darkgreen constructors}:
\[\blue
\begin{array}{lcl}
\mathtt{\redbrown Lf} & : &  \mathtt{Tree}\\
\mathtt{\redbrown Br} & : &  \mathtt{Tree*int*Tree} \to \mathtt{Tree}
\end{array}
\] 



%The tree from the previous slide is denoted by:
%\begin{alltt}
%Br(Br(Br(Lf,2,Lf),7,Lf),
%   9,
%   Br(Br(Lf,13,Lf),21,Br(Lf,25,Lf)))
%\end{alltt}

\end{frame}

\begin{frame}[fragile]\frametitle{Example: Binary Trees}

\begin{center}
\setlength{\unitlength}{2500sp}%
%\setlength{\unitlength}{3947sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(7287,2835)(1126,-2761)
\thinlines \put(4801,-61){\line( 0,-1){675}}
%\put(4801,-61){\line( 5,-2){1810.345}}
\put(4801,-61){\line( 5,-2){1700.000}}
%\put(4801,-61){\makebox(1.6667,11.6667){\SetFigFont{5}{6}{\rmdefault}{\mddefault}{\updefault}.}}
%\put(4801,-61){\line(-5,-2){1810.345}}
\put(4801,-61){\line(-5,-2){1700.000}}

%\put(3001,-961){\line( 0,-1){750}}
\put(3001,-961){\line( 0,-1){710}}

%\put(3001,-961){\line(-5,-3){1213.235}}
\put(3001,-961){\line(-5,-3){1100.000}}

%\put(3001,-961){\line( 5,-3){1213.235}}
\put(3001,-961){\line( 5,-3){1100.000}}



\put(1801,-1861){\line(-4,-5){600}} \put(1801,-1936){\line(
0,-1){600}} \put(1801,-1861){\line( 4,-5){600}}

%\put(6601,-961){\line(-5,-3){1180.147}}
\put(6601,-961){\line(-5,-3){1100.000}}

\put(6601,-961){\line( 0,-1){675}}

%\put(6601,-961){\line( 5,-3){1213.235}}
\put(6601,-961){\line( 5,-3){1100.000}}

\put(5401,-1861){\line(-5,-6){577.869}} \put(5401,-1861){\line(
0,-1){675}} \put(5401,-1861){\line( 4,-5){600}}
\put(7801,-1861){\line(-5,-6){577.869}} \put(7801,-1861){\line(
0,-1){750}} \put(7801,-1861){\line( 4,-5){600}}

\put(4650,-35){\makebox(0,0)[lb]{{\tt Br}}}

%\put(2926,-961){\makebox(0,0)[lb]{Br}}
%\put(6526,-961){\makebox(0,0)[lb]{Br}}
\put(2926,-930){\makebox(0,0)[lb]{{\tt Br}}}
\put(6526,-930){\makebox(0,0)[lb]{{\tt Br}}}

\put(1726,-1800){\makebox(0,0)[lb]{{\tt Br}}}
\put(4126,-1800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(5326,-1800){\makebox(0,0)[lb]{{\tt Br}}}
\put(7726,-1800){\makebox(0,0)[lb]{{\tt Br}}}

%
\put(1126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(1726,-2800){\makebox(0,0)[lb]{2}}
\put(2326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}

\put(2926,-1861){\makebox(0,0)[lb]{7}}

\put(4726,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(5251,-2800){\makebox(0,0)[lb]{13}}
\put(5926,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(7126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
\put(7651,-2800){\makebox(0,0)[lb]{25}}
\put(8326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}

\put(6466,-1861){\makebox(0,0)[lb]{21}}
\put(4726,-961){\makebox(0,0)[lb]{9}}


\end{picture}

\end{center}

\bigskip

Corresponding F\#-value:
\begin{alltt}
Br(Br(Br(Lf,2,Lf),7,Lf),
   9,
   Br(Br(Lf,13,Lf),21,Br(Lf,25,Lf)))
\end{alltt}

\end{frame}

\begin{frame}[fragile]\frametitle{Traversals of binary trees}

\begin{itemize}
	\item Pre-order traversal:
	First visit the root node, then traverse the
	left sub-tree in pre-order and finally traverse the right sub-tree in pre-order.
	\bigskip
	
	\item {\darkgreen In-order traversal}: First traverse the left sub-tree in in-order, then visit
	the root node and finally traverse the right sub-tree in in-order.
	\bigskip
	
	\item Post-order traversal: First traverse the left sub-tree in post-order, then
	traverse the right sub-tree in post-order and finally visit the root node.
\end{itemize}

\medskip
\pause

{\darkgreen In-order traversal}
\begin{alltt}\blue
let rec inOrder = 
   function
   | Lf          -> []
   | Br(t1,j,t2) -> inOrder t1 @ [j] @ inOrder t2;;
\ett{val toList : Tree -> int list}

inOrder(Br(Br(Lf,1,Lf), 3, Br(Br(Lf,4,Lf), 5, Lf)));;
\ett{val it : int list = [1; 3; 4; 5]}
\end{alltt}
\end{frame}


\begin{frame}[fragile]\frametitle{Binary search tree}


{\redbrown Condition:} for every node containing the value $x$:
every value in the left subtree is smaller then $x$, and every
value in the right subtree is greater than $x$.


\bigskip

Example: A {\redbrown\em binary search tree}

\medskip

\begin{center}
	\setlength{\unitlength}{2500sp}%
	%\setlength{\unitlength}{3947sp}%
	%
	\begingroup\makeatletter\ifx\SetFigFont\undefined%
	\gdef\SetFigFont#1#2#3#4#5{%
		\reset@font\fontsize{#1}{#2pt}%
		\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
		\selectfont}%
	\fi\endgroup%
	\begin{picture}(7287,2835)(1126,-2761)
	\thinlines \put(4801,-61){\line( 0,-1){675}}
	%\put(4801,-61){\line( 5,-2){1810.345}}
	\put(4801,-61){\line( 5,-2){1700.000}}
	%\put(4801,-61){\makebox(1.6667,11.6667){\SetFigFont{5}{6}{\rmdefault}{\mddefault}{\updefault}.}}
	%\put(4801,-61){\line(-5,-2){1810.345}}
	\put(4801,-61){\line(-5,-2){1700.000}}
	
	%\put(3001,-961){\line( 0,-1){750}}
	\put(3001,-961){\line( 0,-1){710}}
	
	%\put(3001,-961){\line(-5,-3){1213.235}}
	\put(3001,-961){\line(-5,-3){1100.000}}
	
	%\put(3001,-961){\line( 5,-3){1213.235}}
	\put(3001,-961){\line( 5,-3){1100.000}}
	
	
	
	\put(1801,-1861){\line(-4,-5){600}} \put(1801,-1936){\line(
		0,-1){600}} \put(1801,-1861){\line( 4,-5){600}}
	
	%\put(6601,-961){\line(-5,-3){1180.147}}
	\put(6601,-961){\line(-5,-3){1100.000}}
	
	\put(6601,-961){\line( 0,-1){675}}
	
	%\put(6601,-961){\line( 5,-3){1213.235}}
	\put(6601,-961){\line( 5,-3){1100.000}}
	
	\put(5401,-1861){\line(-5,-6){577.869}} \put(5401,-1861){\line(
		0,-1){675}} \put(5401,-1861){\line( 4,-5){600}}
	\put(7801,-1861){\line(-5,-6){577.869}} \put(7801,-1861){\line(
		0,-1){750}} \put(7801,-1861){\line( 4,-5){600}}
	
	\put(4650,-35){\makebox(0,0)[lb]{{\tt Br}}}
	
	%\put(2926,-961){\makebox(0,0)[lb]{Br}}
	%\put(6526,-961){\makebox(0,0)[lb]{Br}}
	\put(2926,-930){\makebox(0,0)[lb]{{\tt Br}}}
	\put(6526,-930){\makebox(0,0)[lb]{{\tt Br}}}
	
	\put(1726,-1800){\makebox(0,0)[lb]{{\tt Br}}}
	\put(4126,-1800){\makebox(0,0)[lb]{{\tt Lf}}}
	\put(5326,-1800){\makebox(0,0)[lb]{{\tt Br}}}
	\put(7726,-1800){\makebox(0,0)[lb]{{\tt Br}}}
	
	%
	\put(1126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	\put(1726,-2800){\makebox(0,0)[lb]{2}}
	\put(2326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	
	\put(2926,-1861){\makebox(0,0)[lb]{7}}
	
	\put(4726,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	\put(5251,-2800){\makebox(0,0)[lb]{13}}
	\put(5926,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	\put(7126,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	\put(7651,-2800){\makebox(0,0)[lb]{25}}
	\put(8326,-2800){\makebox(0,0)[lb]{{\tt Lf}}}
	
	\put(6466,-1861){\makebox(0,0)[lb]{21}}
	\put(4726,-961){\makebox(0,0)[lb]{9}}
	

	\end{picture}
	
\end{center}



\end{frame}







\begin{frame}[fragile]\frametitle{Binary search trees: Insertion}


\begin{itemize}
\item Recursion following the structure of trees

\item<2-> Constructors {\normalsize\blue\tt Lf} and
{\normalsize\blue\tt Br} are used in {\redbrown patterns} to decompose a tree into its parts

\item<3-> Constructors {\normalsize\blue\tt Lf} and
{\normalsize\blue\tt Br} are used in {\redbrown expressions} to construct a tree from its parts


\item<4-> The search tree condition is an {\redbrown invariant} for
\texttt{\blue \normalsize insert}

\end{itemize}

\pause[5]
\medskip

\begin{alltt}\blue
let rec insert i = 
   function
   | Lf                ->  Br(Lf,i,Lf)
   |{\darkgreen Br(t1,j,t2) as tr} -> //{\darkgreen Layered pattern}
         match compare i j with
         | 0           -> tr
         | n when n<0  -> Br(insert i t1 , j, t2)
         | _           -> Br(t1,j, insert i t2);;
\ett{val insert : int -> Tree -> Tree}
\end{alltt}

\pause[6]

Example:
\begin{alltt}\blue
let t1 = Br(Lf, 3, Br(Lf, 5, Lf));;
let t2 = insert 4 t1;;
\ett{val t2 : Tree = Br (Lf,3,Br (Br (Lf,4,Lf),5,Lf))}
\end{alltt}

\end{frame}



\begin{frame}[fragile]\frametitle{Binary search trees: {\Large\tt\redbrown contains}}


\begin{alltt}\blue 
let rec contains  i = 
   function
   | Lf                  -> false
   | Br(_,j,_)  when i=j -> true
   | Br(t1,j,_) when i<j -> contains i t1
   | Br(_,j,t2)          -> contains i t2;;
\ett{val contains : int -> Tree -> bool}

let t = Br(Br(Br(Lf,2,Lf),7,Lf), 
           9, 
           Br(Br(Lf,13,Lf),21,Br(Lf,25,Lf)));;

contains 21 t;;
\ett{val it : bool = true}

contains 4 t;;
\ett{val it : bool = false}


\end{alltt}


\end{frame}



\begin{frame}[fragile]\frametitle{Parameterize type declarations}

The programs on search trees require only an ordering on elements -- they no not need to be integers.

\bigskip
\pause

A polymorphic tree type is declared as follows:
\begin{alltt}\blue
type Tree{\redbrown{<'a>}} = | Lf | Br of Tree{\redbrown{<'a>}} * 'a * Tree{\redbrown{<'a>}};;
\end{alltt}

\medskip
\pause

Program text is unchanged (though {\redbrown polymorphic} now), for example
\begin{alltt}
let rec insert i = function
       ....
  | Br(t1,j,t2) as tr -> match{\redbrown compare} i j with
       .... ;;
\ett{val insert: 'a -> Tree<'a> -> Tree<'a> when{\redbrown 'a: comparison}}
\pause
let ti = insert 4  (Br(Lf, 3, Br(Lf, 5, Lf)));;
\ett{val ti : Tree<int> = Br (Lf,3,Br (Br (Lf,4,Lf),5,Lf))}
\pause
let ts = insert "4" (Br(Lf, "3", Br(Lf, "5", Lf)));;
\ett{val ts : Tree<string>}
\ett{       = Br (Lf,"3",Br (Br (Lf,"4",Lf),"5",Lf))}
\end{alltt}

\end{frame}



\begin{frame}{So far}
\begin{itemize}
\item Declaration of a recursive algebraic data type, that is, a type for a finite tree

\medskip 

\item Meaning of the type declaration:
\begin{itemize}
\item rules for generating values
\end{itemize}

\medskip 
 
\item Archetypical functions on trees:
\begin{itemize}
	\item gathering information from a tree \hfill Example:  {\blue inOrder}
	\item inspecting a tree \hfill Example:  {\blue contains}
	\item construction of a new tree \hfill Example:  {\blue insert}
\end{itemize}  
\end{itemize}

\end{frame}

\begin{frame}{Manipulation of arithmetical expressions}

Consider $\blue f(x)$:  
\[\blue  3 \cdot (x - 1) - 2\cdot x \]

\bigskip
\pause

We may be interested in 
\begin{itemize}
\item computation of values, e.g. $\blue f(2)$

\item differentiation, e.g. $\blue f'(x) = (3 \cdot 1 + 0 \cdot (x - 1)) - (2 \cdot 1 + 0 \cdot x)$

\item simplification of the expressions, e.g. $\blue f'(x) = 1$

\item ..... 

\end{itemize} 

\bigskip\pause

We would like a suitable representation of such arithmetical expressions that supports the above manipulations 

\pause
\bigskip
How would you visualize the expressions as a tree?
\begin{itemize}
\item root?
\item leaves?
\item branches?

\end{itemize}


\end{frame}



\begin{frame}[fragile]\frametitle{Example: Expression Trees}
{\blue
\begin{alltt}
type Fexpr =
  | Const of float
  | X
  | Add of Fexpr * Fexpr
  | Sub of Fexpr * Fexpr
  | Mul of Fexpr * Fexpr
  | Div of Fexpr * Fexpr;;
\end{alltt}}

\pause
\bigskip

Defines 6 {\redbrown constructors}:
\begin{itemize}
\item \verb!Const: float -> Fexpr!

\item \verb!X : Fexpr!

\item \verb!Add: Fexpr * Fexpr -> Fexpr!

\item \verb!Sub: Fexpr * Fexpr -> Fexpr!

\item \verb!Mul: Fexpr * Fexpr -> Fexpr!

\item \verb!Div: Fexpr * Fexpr -> Fexpr!
\end{itemize}


\pause
\bigskip

\begin{itemize}
	\item Can you write 3 values of type Fexpr?
    \item Drawings of trees?
\end{itemize}


\end{frame}


\begin{frame}[fragile]\frametitle{Expressions: Computation of values}
	
	Given a value (a float) for \texttt{X}, then every expression denote a float.
	
	\medskip
	
{\blue
\begin{alltt}
   compute : float -> Fexpr -> float
\end{alltt}
}
	\medskip
	\pause
	
{\blue
\begin{alltt}
   let rec compute x = 
      function
      | Const r       -> r
      | X             -> x
      | Add(fe1,fe2)  -> compute x fe1 + compute x fe2
      | Sub(fe1,fe2)  -> compute x fe1 - compute x fe2
      | Mul(fe1,fe2)  -> compute x fe1 * compute x fe2
      | Div(fe1,fe2)  -> compute x fe1 / compute x fe2;;		
\end{alltt}
	}
	\bigskip
	\pause
	
	Example:
	
	\begin{alltt}
		compute 4.0 (Mul(X, Add(Const 2.0, X)));;
		\ett{val it : float = 24.0}
	\end{alltt}
	
\end{frame}


\begin{frame}[fragile]
	\frametitle{Blackboard exercise: Substitution}
{\blue
\begin{alltt}
type Fexpr = | Const of float 
             | X
             | Add of Fexpr * Fexpr 
             | Sub of Fexpr * Fexpr 
             | Mul of Fexpr * Fexpr 
             | Div of Fexpr * Fexpr;;
\end{alltt}}

\medskip

Declare a function 
\begin{alltt}\blue 
	substX: Fexpr -> Fexpr -> Fexpr
\end{alltt}
so that $\blue \verb|substX|\, e'\, e$ is the expression obtained from $\blue e$ by substituting every occurrence of $\blue \verb|X|$ with $\blue e'$ 	

\medskip
\pause

For example:
{\blue
\begin{alltt}
let ex = Add(Sub(X, Const 2.0), Mul(Const 4.0, X));;

substX (Div(X,X)) ex;; 
\ett{val it : Fexpr =}
\ett{   Add(Sub(Div(X,X), Const 2.0), Mul(Const 4.0, Div(X,X)))}
\end{alltt}}



\end{frame}
	




\begin{frame}[fragile]\frametitle{Symbolic Differentiation\ \texttt{\redbrown D: Fexpr -> Fexpr}}

A classic example in functional programming:

{\blue
\begin{alltt}
let rec D = function
  | Const _      -> Const 0.0
  | X            -> Const 1.0
  | Add(fe1,fe2) -> Add(D fe1,D fe2)
  | Sub(fe1,fe2) -> Sub(D fe1,D fe2)
  | Mul(fe1,fe2) -> Add(Mul(D fe1,fe2),Mul(fe1,D fe2))
  | Div(fe1,fe2) -> Div(
                       Sub(Mul(D fe1,fe2),Mul(fe1,D fe2)),
                       Mul(fe2,fe2));;
\end{alltt}
}
Notice the direct correspondence with the rules of differentiation.

\bigskip
\pause

Can be tried out directly, as tree are "just" values, for example:
\begin{alltt}
D(Add(Mul(Const 3.0, X), Mul(X, X)));;
\ett{val it : Fexpr =}
\ett{  Add}
\ett{    (Add (Mul (Const 0.0,X),Mul (Const 3.0,Const 1.0)),}
\ett{     Add (Mul (Const 1.0,X),Mul (X,Const 1.0)))}
\end{alltt}
\end{frame}




\begin{frame}[fragile]\frametitle{Trees with a variable number of sub-trees} 

An archetypical declaration:

\begin{alltt}\blue
   type ListTree<'a> = Node of 'a * (ListTree<'a> list)
\end{alltt}

\begin{itemize}
\item \texttt{Node(}$x$\texttt{,[])} represents a leaf tree containing the value $x$
\item \texttt{Node(}$x$\texttt{,[}$t_0$\texttt{;}\ldots\texttt{;}$t_{n-1}$\texttt{])} 
	represents a tree with value $x$ in the root and with $n$ 
 sub-trees represented by the values $t_0, \ldots, t_{n-1}$
\end{itemize}

\bigskip
\pause

\begin{figure}[h]
	
	\setlength{\unitlength}{1mm}
	
	\begin{picture}(25,20)(0,0)
	
	\put(10,20){\makebox(0,0){\tt 1}}
	
	\put(08,18){\line(-1,-1){6}}
	\put(10,18){\line(0,-1){6}}
	\put(12,18){\line(1,-1){6}}
	
	\put(0,10){\makebox(0,0){\tt 2}}
	\put(0,8){\line(0,-1){6}}
	
	\put(10,10){\makebox(0,0){\tt 3}}
	
	\put(20,10){\makebox(0,0){\tt 4}}
	\put(19,8){\line(-1,-2){3}}
	\put(21,8){\line(1,-2){3}}
	
	\put(00,00){\makebox(0,0){\tt 5}}
	
	\put(15,00){\makebox(0,0){\tt 6}}
	
	\put(25,00){\makebox(0,0){\tt 7}}
	\end{picture}
%	
%	
%	\caption{Tree represented by the value {\tt t1}\label{ListTreeFig}}
\end{figure}


\medskip\noindent
\pause
It is represented by the value \texttt{t1} where
\begin{alltt}
	let t7 = Node(7,[]);;    let t6 = Node(6,[]);;
	let t5 = Node(5,[]);;    let t3 = Node(3,[]);;
	let t2 = Node(2,[t5]);;  let t4 = Node(4,[t6; t7]);;
	let t1 = Node(1,[t2; t3; t4]);;
\end{alltt}
\end{frame}


\begin{frame}[fragile]\frametitle{Depth-first traversal of a ListTree} 

\begin{figure}[h]
	
	\setlength{\unitlength}{1mm}
	
	\begin{picture}(25,20)(0,0)
	
	\put(10,20){\makebox(0,0){\tt 1}}
	
	\put(08,18){\line(-1,-1){6}}
	\put(10,18){\line(0,-1){6}}
	\put(12,18){\line(1,-1){6}}
	
	\put(0,10){\makebox(0,0){\tt 2}}
	\put(0,8){\line(0,-1){6}}
	
	\put(10,10){\makebox(0,0){\tt 3}}
	
	\put(20,10){\makebox(0,0){\tt 4}}
	\put(19,8){\line(-1,-2){3}}
	\put(21,8){\line(1,-2){3}}
	
	\put(00,00){\makebox(0,0){\tt 5}}
	
	\put(15,00){\makebox(0,0){\tt 6}}
	
	\put(25,00){\makebox(0,0){\tt 7}}
	\end{picture}
	%	
	%	
	%	\caption{Tree represented by the value {\tt t1}\label{ListTreeFig}}
\end{figure}

Corresponds to the following order of the elements: 1, 2, 5, 3, 4, 6, 7

\bigskip
\pause

Invent {\blue a more general function} traversing a list of List trees:
\begin{alltt}\blue
let rec depthFirstList = 
   function 
   | [] -> []
   | Node(n,{\redbrown{ts}})::trest -> n::depthFirstList({\redbrown{ts}} @ trest)
\ett{depthFirstList : ListTree<'a> list -> 'a list}

let depthFirst t = depthFirstList [t]
\ett{ depthFirst1 : t:ListTree<'a> -> 'a list} 

depthFirst t1;;
\ett{val it : int list = [1; 2; 5; 3; 4; 6; 7]}
\end{alltt}


\end{frame}



\begin{frame}[fragile]\frametitle{Mutual recursion. Example: File system}

\begin{center}
\setlength{\unitlength}{0.9mm}
%\setlength{\unitlength}{1mm}
\begin{picture}(60,70)
\put(30,65){\makebox(0,0){$d_1$}}

\put(30,60){\line(0,-1){10}}
\put(0,50){\line(1,0){60}}

\put(0,50){\line(0,-1){5}}
\put(60,50){\line(0,-1){5}}

\put(6,45){\makebox(0,0){$a_1$}}
\put(22,45){\makebox(0,0){$d_2$}}
\put(38,45){\makebox(0,0){$a_4$}}
\put(54,45){\makebox(0,0){$d_3$}}

\put(22,40){\line(0,-1){10}}
\put(54,40){\line(0,-1){10}}

\put(14,30){\line(1,0){16}}
\put(50,30){\line(1,0){8}}
\put(14,30){\line(0,-1){5}}
\put(30,30){\line(0,-1){5}}
\put(50,30){\line(0,-1){5}}
\put(58,30){\line(0,-1){5}}

\put(54,25){\makebox(0,0){$a_5$}}
\put(18,25){\makebox(0,0){$a_2$}}
\put(26,25){\makebox(0,0){$d_3$}}

\put(26,20){\line(0,-1){10}}
\put(22,10){\line(1,0){8}}
\put(22,10){\line(0,-1){5}}
\put(30,10){\line(0,-1){5}}
\put(26,5){\makebox(0,0){$a_3$}}
\end{picture}
\end{center}

\begin{itemize}
\item A {\darkgreen file system} is a list of {\redbrown elements}
\item an {\redbrown element} is a file or a directory, which is a named {\darkgreen file system}
\end{itemize}
\pause
\begin{center}\darkgreen We focus on structure now -- not on file content \end{center}
\end{frame}



\begin{frame}[fragile]\frametitle{Mutually recursive type declarations}

\begin{itemize} \item are combined using {\redbrown and}
\end{itemize}

\bigskip

\begin{alltt}
type FileSys = Element list
{\redbrown{and}} Element =
  | File of string
  | Dir of string * FileSys
\end{alltt}

\medskip
\pause


\begin{alltt}
let d1 =
  Dir("d1",[File "a1";
            Dir("d2", [File "a2";
                       Dir("d3", [File "a3"])]);
            File "a4";
            Dir("d3", [File "a5"])
           ])
\end{alltt}

\medskip
\pause

\begin{center}
\redbrown The type of d1 is ?
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{Mutually recursive function declarations}

\begin{itemize}
\item are combined using {\redbrown and}
\end{itemize}

\bigskip

Example: extract the names occurring in file systems and elements.

\begin{alltt}
let rec namesFileSys = 
  function
  | []    -> []
  | e::es -> (namesElement e) @ (namesFileSys es)
{\redbrown{and}} namesElement = 
  function
  | File s    -> [s]
  | Dir(s,fs) -> s :: (namesFileSys fs) ;;
\ett{val namesFileSys : Element list -> string list}
\ett{val namesElement : Element -> string list}
\end{alltt}

\medskip
\pause

\begin{alltt}
namesElement d1 ;;
\ett{val it : string list = ["d1"; "a1"; "d2"; "a2";}
\ett{                        "d3"; "a3"; "a4"; "d3"; "a5"]}
\end{alltt}


\end{frame}

\begin{frame}[fragile]
	\frametitle{Mini-project 2: A tiny coherent story}
	
\vspace*{-2mm}
	
Semantics of expressions
\begin{alltt}\blue
   type Exp = Add of Exp*Exp |{\redbrown X} | ...
   sem: Exp -> {\redbrown int} -> int	
\end{alltt}
	%where $\blue \verb|sem|\ e\ x$ gives the value of $\blue e$ with input $\blue x$
	
	\bigskip\pause
A stack machine
\begin{alltt}\blue
   type Instruction = ...
   exec: Instruction list -> int	
\end{alltt}
	%where $\blue \verb|exec|\ is$ gives the value obtained by execution of the instruction list $\blue is$
	
	\bigskip\pause
Compilation
\begin{alltt}\blue
   compile: Exp -> {\redbrown int} -> Instruction list	
  \end{alltt}
	%where $\blue \verb|compile|\ e$ gives function from input to an instruction list.
	
	
	\bigskip\pause
Compiler is correct if $\blue \verb|sem|\ e\ {\redbrown x} = \verb|exec|(\verb|compile|\ e\ {\redbrown x})$. 
	
	
	\bigskip\pause
Optimization: Reduction of expressions
\begin{alltt}\blue
   red: Exp -> Exp	
\end{alltt}
	preserving semantics:  $\blue \verb|sem|\ e\ {\redbrown x} = \verb|sem|(\verb|red|\ e)\ {\redbrown x}$.
	
	\bigskip\pause
A appetizer illustrating fundamental CS concepts 
\begin{itemize}
		\item exercising concepts on finite trees
\end{itemize}
	
\end{frame}


\begin{frame}{Summary}

Finite Trees
\begin{itemize}
\item recursive declarations of algebraic types

\item meaning of type declarations: rules generating values

\item<2-> typical recursions following the structure of trees

\item<3-> trees with a fixed branching structure

\item<4-> trees with a variable number of sub-trees\\
including two techniques  \hfill $\blue Tree\ list \to \ldots$  
\begin{itemize}
	\item use of mutually recursive function declarations
	\item use of a more general helper function 
\end{itemize}
to handle the arbitrary branching

\item<5-> illustrative examples 
\end{itemize}

\bigskip
\pause[6]

Mutually recursive type and function declarations 

\end{frame}

\begin{frame}
\begin{center}\LARGE\darkgreen 
	On Software Test
\end{center}

\pause
\bigskip

\begin{itemize}
\item functional and structural tests
\item an eye to property based tests
\end{itemize}

\pause
\bigskip

\begin{itemize}
\item A four-project solution using {\blue xUnit}
\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Software test}

{\redbrown Systematic} approaches aiming a finding bugs in programs

\pause
\bigskip

Different kinds of errors in programs: 
\begin{itemize}
	\item {\blue Syntax errors} like $\verb| 3 * (2 - x |$ \hfill missing $\verb|)|$ 
	
	\item {\blue Type errors}, like $\verb| 3 * ("2"- x)|$ 
	
	\item {\blue Semantic error}. A syntactically well-formed and type correct program computes a wrong answer\\
	\ \hfill {\redbrown not discovered by the compiler }
\end{itemize}

\pause
\bigskip

E.W.~Dijkstra, EDW249, 1970: 
\begin{quote}\darkgreen Program testing can be used to show the presence of bugs, but never to show their absence!
\end{quote}

\pause
\bigskip
In "our" context:  
\begin{itemize}
	\item test for finding semantic errors in functions   \ \hfill {\redbrown Unit testing}  
\end{itemize}


\end{frame}

\begin{frame}[fragile]\frametitle{Two important  (among an abundance of) techniques}

\begin{itemize}
	\item {\blue Structural test} (or white-box test or internal test)\\
	
	\medskip
	
	The tester inspects {\redbrown the program} and constructs a {\blue test suite} that shows that all branches can be executed	
	
	\bigskip	
	
	
	
	\item {\blue Functional test} (or black-box test or external test)
	
	
	\medskip
	
	The tester focuses on {\redbrown the requirement} ({\em not the program}) and constructs a {\blue test suite} aiming at justifying that the program solves the task it is supposed to solve.
	
	\bigskip	
	
\end{itemize}


\bigskip\pause

The two techniques {\blue complement} each other, for example

\begin{itemize}
	\item a structural test cannot detect that a sub-task is not implemented
	
	\item a functional test cannot detect the presence of dead code 
	
\end{itemize}


\bigskip\pause

A {\blue test suite} must at least include
\begin{itemize}
	\item input
	\item expected output
\end{itemize}
-- It is used {\darkgreen to assess the quality of the tests}  
\end{frame}



\begin{frame}[fragile]\frametitle{Functional test: an example}

\begin{alltt}\blue
	type Lid     = string 
	type Flight  = string 
	type Airport = string
	
	type Route            = (Flight * Airport) list
	type LuggageCatalogue = (Lid * Route) list 
	
	withFlight: Flight -> LuggageCatalogue -> Lid list
\end{alltt}

Requirement: $\blue \texttt{withFlight}\ f\ lc$ gives the list of identifiers of luggage that are on flight $\blue f$ according to $\blue lc$


\pause\bigskip

{\redbrown Destructive thinking} when designing the test suite: 
\begin{itemize}
	\item Which mistakes may occur in envisioned implementations? 
	
	
	
\end{itemize}


\pause\bigskip

Input should be covered by a finite number of test cases 

%
%This contexts: 02157 Functional programming - Week 7
%

\end{frame}

\begin{frame}[fragile]\frametitle{Functional test: an example test suite (1)}

Requirement: $\blue \texttt{withFlight}\ f\ lc$ gives the list of identifiers of luggage that are on flight $\blue f$ according to $\blue lc$

\medskip \pause

\begin{tabular}{l|l}
	TestId & Input Property \\ \hline
	A      & Empty catalogue \\
	B1 	   & one element cat., flight first in route\\
	B2     & one element cat., flight later in route\\
	B3     & one element cat., flight not in route\\
	C1     & one+ element cat, flight not in any route\\
	C2     & one+ element cat, flight in one route\\
	C3     & one+ element cat, flight in several routes
\end{tabular}

\pause\bigskip

Are there superfluous test cases? 

\pause\bigskip

{\redbrown Destructive thinking}: Are these cases sufficient? 


\pause\bigskip

What about, for example 
\begin{itemize}
	\item C2a: one+ element cat, flight appears first in a route ?
	\item C2b: one+ element cat, flight appears inside a route ?
	\item C2c: one+ element cat, flight appears at the end of a route ?   
\end{itemize}


\end{frame}


\begin{frame}[fragile]\frametitle{Functional test: an example test suite (2)}



\begin{tabular}{l|l|l}
	TestId & Input (f/cat) & expected output contains \\ \hline
	A      &  {\blue "f" []}       & nothing     \\
	...    & ...           & ...         \\
	C2c    & {\blue "f" catC2c}    &   "lid2"      \\
	C3     & ...           & 
\end{tabular}

\medskip

where 
\begin{alltt}\blue
   let catC2c = [("lid1", [("f1","a1")]);
                 ("lid2", [("f2","a2"); ("f","a")]) ]
\end{alltt}	


\pause\bigskip

Functional test:
\begin{itemize}
	\item<2-> Based on educated guesswork: What can possibly go wrong? \\
	You cannot be sure that all errors will be spotted.
	
	\item<3-> It is useful to design the functional test during program development. \\[3mm]
	
	Sharpens the understanding of the problem and its solution.\\[3mm]
	
	\pause[4]
	
	\ \hfill  {\redbrown Is an empty route in a catalogue meaningful?}
	
\end{itemize}

\end{frame}
\begin{frame}[fragile]\frametitle{Structural test: an example test suite (1)}
	
\begin{alltt}\blue
type LuggageCatalogue = (Lid * Route) list 		

// routeOf: Lid -> LuggageCatalogue -> Route option
let rec routeOf lid = 
   function 
   | []                        -> None              // c1 
   | (lid',r)::_ when lid=lid' -> Some r            // c2
   | _::rest                   -> routeOf lid rest  // c3
\end{alltt}
A structural test should exercise 
\begin{itemize}
		\item every branch of the program and
		%\item 
		0, 1 and more recursive calls. 
\end{itemize}
	
	\pause \bigskip
	
	\begin{tabular}{l|l|l|l}
		Choice     & TestId & Input Property  & Recursive calls\\ \hline
		c1         & A      & empty cat.     & $0$              \\
		c2   & B      & non-empty cat & $0$                   \\
		c3  & C 	    & one element cat, lid not found & $1$ \\
		c3  & D      & more than one element cat, lid found & $>1$ 
	\end{tabular} \pause
	
	\bigskip
	
	\begin{center}
		\darkgreen Test C makes Test A superfluous
	\end{center}
	
	
\end{frame}

\begin{frame}[fragile]\frametitle{Structural test: an example test suite (2)}
\begin{alltt}\blue 
let rec routeOf lid = 
   function 
   | []                        -> None              // c1 
   | (lid',r)::_ when lid=lid' -> Some r            // c2
   | _::rest                   -> routeOf lid rest  // c3
\end{alltt}
	\bigskip
	
\begin{tabular}{l|l|l}
TestId & Input (lid/cat) & expected output\\ \hline
B      &  {\blue  "l0" [("l0", $r_0$)]}       &   {\blue\texttt{Some} $r_0$}  \\
C      &  {\blue "l4" [("l0", $r_0$)]}      &  \texttt{\blue None}     \\
D      & {\blue  "l2" [("l0",$r_0$);("l1",$r_1$);("l2",$r_2$)] }    &  {\blue\texttt{Some} $r_2$}     \\ 
\end{tabular}

where	
\begin{itemize}
\item {\blue $r_i$ = [("f0","a0"); \ldots ; ("fi", "ai")], for $i=0,1,2$. }
	
\end{itemize}
	
\bigskip\pause
	
	Each test case is kept "small" focusing only on the concerned Input Property 
	
	\bigskip\pause
	Designing a Structural test is typically easier than designing a Functional test
	
\end{frame}



\begin{frame}[fragile]\frametitle{Property-based test: A fundamental property (III)}
\begin{alltt}\blue	
   type Route            = (Flight * Airport) list
   type LuggageCatalogue = (Lid * Route) list 
	
   withFlight: Flight -> LuggageCatalogue -> Lid list
   routeOf: Lid -> LuggageCatalogue -> Route option
\end{alltt}	

Functional and Structural tests:
\begin{itemize}
\item test just a small number of (hopefully well-justified) single cases for each function	
\end{itemize}

\pause\bigskip

Property-based test (PBT): \hfill {\darkgreen tests having arguments}
\begin{itemize}
\item Fundamental properties {\redbrown every input must satisfy}
\item Properties may express relationships between functions 
\item Validation using random samples 
\end{itemize}

\pause\bigskip

Property($\blue lc$: LuggageCatalogue): \hfill {\redbrown for every $\blue lc$}\\
\qquad for every $\blue lid$ occurring in $\blue lc$::\\
\qquad\qquad for every  $\blue f$ occurring in routeOf $\blue lid$ $\blue lc$:\\ 
\qquad\qquad\qquad $\blue lid$ is in withFlight $\blue f$ $\blue lc$ 




\end{frame}

\begin{frame}[fragile]\frametitle{Automating the tests}


A four-project solution is uploaded to the Material folder on Learn
\begin{itemize}
	\item A class library project containing inRoute, routeOf and withFlight
	
	\item A test project containing structural tests for routeOf
	
	\item A test project containing functional tests for withFlight

	\item A test project containing a PBT for routeOf and withFlight
\end{itemize}
\ \hfill  $\blue \verb|xUnit|$ is used as testing tool 

\pause\bigskip

It happens that $\blue \verb|withFlight|$ is implemented by a programmer having weird ideas.

\medskip

Run the tests in the folder {\blue $\redbrown{X}$Tests} using the command:\\[2mm]
${\blue ...\backslash \mathtt{src}\backslash \mbox{\redbrown{X}}\mathtt{Tests}>\mathtt{dotnet}\ \mathtt{test}}$\\[2mm]

where $\redbrown{X}$ is 'Functional', 'Structural', 'Property'. 
\pause\bigskip

Spot errors, correct the declaration of $\blue \verb|withFlight|$ and rerun tests 

\end{frame}

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

\begin{itemize}
	\item<1-> Functional and Structural test are complementary techniques
	
	\medskip
	
	\item<2-> Test can show the presence of bugs not the absence 
	
	\medskip
	
	\item<3-> Test suite descriptions: the basis for assessing test quality\\
	--- well-designed descriptions increase confidence in programs  
	
	\medskip
	
	\item<4-> Design a functional test suite during program development\\
	--- sharpens the understanding of the problem
	
	\medskip
	
	\item<5-> PBT is a further supplement

    \medskip

    \item<6-> Automate test.\\
Rerun test whenever the program is revised
\end{itemize}

\bigskip\pause[7]
The note: 
\begin{itemize}
	\item {\blue\em Systematic software test}, by Peter Sestoft, 1998
\end{itemize} 
is uploaded to the Material folder on Learn. 


\end{frame}


\end{document}


