# HG changeset patch # User Christian Urban # Date 1565190942 -3600 # Node ID b192276607528f0f5736bb31a63ea6ab35ea160f # Parent da3d30ae67ec3f4bc61abf03d3ac53b93f9fe4f9 updated diff -r da3d30ae67ec -r b19227660752 handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed diff -r da3d30ae67ec -r b19227660752 handouts/pep-ho.tex --- a/handouts/pep-ho.tex Wed Aug 07 14:32:21 2019 +0100 +++ b/handouts/pep-ho.tex Wed Aug 07 16:15:42 2019 +0100 @@ -743,9 +743,9 @@ On top is the ``input'' list we want to transform; on the left is the ``map'' function for how to transform each element in the input list (the square function in this case); at the bottom is the result list of -the map. This means that a map produces a \emph{new} list as a result, -unlike a for-loop in Java or C/C++ which would most likely update the list -exists in memory after the map. +the map. This means that a map produces a \emph{new} list, unlike a +for-loop in Java or C/C++ which would most likely just update the +existing list. Now there are two ways to express such maps in Scala. The first way is called a \emph{for-comprehension}. The keywords are \code{for} and @@ -764,15 +764,15 @@ languages, even though the idea behind for-loops and for-comprehensions is quite different. Also, this is a simple example---what comes after \code{yield} can be a complex expression enclosed in \texttt{\{...\}}. -An example might be +A more complicated example might be \begin{lstlisting}[numbers=none] scala> for (n <- (1 to 8).toList) yield { val i = n + 1 val j = n - 1 - i * j + i * j + 1 } -res3: List[Int] = List(0, 3, 8, 15, 24, 35, 48, 63) +res3: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64) \end{lstlisting} As you can see in for-comprehensions above, we specified the list where @@ -788,9 +788,9 @@ \noindent In this way, the expression \code{n => n * n} stands for the function that calculates the square (this is how the \code{n}s are transformed by the map). It might not be obvious, but -for-comprehensions above are just syntactic sugar: when compiling, Scala -translates for-comprehensions into equivalent maps. This even works when -for-comprehensions get more complicated (see below). +for-comprehensions above are just syntactic sugar: when compiling such +code, Scala translates for-comprehensions into equivalent maps. This +even works when for-comprehensions get more complicated (see below). The very charming feature of Scala is that such maps or for-comprehensions can be written for any kind of data collection, such @@ -852,9 +852,9 @@ the result because the sum is odd). To sum up, maps (or for-comprehensions) transform one collection into -another. For example a list of \code{Int}s into a list of squares, or a -list of \code{Int}s into a set of \code{Int}s and so on. There is no need -for for-loops in Scala. But please do not be tempted to write anything like +another. For example a list of \code{Int}s into a list of squares, and +so on. There is no need for for-loops in Scala. But please do not be +tempted to write anything like \begin{lstlisting}[numbers=none] scala> val cs = ('a' to 'h').toList @@ -876,16 +876,15 @@ \subsection*{Results and Side-Effects} While hopefully this all 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 just want to print out -a list of integers? Then actually the for-comprehension -needs to be modified. The reason is that \code{print}, you -guessed it, does not produce any result, but only produces -what is in the functional-programming-lingo called a -\emph{side-effect}. Printing out the list of numbers from 1 to 5 -would look as follows +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 +just want to print out a list of integers? In these cases the +for-comprehensions need to be modified. The reason is that \code{print}, +you guessed it, does not produce any result, but only produces what is +in the functional-programming-lingo called a \emph{side-effect}\ldots it +prints something out on the screen. Printing out the list of numbers +from 1 to 5 would look as follows \begin{lstlisting}[numbers=none] scala> for (n <- (1 to 5).toList) print(n) @@ -933,17 +932,55 @@ 12345 \end{lstlisting} -\noindent Again I hope this reminds you a bit of your -lambda-calculus lessons, where an explanation is given why -both forms produce the same result. - - +\noindent If you want to find out more about maps and functions with side-effects, you can ponder about the response Scala gives if you replace \code{foreach} by \code{map} in the expression above. Scala will still allow \code{map} with side-effect functions, but then reacts with a slightly interesting result. +\subsection*{Aggregates} + +There is one more usage of for-loops in Java, C/C++ and the like: +sometimes you want to \emph{aggregate} something about a list, for +example to sum up all its elements. In this case you cannot use map, +because maps \emph{transform} one data collection into another data +collection. They cannot be used to generate a single integer +representing an aggregate. So how is this done in Scala? Let us +suppose you want to sum up all elements from a list. You might +be tempted to write something like + +\begin{lstlisting}[numbers=none] +var cnt = 0 +for (n <- (1 to 8).toList) { + cnt += n +} +print(cnt) +\end{lstlisting} + +\noindent +and indeed is accepted Scala code and produces the expected result, +namely \code{36}, \textbf{BUT} this is imperative style and not +permitted. It uses a \code{var} and therefore violates the immutability +property I ask for in your code. + +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 +\code{sum}-function: + +\begin{lstlisting}[numbers=none] +def sum(xs: List[Int]) : Int = + if (xs.isEmpty) 0 else xs.head + sum(xs.tail) +\end{lstlisting} + +\noindent +You can then call \code{sum((1 to 8).toList)} and obtain the same result +without a mutable for-loop. Obviously for simple things like sum, you +could have written \code{xs.sum} in the first place. But not all +aggregate functions are pre-defined and often you have to write your own +recursive function for this. + + \subsection*{Higher-Order Functions} \subsection*{Types} diff -r da3d30ae67ec -r b19227660752 progs/lecture1.scala --- a/progs/lecture1.scala Wed Aug 07 14:32:21 2019 +0100 +++ b/progs/lecture1.scala Wed Aug 07 16:15:42 2019 +0100 @@ -472,6 +472,16 @@ time_needed(10, for (n <- list) yield n + 42) time_needed(10, for (n <- list.par) yield n + 42) +val list = (1 to 1000000).toList.map(BigInt(_)) +list.sum +list.par.sum +list.par.reduce(_ + _) +list.par.aggregate(BigInt(0))(_ + _, _ + _) + +time_needed(10, list.sum) +time_needed(10, list.par.sum) +time_needed(10, list.par.reduce(_ + _)) +time_needed(10, list.par.aggregate(BigInt(0))(_ + _, _ + _)) // Just for "Fun": Mutable vs Immutable