32 \subsection*{Task 1 (Options)}

    32 \subsection*{Task 1 (Datatypes, Pattern-Matching)}

    34 Get familiar with the return value of functions that can

    34 Define the datatype for binary trees where leaves contain an

    35 ``go wrong'':

    35 integer and inner nodes contain only a left and a right child.

    36 Use pattern-matching to define the following functions:

    37 

    38 

    39 \begin{itemize}

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

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

    42 exchanged).

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

    44   leaves in a tree.

    45 \end{itemize}  

    46 

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

    48 

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

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

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

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

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

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

    55 auxiliary function or with a default argument like

    38 scala> List(7,2,3,4,5,6).find(_ < 4)

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

    39 scala> List(5,6,7,8,9).find(_ < 4)

    40 scala> List(5,6,7,8,9).min

    41 scala> List(5,6,7,8,9).minOption

    42 scala> List[Int]().minOption

    46 Note that there needs to be a type-annotation for \texttt{List()} otherwise

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

    47 Scala will not know which \texttt{min}-version it should use. 

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

    64 of lists.

    49 \subsection*{Task 2 (Try)}

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

    51 The Scala-Idiom \texttt{Try-getOrElse} allows you to conveniently

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

    52 deal with failure cases.

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

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

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

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

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

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

    55 scala> Try(Some(List(5,6,7,8,9).min)).getOrElse(None)

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

    56 scala> Try(Some(List[Int]().min)).getOrElse(None)

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

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

    59 \noindent

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

    60 Note that \texttt{Try} needs the library \texttt{scala.util.\_} to be

    61 imported. 

    64 \begin{lstlisting}[numbers=none]

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

    65 def safe_div(x: Int, y: Int) : Option[Int] = 

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

    66   Try(Some(x / y)).getOrElse(None)

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

    67 \end{lstlisting}

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

    91 the balancing is repeated.

    69 \subsection*{Task 3 (URLs / Files)}

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

    70 

    71 For simple tasks such as reading webpages and files, Scala provides

    72 convenient functions \texttt{Source.fromURL} and \texttt{Source.fromFile}.

    73 To try them out, you need to import \texttt{io.Source}.

    74 

    75 \begin{lstlisting}[numbers=none]

    76 scala> Source.fromURL(my_url)("ISO-8859-1").mkString

    77 scala> Source.fromFile(my_file)("ISO-8859-1").mkString

    78 \end{lstlisting}

    79 

    80 \noindent

    81 These functions return an iterator, which can be transformed into a String

    82 using \texttt{mkString}. The second argument fixes the character encoding

    83 and should not be omitted. If you are interested in the individual lines

    84 in the file, for example, you can use

    85 

    86 \begin{lstlisting}[numbers=none]

    87 Source.fromFile(my_file)("ISO-8859-1")

    88                             .getLines().toList

    89 \end{lstlisting}

    90 

    91 \noindent

    92 If you are after proper error-handling, then you can use Scala's options

    93 as follows

    94 

    95 \begin{lstlisting}[numbers=none]

    96 Try(Some(Source.fromFile("test.txt")("ISO-8859-1")

    97                           .mkString)).getOrElse(None)

    98 \end{lstlisting}  

    99 

   100 This can also be written slightly shorter as

   101 

   102 \begin{lstlisting}[numbers=none]

   103 Try(Source.fromFile("test.txt")("ISO-8859-1")

   104                           .mkString).toOption

   105 \end{lstlisting}  

   106 

   107 \noindent

   108 In case of reading files, there can be an issue with closing

   109 files properly. For this Scala provides \texttt{Using}

   110 

   111 \begin{lstlisting}[numbers=none]

   112   Using(Source.fromFile("test.txt")("ISO-8859-1"))

   113                                  (_.mkString).toOption

   114 \end{lstlisting}  

   115 

   116 \noindent

   117 This closes the files automatically after reading, but otherwise

   118 behaves as the code shown above: It gives a \texttt{Some} in the

   119 success case and \texttt{None} in the failure case. However,

   120 \texttt{Using} requires a function as argument for prescribing

   121 of what to do with the file content in the success case.

   122 

   123 \subsection*{Task 4 (Higher-Order Functions)}

   124 

   125 Higher-Order functions means that Scala allows functions to

   126 have functions as arguments and also allows functions to

   127 return functions. Get familiar with the short-hand notation

   128 for simple functions

   129 

   130 \begin{lstlisting}[numbers=none]

   131 scala> List(7,2,3,4,5,6).find(_ < 4)

   132 scala> List(7,2,3,4,5,6).count(_ % 2 == 0)

   133 scala> List(7,2,3,4,5,6).sortWith(_ > _)

   134 scala> List(7,2,3,4,5,6).filter(_ > 4)

   135 \end{lstlisting}

   136 

   137 \noindent

   138 Be aware that this short-hand notation only works for ``smallish'' functions

   139 and that sometimes Scala cannot figure out the types involved without

   140 explicit type annotations.

   141 

   142 \subsection*{Task 5 (Maps)}

   143 

   144 Get familiar with the map-function for lists, sets etc. It is the

   145 quintessential higher-order function and frequently used for transforming

   146 lists.

   147 

   148 \begin{lstlisting}[numbers=none]

   149 scala> List(7,2,3,4,5,6).map(n => n * n)

   150 \end{lstlisting}  

   151 

   152 \noindent

   153 Make also sure you see that Scala's \texttt{for}-comprehensions

   154 are just syntactic sugar for \texttt{map}s. What would this

   155 expression look like as \texttt{for}-comprehension? What are

   156 the advantages of \texttt{for}-comprehensions over \texttt{map}s.

   157 

   158 

   159 \subsection*{Task 6 (Pattern-Matching)}

   160 

   161 Rewrite the following function using pattern-matching

   162 

   163 \begin{lstlisting}[numbers=none]

   164 def my_map(lst: List[Int], f: Int => Int) : List[Int] = {

   165  if (lst == Nil) Nil

   166  else f(lst.head) :: my_map(lst.tail, f)

   167 }

   168 \end{lstlisting}

   169 

   170 \noindent

   171 Observe that the type of the function is from \texttt{Int}s to

   172 \texttt{Int}s, which is written in Scala as type \texttt{Int => Int}.

   173 

   174 

   175 \subsection*{Task 7 (Fold, Hard)}

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

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

   180 is an integer. The return type of \texttt{fold} is \texttt{Int}.

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

   183 unit element $u$. 

   101 unit element $u$.

   102 %

   103 \[

   104   \begin{array}{lcl}

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

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

   107   \end{array}\smallskip  

   108 \]

   109 

   110 \noindent

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

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

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