--- a/wsheets/wsh03.tex Fri Nov 25 00:03:15 2022 +0000
+++ b/wsheets/wsh03.tex Fri Dec 02 07:48:03 2022 +0000
@@ -29,158 +29,88 @@
-\subsection*{Task 1 (Options)}
+\subsection*{Task 1 (Datatypes, Pattern-Matching)}
-Get familiar with the return value of functions that can
-``go wrong'':
+Define the datatype for binary trees where leaves contain an
+integer and inner nodes contain only a left and a right child.
+Use pattern-matching to define the following functions:
+
-\begin{lstlisting}[numbers=none]
-scala> List(7,2,3,4,5,6).find(_ < 4)
-scala> List(5,6,7,8,9).find(_ < 4)
-scala> List(5,6,7,8,9).min
-scala> List(5,6,7,8,9).minOption
-scala> List[Int]().minOption
-\end{lstlisting}
+\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}
-\noindent
-Note that there needs to be a type-annotation for \texttt{List()} otherwise
-Scala will not know which \texttt{min}-version it should use.
+\subsection*{Task 2 (Pattern-Matching, Accumulators)}
-\subsection*{Task 2 (Try)}
-
-The Scala-Idiom \texttt{Try-getOrElse} allows you to conveniently
-deal with failure cases.
+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]
-scala> Try(Some(List(5,6,7,8,9).min)).getOrElse(None)
-scala> Try(Some(List[Int]().min)).getOrElse(None)
-\end{lstlisting}
-
-\noindent
-Note that \texttt{Try} needs the library \texttt{scala.util.\_} to be
-imported.
-
-
-\begin{lstlisting}[numbers=none]
-def safe_div(x: Int, y: Int) : Option[Int] =
- Try(Some(x / y)).getOrElse(None)
-\end{lstlisting}
-
-\subsection*{Task 3 (URLs / Files)}
-
-For simple tasks such as reading webpages and files, Scala provides
-convenient functions \texttt{Source.fromURL} and \texttt{Source.fromFile}.
-To try them out, you need to import \texttt{io.Source}.
-
-\begin{lstlisting}[numbers=none]
-scala> Source.fromURL(my_url)("ISO-8859-1").mkString
-scala> Source.fromFile(my_file)("ISO-8859-1").mkString
-\end{lstlisting}
-
-\noindent
-These functions return an iterator, which can be transformed into a String
-using \texttt{mkString}. The second argument fixes the character encoding
-and should not be omitted. If you are interested in the individual lines
-in the file, for example, you can use
-
-\begin{lstlisting}[numbers=none]
-Source.fromFile(my_file)("ISO-8859-1")
- .getLines().toList
+def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ???
\end{lstlisting}
\noindent
-If you are after proper error-handling, then you can use Scala's options
-as follows
-
-\begin{lstlisting}[numbers=none]
-Try(Some(Source.fromFile("test.txt")("ISO-8859-1")
- .mkString)).getOrElse(None)
-\end{lstlisting}
+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.
-This can also be written slightly shorter as
-
-\begin{lstlisting}[numbers=none]
-Try(Source.fromFile("test.txt")("ISO-8859-1")
- .mkString).toOption
-\end{lstlisting}
-
-\noindent
-In case of reading files, there can be an issue with closing
-files properly. For this Scala provides \texttt{Using}
+\subsection*{Task 3 (Pattern-Matching, Options, Maps)}
-\begin{lstlisting}[numbers=none]
- Using(Source.fromFile("test.txt")("ISO-8859-1"))
- (_.mkString).toOption
-\end{lstlisting}
-
-\noindent
-This closes the files automatically after reading, but otherwise
-behaves as the code shown above: It gives a \texttt{Some} in the
-success case and \texttt{None} in the failure case. However,
-\texttt{Using} requires a function as argument for prescribing
-of what to do with the file content in the success case.
-
-\subsection*{Task 4 (Higher-Order Functions)}
-
-Higher-Order functions means that Scala allows functions to
-have functions as arguments and also allows functions to
-return functions. Get familiar with the short-hand notation
-for simple functions
+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> List(7,2,3,4,5,6).find(_ < 4)
-scala> List(7,2,3,4,5,6).count(_ % 2 == 0)
-scala> List(7,2,3,4,5,6).sortWith(_ > _)
-scala> List(7,2,3,4,5,6).filter(_ > 4)
+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}
-\noindent
-Be aware that this short-hand notation only works for ``smallish'' functions
-and that sometimes Scala cannot figure out the types involved without
-explicit type annotations.
-
-\subsection*{Task 5 (Maps)}
+\subsection*{Task 4 (Pattern-Matching, If-guards, hard)}
-Get familiar with the map-function for lists, sets etc. It is the
-quintessential higher-order function and frequently used for transforming
-lists.
-
-\begin{lstlisting}[numbers=none]
-scala> List(7,2,3,4,5,6).map(n => n * n)
-\end{lstlisting}
+Recall the tree definition from Task 1. Define a \texttt{height}
+function that calculates the height of a tree.
-\noindent
-Make also sure you see that Scala's \texttt{for}-comprehensions
-are just syntactic sugar for \texttt{map}s. What would this
-expression look like as \texttt{for}-comprehension? What are
-the advantages of \texttt{for}-comprehensions over \texttt{map}s.
-
-
-\subsection*{Task 6 (Pattern-Matching)}
-
-Rewrite the following function using pattern-matching
+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.
-\begin{lstlisting}[numbers=none]
-def my_map(lst: List[Int], f: Int => Int) : List[Int] = {
- if (lst == Nil) Nil
- else f(lst.head) :: my_map(lst.tail, f)
-}
-\end{lstlisting}
-
-\noindent
-Observe that the type of the function is from \texttt{Int}s to
-\texttt{Int}s, which is written in Scala as type \texttt{Int => Int}.
-
-
-\subsection*{Task 7 (Fold, Hard)}
+\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 is of type \texttt{(Int, Int) => Int} and the unit element
-is an integer. The return type of \texttt{fold} is \texttt{Int}.
+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$.
+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}