% !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: