diff -r b183e0dfb7ec -r 4772b6166720 wsheets/wsh04.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/wsheets/wsh04.tex	Thu Dec 08 17:53:08 2022 +0000
@@ -0,0 +1,117 @@
+% !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 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: