diff -r db2a3e3287a9 -r d67c5f7177a6 wsheets/wsh03.tex --- 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}