% !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 4}\subsection*{Task 1 (Options Again)}\begin{itemize}\item[(1)] Define a function \texttt{mirror} that takes a tree as argument and returnsthe mirror-image of a tree (meaning left- and right-hand side areexchanged).\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 integersas argument and returns a list of integers. In order to removeelements that have already been seen, use an accumulator which can bea set of of integers (for fast lookup whether an element has alreadybeen seen). The accumulator can be implemented either with anauxiliary function or with a default argument like\begin{lstlisting}[numbers=none]def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???\end{lstlisting}\noindentAre you familiar with polymorphic types in Scala? If yes, can youdefine \texttt{remdups} generically so that it works for any typeof lists.\subsection*{Task 3 (Pattern-Matching, Options, Maps)}Remember that the method \texttt{indexOf} returns $-1$ whenever itcannot find an element in a list. Define a better version ofthis function, called \texttt{indexOfOption} that returns inthe failure case \texttt{None} and in the success case\texttt{Some}$(n)$ where $n$ is the index of the element in thelist. Try to define this function recursively but without anauxiliary function. For this use a \texttt{map}.\begin{lstlisting}[numbers=none]scala> indexOfOption(List(1,2,3,4,5,6), 7) // => Nonescala> 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 theheight of a left and right child is balanced (only differ in heightsby maximal of one). Implement this function by balancing treesstepwise - reorder that the height difference changes by one and thenthe balancing is repeated.\subsection*{Task 5 (Fold, hard)}Implement a function \texttt{fold} for lists of integers. It takesa 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 elementis 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 theunit 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 \]\noindentUse \texttt{fold} to define the sum of a list of integers and theproduct 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: