1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{../styles/style}

     4 \usepackage{../styles/langs}

     5 \usepackage{tikz}

     6 \usepackage{pgf}

     7 \usepackage{marvosym}

     8 \usepackage{boxedminipage}

     9 

    10 \lstset{escapeinside={/*!}{!*/}}

    11 \newcommand{\annotation}[1]{\hfill\footnotesize{}#1}

    12 

    13 \usepackage{menukeys}

    14 

    15 

    16 % Exact colors from NB

    17 \usepackage[breakable]{tcolorbox}

    18 \definecolor{incolor}{HTML}{303F9F}

    19 \definecolor{outcolor}{HTML}{D84315}

    20 \definecolor{cellborder}{HTML}{CFCFCF}

    21 \definecolor{cellbackground}{HTML}{F7F7F7}

    22 

    23 

    24     

    25 \begin{document}

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

    27 

    28 \section*{Scala Worksheet 4}

    29 

    30 

    31 

    32 \subsection*{Task 1 (Options Again)}

    33 

    34 

    35 

    36 \begin{itemize}

    37 \item[(1)] Define a function \texttt{mirror} that takes a tree as argument and returns

    38 the mirror-image of a tree (meaning left- and right-hand side are

    39 exchanged).

    40 \item[(2)] Define a function \texttt{sum\_tree} that sums up all

    41   leaves in a tree.

    42 \end{itemize}  

    43 

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

    45 

    46 Define a function \texttt{remdups} that removes duplicates in a list,

    47 say list of integers. This functions should take a list of integers

    48 as argument and returns a list of integers. In order to remove

    49 elements that have already been seen, use an accumulator which can be

    50 a set of of integers (for fast lookup whether an element has already

    51 been seen). The accumulator can be implemented either with an

    52 auxiliary function or with a default argument like

    53 

    54 \begin{lstlisting}[numbers=none]

    55 def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???

    56 \end{lstlisting}

    57 

    58 \noindent

    59 Are you familiar with polymorphic types in Scala? If yes, can you

    60 define \texttt{remdups} generically so that it works for any type

    61 of lists.

    62 

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

    64 

    65 Remember that the method \texttt{indexOf} returns $-1$ whenever it

    66 cannot find an element in a list. Define a better version of

    67 this function, called \texttt{indexOfOption} that returns in

    68 the failure case \texttt{None} and in the success case

    69 \texttt{Some}$(n)$ where $n$ is the index of the element in the

    70 list. Try to define this function recursively but without an

    71 auxiliary function. For this use a \texttt{map}.

    72 

    73 \begin{lstlisting}[numbers=none]

    74 scala> indexOfOption(List(1,2,3,4,5,6), 7)   // => None

    75 scala> indexOfOption(List(1,2,3,4,5,6), 4)   // => Some(3)

    76 scala> indexOfOption(List(1,2,3,4,3,6), 3)   // => Some(2)

    77 \end{lstlisting}

    78 

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

    80 

    81 Recall the tree definition from Task 1. Define a \texttt{height}

    82 function that calculates the height of a tree.

    83 

    84 Define a second function \texttt{balance} that makes sure that the

    85 height of a left and right child is balanced (only differ in heights

    86 by maximal of one). Implement this function by balancing trees

    87 stepwise - reorder that the height difference changes by one and then

    88 the balancing is repeated.

    89 

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

    91 

    92 Implement a function \texttt{fold} for lists of integers. It takes

    93 a list of integers as argument as well as a function $f$ and a unit element $u$.

    94 The function $f$ is of type \texttt{(Int, Int) => Int} and the unit element

    95 is of type \texttt{Int}. The return type of \texttt{fold} is \texttt{Int}.

    96 What is \texttt{fold} supposed to do? Well it should fold the function $f$

    97 over the elements of the list and in case of the empty list return the

    98 unit element $u$.

    99 %

   100 \[

   101   \begin{array}{lcl}

   102     \texttt{fold}(Nil, f, u) & \dn & u\\

   103     \texttt{fold}(x::xs, f, u) & \dn & f(x, \texttt{fold}(xs, f, u))\\

   104   \end{array}\smallskip  

   105 \]

   106 

   107 \noindent

   108 Use \texttt{fold} to define the sum of a list of integers and the

   109 product of a list of integers. Try to use Scala's shorthand notation

   110 \texttt{\_ + \_} and \texttt{\_ * \_} for functions.

   111 

   112 \end{document}

   113 

   114 %%% Local Variables: 

   115 %%% mode: latex

   116 %%% TeX-master: t

   117 %%% End: