--- a/handouts/pep-ho.tex Thu Oct 31 12:01:56 2019 +0000
+++ b/handouts/pep-ho.tex Fri Nov 01 12:39:25 2019 +0000
@@ -35,7 +35,7 @@
%from program fragments.
-%explain graph coloring program (examples from)
+%explain graph colouring program (examples from)
%https://www.metalevel.at/prolog/optimization
% nice example for map and reduce using Harry potter characters
@@ -386,7 +386,7 @@
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala
-Welcome to Scala 2.13.0 (Java HotSpot(TM) 64-Bit Server VM, Java 9).
+Welcome to Scala 2.13.1 (Java HotSpot(TM) 64-Bit Server VM, Java 9).
Type in expressions for evaluation. Or try :help.
scala>
@@ -609,9 +609,11 @@
\noindent
but this seems a bit overkill for a small function like \code{fact}.
-Note that Scala does not have a \code{then}-keyword in an \code{if}-statement.
-Note also that there are a few other ways of how to define a function. We
-will see some of them in the next sections.
+Note that Scala does not have a \code{then}-keyword in an
+\code{if}-statement; and there should be always an \code{else}-branch.
+Never write an \code{if} without an \code{else}, unless you know what
+you are doing! Note also that there are a few other ways of how to
+define a function. We will see some of them in the next sections.
Before we go on, let me explain one tricky point in function
definitions, especially in larger definitions. What does a Scala function
@@ -836,13 +838,14 @@
res5 = Set(2, 1, 0)
\end{lstlisting}
-\noindent This is the correct result for sets, as there are
-only three equivalence classes of integers modulo 3. Note that
-in this example we need to ``help'' Scala to transform the
-numbers into a set of integers by explicitly annotating the
-type \code{Int}. Since maps and for-comprehensions are
-just syntactic variants of each other, the latter can also be
-written as
+\noindent This\footnote{This returns actually \code{HashSet(2, 1, 3)},
+but this is just an implementation detail of how sets are implemented in
+Scala.} is the correct result for sets, as there are only three
+equivalence classes of integers modulo 3. Note that in this example we
+need to ``help'' Scala to transform the numbers into a set of integers
+by explicitly annotating the type \code{Int}. Since maps and
+for-comprehensions are just syntactic variants of each other, the latter
+can also be written as
\begin{lstlisting}[numbers=none]
scala> for (n <- (1 to 8).toSet[Int]) yield n % 3
@@ -900,7 +903,7 @@
\subsection*{Results and Side-Effects}
-While hopefully this all about maps looks reasonable, there is one
+While hopefully all this about maps looks reasonable, there is one
complication: In the examples above we always wanted to transform one
list into another list (e.g.~list of squares), or one set into another
set (set of numbers into set of remainders modulo 3). What happens if we
@@ -932,7 +935,7 @@
5 * 5 = 25
\end{lstlisting}%$
-\noindent In this code I use a variable assignment (\code{val
+\noindent In this code I use a value assignment (\code{val
square = ...} ) and also what is called in Scala a
\emph{string interpolation}, written \code{s"..."}. The latter
is for printing out an equation. It allows me to refer to the
@@ -986,8 +989,9 @@
\noindent
and indeed this is accepted Scala code and produces the expected result,
namely \code{36}, \textbf{BUT} this is imperative style and not
-permitted in PEP. It uses a \code{var} and therefore violates the
-immutability property I ask for in your code. Sorry!
+permitted in PEP. If you submit this kind of code, you get 0 marks. The
+code uses a \code{var} and therefore violates the immutability property
+I ask for in your code. Sorry!
So how to do that same thing without using a \code{var}? Well there are
several ways. One way is to define the following recursive
@@ -1005,10 +1009,131 @@
all aggregate functions are pre-defined and often you have to write your
own recursive function for this.
-
\subsection*{Higher-Order Functions}
-TBD
+Functions obviously play a central role in functional programming. Two simple
+examples are
+
+\begin{lstlisting}[numbers=none]
+def even(x: Int) : Boolean = x % 2 == 0
+def odd(x: Int) : Boolean = x % 2 == 1
+\end{lstlisting}
+
+\noindent
+More interestingly, the concept of functions is really pushed to the
+limit in functional programming. Functions can take other functions as
+arguments and can return a function as a result. This is actually
+quite important for making code generic. Assume a list of 10 elements:
+
+\begin{lstlisting}[numbers=none]
+val lst = (1 to 10).toList
+\end{lstlisting}
+
+\noindent
+Say, we want to filter out all even numbers. For this we can use
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(even)
+List(2, 4, 6, 8, 10)
+\end{lstlisting}
+
+\noindent
+where \code{filter} expects a function as argument specifying which
+elements of the list should be kept and which should be left out. By
+allowing \code{filter} to take a function as argument, we can also
+easily filter out odd numbers as well.
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(odd)
+List(1, 3, 5, 7, 9)
+\end{lstlisting}
+
+\noindent
+Such function arguments are quite frequently used for ``generic'' functions.
+For example it is easy to count odd elements in a list or find the first
+even number in a list:
+
+\begin{lstlisting}[numbers=none]
+scala> lst.count(odd)
+5
+scala> lst.find(even)
+Some(2)
+\end{lstlisting}
+
+\noindent
+Recall that the return type of \code{even} and \code{odd} are booleans.
+Such function are sometimes called predicates, because they determine
+what should be true for an element and what false, and then performing
+some operation according to this boolean. Such predicates are quite useful.
+Say you want to sort the \code{lst}-list in ascending and descending order.
+For this you can write
+
+\begin{lstlisting}[numbers=none]
+lst.sortWith(_ < _)
+lst.sortWith(_ > _)
+\end{lstlisting}
+
+\noindent where \code{sortWith} expects a predicate as argument. The
+construction \code{_ < _} stands for a function that takes two arguments
+and returns true when the first one is smaller than the second. You can
+think of this as elegant shorthand notation for
+
+\begin{lstlisting}[numbers=none]
+def smaller(x: Int, y: Int) : Boolean = x < y
+lst.sortWith(smaller)
+\end{lstlisting}
+
+\noindent
+Say you want to find in \code{lst} the first odd number greater than 2.
+For this you need to write a function that specifies exactly this
+condition. To do this you can use a slight variant of the shorthand
+notation above
+
+\begin{lstlisting}[numbers=none]
+scala> lst.find(n => odd(n) && n > 2)
+Some(3)
+\end{lstlisting}
+
+\noindent
+Here \code{n => ...} specifies a function that takes \code{n} as
+argument and uses this argument in whatever comes after the double
+arrow. If you want to use this mechanism for looking for an element that
+is both even and odd, then of course you out of luck.
+
+\begin{lstlisting}[numbers=none]
+scala> lst.find(n => odd(n) && even(n))
+None
+\end{lstlisting}
+
+While functions taking functions as arguments seems a rather useful
+feature, the utility of returning a function might not be so clear.
+I admit the following example is a bit contrived, but believe me
+sometims functions produce other functions in a very meaningful way.
+Say we want to generate functions according to strings, as in
+
+\begin{lstlisting}[numbers=none]
+def mkfn(s: String) : (Int => Boolean) =
+ if (s == "even") even else odd
+\end{lstlisting}
+
+\noindent
+With this we can generate the required function for \code{filter}
+according to a string:
+
+\begin{lstlisting}[numbers=none]
+scala> lst.filter(mkfn("even"))
+List(2, 4, 6, 8, 10)
+scala> lst.filter(mkfn("foo"))
+List(1, 3, 5, 7, 9)
+\end{lstlisting}
+
+\noindent
+As said, this is example is a bit contrived---I was not able to think
+of anything simple, but for example in the Compiler module next year I
+show a compilation functions that needs to generate functions as
+intermediate result. Anyway, notice the interesting type we had to
+annotate to \code{mkfn}. Types of Scala are described next.
+
\subsection*{Types}
@@ -1056,10 +1181,10 @@
\begin{lstlisting}[ numbers=none]
-def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)
+def quo_rem(m: Int, n: Int) : (Int, Int) =
+ (m / n, m % n)
\end{lstlisting}
-
\noindent Since this function returns a pair of integers, its
\emph{return type} needs to be of type \code{(Int, Int)}. Incidentally,
this is also the \emph{input type} of this function. For this notice
@@ -1071,10 +1196,12 @@
(Int, Int) => (Int, Int)
\end{lstlisting}
+\noindent
This uses another special type-constructor, written as the arrow
-\code{=>}. For example, the type \code{Int => String} is for a function
-that takes an integer as input argument and produces a string as result.
-A function of this type is for instance
+\code{=>}. This is sometimes also called \emph{function arrow}. For
+example, the type \code{Int => String} is for a function that takes an
+integer as input argument and produces a string as result. A function
+of this type is for instance
\begin{lstlisting}[numbers=none]
def mk_string(n: Int) : String = n match {
@@ -1086,7 +1213,8 @@
\end{lstlisting}
\noindent It takes an integer as input argument and returns a
-string.
+string. The type of the function generated in \code{mkfn} above, is
+\code{Int => Boolean}.
Unfortunately, unlike other functional programming languages, there is
in Scala no easy way to find out the types of existing functions, except
@@ -1160,8 +1288,8 @@
constructions. I think, the point of Java 8 and successors was to lift this
restriction. But in all functional programming languages,
including Scala, it is really essential to allow functions as
-input argument. Above you already seen \code{map} and
-\code{foreach} which need this. Consider the functions
+input argument. Above you have already seen \code{map} and
+\code{foreach} which need this feature. Consider the functions
\code{print} and \code{println}, which both print out strings,
but the latter adds a line break. You can call \code{foreach}
with either of them and thus changing how, for example, five
@@ -1193,24 +1321,23 @@
\emph{polymorphic}.\footnote{Another interesting topic about
types, but we omit it here for the sake of brevity.}
-There is one more type constructor that is rather special. It
-is called \code{Unit}. Recall that \code{Boolean} has two
-values, namely \code{true} and \code{false}. This can be used,
-for example, to test something and decide whether the test
-succeeds or not. In contrast the type \code{Unit} has only a
-single value, written \code{()}. This seems like a completely
-useless type and return value for a function, but is actually
-quite useful. It indicates when the function does not return
-any result. The purpose of these functions is to cause
-something being written on the screen or written into a file,
-for example. This is what is called they cause some effect on
-the side, namely a new content displayed on the screen or some
-new data in a file. Scala uses the \code{Unit} type to indicate
-that a function does not have a result, but potentially causes
-some side-effect. Typical examples are the printing functions,
-like \code{print}.
+There is one more type constructor that is rather special. It is
+called \code{Unit}. Recall that \code{Boolean} has two values, namely
+\code{true} and \code{false}. This can be used, for example, to test
+something and decide whether the test succeeds or not. In contrast the
+type \code{Unit} has only a single value, written \code{()}. This
+seems like a completely useless type and return value for a function,
+but is actually quite useful. It indicates when the function does not
+return any result. The purpose of these functions is to cause
+something being written on the screen or written into a file, for
+example. This is what is called they cause a \emph{side-effect}, for
+example new content displayed on the screen or some new data in a
+file. Scala uses the \code{Unit} type to indicate that a function does
+not have a result, but potentially causes a side-effect. Typical
+examples are the printing functions, like \code{print}.
-\subsection*{User-Defined Types}
+
+%%\subsection*{User-Defined Types}
% \subsection*{Cool Stuff}