% !TEX program = xelatex
\documentclass{article}
\usepackage{../styles/style}
\usepackage{../styles/langs}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{marvosym}
\usepackage{boxedminipage}

\lstset{escapeinside={/*!}{!*/}}
\newcommand{\annotation}[1]{\hfill\footnotesize{}#1}

\usepackage{menukeys}


% Exact colors from NB
\usepackage[breakable]{tcolorbox}
\definecolor{incolor}{HTML}{303F9F}
\definecolor{outcolor}{HTML}{D84315}
\definecolor{cellborder}{HTML}{CFCFCF}
\definecolor{cellbackground}{HTML}{F7F7F7}


    
\begin{document}
\fnote{\copyright{} Christian Urban, King's College London, 2022}

\section*{Scala Worksheet 3}



\subsection*{Task 1 (Datatypes, Pattern-Matching)}

Define the datatype for binary trees where leaves contain an
integer and inner nodes contain only a left and a right child.
Use pattern-matching to define the following functions:


\begin{itemize}
\item[(1)] Define a function \texttt{mirror} that takes a tree as argument and returns
the mirror-image of a tree (meaning left- and right-hand side are
exchanged).
\item[(2)] Define a function \texttt{sum\_tree} that sums up all
  leaves in a tree.
\end{itemize}  

\subsection*{Task 2 (Pattern-Matching, Accumulators)}

Define a function \texttt{remdups} that removes duplicates in a list,
say list of integers. This functions should take a list of integers
as argument and returns a list of integers. In order to remove
elements that have already been seen, use an accumulator which can be
a set of of integers (for fast lookup whether an element has already
been seen). The accumulator can be implemented either with an
auxiliary function or with a default argument like

\begin{lstlisting}[numbers=none]
def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???
\end{lstlisting}

\noindent
Are you familiar with polymorphic types in Scala? If yes, can you
define \texttt{remdups} generically so that it works for any type
of lists.

\subsection*{Task 3 (Pattern-Matching, Options, Maps)}

Remember that the method \texttt{indexOf} returns $-1$ whenever it
cannot find an element in a list. Define a better version of
this function, called \texttt{indexOfOption} that returns in
the failure case \texttt{None} and in the success case
\texttt{Some}$(n)$ where $n$ is the index of the element in the
list. Try to define this function recursively but without an
auxiliary function. For this use a \texttt{map}.

\begin{lstlisting}[numbers=none]
scala> indexOfOption(List(1,2,3,4,5,6), 7)   // => None
scala> indexOfOption(List(1,2,3,4,5,6), 4)   // => Some(3)
scala> indexOfOption(List(1,2,3,4,3,6), 3)   // => Some(2)
\end{lstlisting}

\subsection*{Task 4 (Pattern-Matching, If-guards,  hard)}

Recall the tree definition from Task 1. Define a \texttt{height}
function that calculates the height of a tree.

Define a second function \texttt{balance} that makes sure that the
height of a left and right child is balanced (only differ in heights
by maximal of one). Implement this function by balancing trees
stepwise - reorder that the height difference changes by one and then
the balancing is repeated.

\subsection*{Task 5 (Fold, hard)}

Implement a function \texttt{fold} for lists of integers. It takes
a list of integers as argument as well as a function $f$ and a unit element $u$.
The function $f$ is of type \texttt{(Int, Int) => Int} and the unit element
is of type \texttt{Int}. The return type of \texttt{fold} is \texttt{Int}.
What is \texttt{fold} supposed to do? Well it should fold the function $f$
over the elements of the list and in case of the empty list return the
unit element $u$.
%
\[
  \begin{array}{lcl}
    \texttt{fold}(Nil, f, u) & \dn & u\\
    \texttt{fold}(x::xs, f, u) & \dn & f(x, \texttt{fold}(xs, f, u))\\
  \end{array}\smallskip  
\]

\noindent
Use \texttt{fold} to define the sum of a list of integers and the
product of a list of integers. Try to use Scala's shorthand notation
\texttt{\_ + \_} and \texttt{\_ * \_} for functions.

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: