197
|
1 |
% !TEX program = xelatex
|
123
|
2 |
\documentclass{article}
|
426
|
3 |
\usepackage{../styles/style}
|
|
4 |
\usepackage{../styles/langs}
|
272
|
5 |
\usepackage{tikz}
|
|
6 |
\usepackage{pgf}
|
123
|
7 |
\usepackage{marvosym}
|
184
|
8 |
\usepackage{boxedminipage}
|
123
|
9 |
|
352
|
10 |
\lstset{escapeinside={/*!}{!*/}}
|
|
11 |
\newcommand{\annotation}[1]{\hfill\footnotesize{}#1}
|
272
|
12 |
|
352
|
13 |
\usepackage{menukeys}
|
335
|
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}
|
334
|
22 |
|
335
|
23 |
|
|
24 |
|
123
|
25 |
\begin{document}
|
442
|
26 |
\fnote{\copyright{} Christian Urban, King's College London, 2022}
|
195
|
27 |
|
452
|
28 |
\section*{Scala Worksheet 4}
|
271
|
29 |
|
444
|
30 |
|
445
|
31 |
|
452
|
32 |
\subsection*{Task 1 (Options Again)}
|
444
|
33 |
|
449
|
34 |
|
301
|
35 |
|
449
|
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}
|
123
|
43 |
|
449
|
44 |
\subsection*{Task 2 (Pattern-Matching, Accumulators)}
|
445
|
45 |
|
449
|
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
|
444
|
53 |
|
445
|
54 |
\begin{lstlisting}[numbers=none]
|
449
|
55 |
def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???
|
343
|
56 |
\end{lstlisting}
|
|
57 |
|
447
|
58 |
\noindent
|
449
|
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.
|
447
|
62 |
|
449
|
63 |
\subsection*{Task 3 (Pattern-Matching, Options, Maps)}
|
447
|
64 |
|
449
|
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}.
|
444
|
72 |
|
|
73 |
\begin{lstlisting}[numbers=none]
|
449
|
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)
|
444
|
77 |
\end{lstlisting}
|
|
78 |
|
449
|
79 |
\subsection*{Task 4 (Pattern-Matching, If-guards, hard)}
|
447
|
80 |
|
449
|
81 |
Recall the tree definition from Task 1. Define a \texttt{height}
|
|
82 |
function that calculates the height of a tree.
|
447
|
83 |
|
449
|
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.
|
447
|
89 |
|
449
|
90 |
\subsection*{Task 5 (Fold, hard)}
|
447
|
91 |
|
448
|
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$.
|
449
|
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}.
|
448
|
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
|
449
|
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.
|
444
|
111 |
|
123
|
112 |
\end{document}
|
|
113 |
|
|
114 |
%%% Local Variables:
|
|
115 |
%%% mode: latex
|
|
116 |
%%% TeX-master: t
|
|
117 |
%%% End:
|