wsheets/wsh04.tex
author Christian Urban <christian.urban@kcl.ac.uk>
Thu, 08 Dec 2022 21:28:33 +0000
changeset 453 08cd972b219f
parent 452 4772b6166720
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
197
Christian Urban <urbanc@in.tum.de>
parents: 195
diff changeset
     1
% !TEX program = xelatex
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
\documentclass{article}
426
b51467741af2 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 400
diff changeset
     3
\usepackage{../styles/style}
b51467741af2 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 400
diff changeset
     4
\usepackage{../styles/langs}
272
da3d30ae67ec updated
Christian Urban <urbanc@in.tum.de>
parents: 271
diff changeset
     5
\usepackage{tikz}
da3d30ae67ec updated
Christian Urban <urbanc@in.tum.de>
parents: 271
diff changeset
     6
\usepackage{pgf}
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
\usepackage{marvosym}
184
84dc794928de updated
pdated
parents: 183
diff changeset
     8
\usepackage{boxedminipage}
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
352
97bcf8efe4e0 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 343
diff changeset
    10
\lstset{escapeinside={/*!}{!*/}}
97bcf8efe4e0 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 343
diff changeset
    11
\newcommand{\annotation}[1]{\hfill\footnotesize{}#1}
272
da3d30ae67ec updated
Christian Urban <urbanc@in.tum.de>
parents: 271
diff changeset
    12
352
97bcf8efe4e0 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 343
diff changeset
    13
\usepackage{menukeys}
335
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    14
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    15
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    16
% Exact colors from NB
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    17
\usepackage[breakable]{tcolorbox}
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    18
\definecolor{incolor}{HTML}{303F9F}
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    19
\definecolor{outcolor}{HTML}{D84315}
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    20
\definecolor{cellborder}{HTML}{CFCFCF}
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    21
\definecolor{cellbackground}{HTML}{F7F7F7}
334
841727e27252 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 333
diff changeset
    22
335
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    23
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 334
diff changeset
    24
    
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
\begin{document}
442
c86e7dd198bf updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 441
diff changeset
    26
\fnote{\copyright{} Christian Urban, King's College London, 2022}
195
fc3ac7b70a06 updated
Christian Urban <urbanc@in.tum.de>
parents: 193
diff changeset
    27
452
4772b6166720 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 449
diff changeset
    28
\section*{Scala Worksheet 4}
271
48e12e7aee6e updated
Christian Urban <urbanc@in.tum.de>
parents: 270
diff changeset
    29
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    30
445
b73e7ce91c10 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 444
diff changeset
    31
452
4772b6166720 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 449
diff changeset
    32
\subsection*{Task 1 (Options Again)}
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    33
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    34
301
c3b33c709696 updated
Christian Urban <urbanc@in.tum.de>
parents: 278
diff changeset
    35
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    36
\begin{itemize}
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    37
\item[(1)] Define a function \texttt{mirror} that takes a tree as argument and returns
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    38
the mirror-image of a tree (meaning left- and right-hand side are
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    39
exchanged).
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    40
\item[(2)] Define a function \texttt{sum\_tree} that sums up all
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    41
  leaves in a tree.
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    42
\end{itemize}  
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    43
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    44
\subsection*{Task 2 (Pattern-Matching, Accumulators)}
445
b73e7ce91c10 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 444
diff changeset
    45
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    46
Define a function \texttt{remdups} that removes duplicates in a list,
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    47
say list of integers. This functions should take a list of integers
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    48
as argument and returns a list of integers. In order to remove
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    49
elements that have already been seen, use an accumulator which can be
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    50
a set of of integers (for fast lookup whether an element has already
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    51
been seen). The accumulator can be implemented either with an
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    52
auxiliary function or with a default argument like
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    53
445
b73e7ce91c10 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 444
diff changeset
    54
\begin{lstlisting}[numbers=none]
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    55
def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???
343
c8fcc0e0a57f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 335
diff changeset
    56
\end{lstlisting}
c8fcc0e0a57f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 335
diff changeset
    57
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    58
\noindent
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    59
Are you familiar with polymorphic types in Scala? If yes, can you
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    60
define \texttt{remdups} generically so that it works for any type
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    61
of lists.
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    62
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    63
\subsection*{Task 3 (Pattern-Matching, Options, Maps)}
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    64
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    65
Remember that the method \texttt{indexOf} returns $-1$ whenever it
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    66
cannot find an element in a list. Define a better version of
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    67
this function, called \texttt{indexOfOption} that returns in
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    68
the failure case \texttt{None} and in the success case
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    69
\texttt{Some}$(n)$ where $n$ is the index of the element in the
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    70
list. Try to define this function recursively but without an
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    71
auxiliary function. For this use a \texttt{map}.
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    72
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    73
\begin{lstlisting}[numbers=none]
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    74
scala> indexOfOption(List(1,2,3,4,5,6), 7)   // => None
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    75
scala> indexOfOption(List(1,2,3,4,5,6), 4)   // => Some(3)
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    76
scala> indexOfOption(List(1,2,3,4,3,6), 3)   // => Some(2)
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    77
\end{lstlisting}
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
    78
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    79
\subsection*{Task 4 (Pattern-Matching, If-guards,  hard)}
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    80
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    81
Recall the tree definition from Task 1. Define a \texttt{height}
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    82
function that calculates the height of a tree.
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    83
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    84
Define a second function \texttt{balance} that makes sure that the
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    85
height of a left and right child is balanced (only differ in heights
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    86
by maximal of one). Implement this function by balancing trees
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    87
stepwise - reorder that the height difference changes by one and then
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    88
the balancing is repeated.
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    89
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    90
\subsection*{Task 5 (Fold, hard)}
447
f51e593903ac updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 445
diff changeset
    91
448
db2a3e3287a9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 447
diff changeset
    92
Implement a function \texttt{fold} for lists of integers. It takes
db2a3e3287a9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 447
diff changeset
    93
a list of integers as argument as well as a function $f$ and a unit element $u$.
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    94
The function $f$ is of type \texttt{(Int, Int) => Int} and the unit element
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    95
is of type \texttt{Int}. The return type of \texttt{fold} is \texttt{Int}.
448
db2a3e3287a9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 447
diff changeset
    96
What is \texttt{fold} supposed to do? Well it should fold the function $f$
db2a3e3287a9 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 447
diff changeset
    97
over the elements of the list and in case of the empty list return the
449
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    98
unit element $u$.
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
    99
%
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   100
\[
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   101
  \begin{array}{lcl}
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   102
    \texttt{fold}(Nil, f, u) & \dn & u\\
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   103
    \texttt{fold}(x::xs, f, u) & \dn & f(x, \texttt{fold}(xs, f, u))\\
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   104
  \end{array}\smallskip  
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   105
\]
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   106
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   107
\noindent
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   108
Use \texttt{fold} to define the sum of a list of integers and the
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   109
product of a list of integers. Try to use Scala's shorthand notation
d67c5f7177a6 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 448
diff changeset
   110
\texttt{\_ + \_} and \texttt{\_ * \_} for functions.
444
7a0735db4788 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 442
diff changeset
   111
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   112
\end{document}
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   113
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   114
%%% Local Variables: 
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   115
%%% mode: latex
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   116
%%% TeX-master: t
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   117
%%% End: