\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{marvosym}

%cheat sheet

%http://worldline.github.io/scala-cheatsheet/

\begin{document}

\section*{A Crash-Course on Scala}

\subsection*{The Very Basics}

One advantage of Scala over Java is that it includes an interpreter (a

REPL, or

\underline{R}ead-\underline{E}val-\underline{P}rint-\underline{L}oop)

with which you can run and test small code-snippets without the need

of a compiler. This helps a lot with interactively developing

programs. Once you installed Scala, you can start the interpreter by

typing on the command line:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scala

Welcome to Scala 2.12.4 (Java HotSpot(TM) 64-Bit Server VM, Java 9).

Type in expressions for evaluation. Or try :help.

scala>

\end{lstlisting}%$

\noindent The precise response may vary depending

on the version and platform where you installed Scala. At the Scala

prompt you can type things like \code{2 + 3}\;\keys{Ret} and

the output will be

\begin{lstlisting}[numbers=none]

scala> 2 + 3

res0: Int = 5

\end{lstlisting}

\noindent indicating that the result of the addition is of

type \code{Int} and the actual result is 5. Another classic

example you can try out is

\begin{lstlisting}[numbers=none]

scala> print("hello world")

hello world

\end{lstlisting}

\noindent Note that in this case there is no result. The

reason is that \code{print} does not actually produce a result

(there is no \code{resXX} and no type), rather it is a

function that causes the \emph{side-effect} of printing out a

string. Once you are more familiar with the functional

programming-style, you will know what the difference is

between a function that returns a result, like addition, and a

function that causes a side-effect, like \code{print}. We

shall come back to this point later, but if you are curious

now, the latter kind of functions always has \code{Unit} as

return type.

You can try more examples with the Scala interpreter, but try

first to guess what the result is (not all answers by Scala are obvious):

\begin{lstlisting}[numbers=none]

scala> 2 + 2

scala> 1 / 2

scala> 1.0 / 2

scala> 1 / 2.0

scala> 1 / 0

scala> 1.0 / 0.0

scala> true == false

scala> true && false

scala> 1 > 1.0

scala> "12345".length

\end{lstlisting}

\subsection*{Stand-Alone Apps}

If you want to write a stand-alone app in Scala, you can

implement an object that is an instance of \code{App}, say

\begin{lstlisting}[numbers=none]

object Hello extends App {

    println("hello world")

}

\end{lstlisting}

\noindent save it in a file, say {\tt hello-world.scala}, and

then run the compiler and runtime environment:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scalac hello-world.scala

$ scala Hello

hello world

\end{lstlisting}

Like Java, Scala targets the JVM and consequently

Scala programs can also be executed by the bog-standard Java

Runtime. This only requires the inclusion of {\tt

scala-library.jar}, which on my computer can be done as

follows:

\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]

$ scalac hello-world.scala

$ java -cp /usr/local/src/scala/lib/scala-library.jar:. Hello

hello world

\end{lstlisting}

\noindent You might need to adapt the path to where you have

installed Scala.

\subsection*{Values}

In the lectures, I will try as much as possible to avoid the term

\emph{variables} familiar from other programming languages. Scala

has \emph{values}, which can be seen as abbreviations of larger

expressions. For example

\begin{lstlisting}[numbers=none]

scala> val x = 42

x: Int = 42

scala> val y = 3 + 4

y: Int = 7

scala> val z = x / y

z: Int = 6

\end{lstlisting}

\noindent

Why the kerfuffle about values? Well, values are \emph{immutable}. You cannot

change their value after you defined them. If you try to reassign, say,

\code{z}, Scala will yell at you:

\begin{lstlisting}[numbers=none]

scala> z = 9

error: reassignment to val

       z = 9

         ^

\end{lstlisting}

\noindent

So it would be a bit absurd to call values as variables...you cannot

change them. You might think you can re-assign them like

\begin{lstlisting}[numbers=none]

scala> val x = 42

scala> val z = x / 7

scala> val x = 70

scala> println(z) 

\end{lstlisting}

\noindent but try to guess what Scala will print out in the code above

for \code{z}?  Will it be \code{6} or \code{10}? A final word about

values: Try to stick to the convention that names of values should be

lower case, like \code{x}, \code{y}, \code{foo41} and so on.

\subsection*{Function Definitions}

A function \code{f} taking a single argument of type \code{Int} can be defined

as follows:

\begin{lstlisting}[numbers=none]

def f(x: Int) : String = EXPR

\end{lstlisting} 

\noindent

It returns the value resulting from evaluating the expression

\code{EXPR} (whatever is substituted for this). The result will be

of type \code{String}. Simple examples of Scala functions are:

\begin{lstlisting}[numbers=none]

def incr(x: Int) : Int = x + 1

def double(x: Int) : Int = x + x

def square(x: Int) : Int = x * x

\end{lstlisting}

\noindent

The general scheme for a function is

\begin{lstlisting}[numbers=none]

def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = {

  BODY

}

\end{lstlisting}

\noindent

where each argument requires its type and the result type of the

function, \code{rty}, shoudl be given. If the body of the  function

is more complex, then it can be enclosed in braces; it it is just a

simple expression, like \code{x + 1}, you can omit the braces. Very

often functions are recursive (call themselves) like

\begin{lstlisting}[numbers=none]

def fact(n: Int): Int = 

  if (n == 0) 1 else n * fact(n - 1)

\end{lstlisting}

\subsection*{Loops, or better the Absence thereof}

Coming from Java or C++, you might be surprised that Scala does

not really have loops. It has instead, what is in functional

programming called, \emph{maps}. To illustrate how they work,

let us assume you have a list of numbers from 1 to 8 and want to

build the list of squares. The list of numbers from 1 to 8 

can be constructed in Scala as follows:

\begin{lstlisting}[numbers=none]

scala> (1 to 8).toList

res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

\end{lstlisting}

\noindent Generating from this list, the list of squares in a

programming language such as Java, you would assume the list

is given as a kind of array. You would then iterate, or loop,

an index over this array and replace each entry in the array

by the square. Right? In Scala, and in other functional

programming languages, you use maps to achieve the same. 

A map essentially takes a function that describes how each

element is transformed (for example squared) and a list over

which this function should work. There are two forms to

express such maps in Scala. The first way is called a

\emph{for-comprehension}. Squaring the numbers from 1 to 8

would look as follows:

\begin{lstlisting}[numbers=none]

scala> for (n <- (1 to 8).toList) yield n * n

res2: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64)

\end{lstlisting}

\noindent The important keywords are \code{for} and

\code{yield}. This for-comprehension roughly states that from

the list of numbers we draw \code{n}s and compute the result

of \code{n * n}. As you can see, we specified the list where

each \code{n} comes from, namely \code{(1 to 8).toList}, and

how each element needs to be transformed. This can also be

expressed in a second way in Scala by using directly

\code{map}s as follows:

\begin{lstlisting}[numbers=none]

scala> (1 to 8).toList.map(n => n * n)

res3 = List(1, 4, 9, 16, 25, 36, 49, 64)

\end{lstlisting}

\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). This expression for functions

might remind you of your lessons about the lambda-calculus

where this would have been written as $\lambda n.\,n * n$. It

might not be obvious, but for-comprehensions are just

syntactic sugar: when compiling, 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 as lists, sets, vectors, options and so on.

For example if we instead compute the reminders modulo 3 of

this list, we can write

\begin{lstlisting}[numbers=none]

scala> (1 to 8).toList.map(n => n % 3)

res4 = List(1, 2, 0, 1, 2, 0, 1, 2)

\end{lstlisting}

\noindent If we, however, transform the numbers 1 to 8 not

into a list, but into a set, and then compute the reminders

modulo 3 we obtain

\begin{lstlisting}[numbers=none]

scala> (1 to 8).toSet[Int].map(n => n % 3)

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

\begin{lstlisting}[numbers=none]

scala> for (n <- (1 to 8).toSet[Int]) yield n % 3

res5 = Set(2, 1, 0)

\end{lstlisting}

For-comprehensions can also be nested and the selection of 

elements can be guarded. For example if we want to pair up

the numbers 1 to 4 with the letters a to c, we can write

\begin{lstlisting}[numbers=none]

scala> for (n <- (1 to 4).toList; 

            m <- ('a' to 'c').toList) yield (n, m)

res6 = List((1,a), (1,b), (1,c), (2,a), (2,b), (2,c), 

            (3,a), (3,b), (3,c), (4,a), (4,b), (4,c))

\end{lstlisting}

\noindent 

Or if we want to find all pairs of numbers between 1 and 3

where the sum is an even number, we can write

\begin{lstlisting}[numbers=none]

scala> for (n <- (1 to 3).toList; 

            m <- (1 to 3).toList;

            if (n + m) % 2 == 0) yield (n, m)

res7 = List((1,1), (1,3), (2,2), (3,1), (3,3))

\end{lstlisting}

\noindent The \code{if}-condition in the for-comprehension

filters out all pairs where the sum is not even.

While hopefully this all 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

reminders 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

side-effect. 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)

12345

\end{lstlisting}

\noindent

where you need to omit the keyword \code{yield}. You can

also do more elaborate calculations such as

\begin{lstlisting}[numbers=none]

scala> for (n <- (1 to 5).toList) {

  val square_n = n * n

  println(s"$n * $n = $square_n") 

}

1 * 1 = 1

2 * 2 = 4

3 * 3 = 9

4 * 4 = 16

5 * 5 = 25

\end{lstlisting}%$

\noindent In this code I use a variable assignment (\code{val

square_n = ...} ) 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

integer values \code{n} and \code{square\_n} inside a string.

This is very convenient for printing out ``things''. 

The corresponding map construction for functions with 

side-effects is in Scala called \code{foreach}. So you 

could also write

\begin{lstlisting}[numbers=none]

scala> (1 to 5).toList.foreach(n => print(n))

12345

\end{lstlisting}

\noindent or even just

\begin{lstlisting}[numbers=none]

scala> (1 to 5).toList.foreach(print)

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.

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*{Types}

In most functional programming languages, types play an

important role. Scala is such a language. You have already

seen built-in types, like \code{Int}, \code{Boolean},

\code{String} and \code{BigInt}, but also user-defined ones,

like \code{Rexp}. Unfortunately, types can be a thorny

subject, especially in Scala. For example, why do we need to

give the type to \code{toSet[Int]}, but not to \code{toList}?

The reason is the power of Scala, which sometimes means it

cannot infer all necessary typing information. At the

beginning while getting familiar with Scala, I recommend a

``play-it-by-ear-approach'' to types. Fully understanding

type-systems, especially complicated ones like in Scala, can

take a module on their own.\footnote{Still, such a study can

be a rewarding training: If you are in the business of

designing new programming languages, you will not be able to

turn a blind eye to types. They essentially help programmers

to avoid common programming errors and help with maintaining

code.}

In Scala, types are needed whenever you define an inductive

datatype and also whenever you define functions (their

arguments and their results need a type). Base types are types

that do not take any (type)arguments, for example \code{Int}

and \code{String}. Compound types take one or more arguments,

which as seen earlier need to be given in angle-brackets, for

example \code{List[Int]} or \code{Set[List[String]]} or 

\code{Map[Int, Int]}.

There are a few special type-constructors that fall outside

this pattern. One is for tuples, where the type is written

with parentheses. For example 

\begin{lstlisting}[ numbers=none]

(Int, Int, String)

\end{lstlisting}

\noindent is for a triple (a tuple with three components---two

integers and a string). Tuples are helpful if you want to

define functions with multiple results, say the function

returning the quotient and reminder of two numbers. For this

you might define:

\begin{lstlisting}[ numbers=none]

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

return type needs to be of type \code{(Int, Int)}.

Incidentally, this is also the input type of this function.

Notice this function takes \emph{two} arguments, namely

\code{m} and \code{n}, both of which are integers. They are

``packaged'' in a pair. Consequently the complete type of

\code{quo_rem} is

\begin{lstlisting}[ numbers=none]

(Int, Int) => (Int, Int)

\end{lstlisting}

Another special type-constructor is for functions, 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

\begin{lstlisting}[numbers=none]

def mk_string(n: Int) : String = n match {

  case 0 => "zero"

  case 1 => "one"

  case 2 => "two"

  case _ => "many" 

} 

\end{lstlisting}

\noindent It takes an integer as input argument and returns a

string. Unlike other functional programming languages, there

is in Scala no easy way to find out the types of existing

functions, except by looking into the documentation

\begin{quote}

\url{http://www.scala-lang.org/api/current/}

\end{quote}

The function arrow can also be iterated, as in 

\code{Int => String => Boolean}. This is the type for a function

taking an integer as first argument and a string as second,

and the result of the function is a boolean. Though silly, a

function of this type would be

\begin{lstlisting}[numbers=none]

def chk_string(n: Int)(s: String) : Boolean = 

  mk_string(n) == s

\end{lstlisting}

\noindent which checks whether the integer \code{n}

corresponds to the name \code{s} given by the function

\code{mk\_string}. Notice the unusual way of specifying the

arguments of this function: the arguments are given one after

the other, instead of being in a pair (what would be the type

of this function then?). This way of specifying the arguments

can be useful, for example in situations like this

\begin{lstlisting}[numbers=none]

scala> List("one", "two", "three", "many").map(chk_string(2))

res4 = List(false, true, false, false)

scala> List("one", "two", "three", "many").map(chk_string(3))

res5 = List(false, false, false, true)

\end{lstlisting}

\noindent In each case we can give to \code{map} a specialised

version of \code{chk_string}---once specialised to 2 and once

to 3. This kind of ``specialising'' a function is called

\emph{partial application}---we have not yet given to this

function all arguments it needs, but only some of them.

Coming back to the type \code{Int => String => Boolean}. The

rule about such function types is that the right-most type

specifies what the function returns (a boolean in this case).

The types before that specify how many arguments the function

expects and what their type is (in this case two arguments,

one of type \code{Int} and another of type \code{String}).

Given this rule, what kind of function has type

\mbox{\code{(Int => String) => Boolean}}? Well, it returns a

boolean. More interestingly, though, it only takes a single

argument (because of the parentheses). The single argument

happens to be another function (taking an integer as input and

returning a string). Remember that \code{mk_string} is just 

such a function. So how can we use it? For this define

the somewhat silly function \code{apply_3}:

\begin{lstlisting}[numbers=none]

def apply_3(f: Int => String): Bool = f(3) == "many"

scala> apply_3(mk_string)

res6 = true

\end{lstlisting}

You might ask: Apart from silly functions like above, what is

the point of having functions as input arguments to other