Object-Oriented and Functional Programming: exam prep

Scala in one page: expressions, methods, ranges, printing

Scala is a statically typed language that runs on the Java virtual machine and mixes object oriented and functional programming. "Statically typed" means the compiler knows the type of every expression before the program runs, and refuses programs where types do not fit. A few facts explain most of the code you will read on the exam.

Almost everything is an expression. An expression is a piece of code that produces a value. In Scala, if is an expression (it gives a value, like the ? : operator in Java), and a block { ... } is an expression whose value is the value of its last line. A method body is usually just one expression.

val n = 7
val kind = if (n % 2 == 0) "even" else "odd"   // if gives a value
println(kind)
val total = { val a = 3; val b = 4; a * b }    // value of a block = last expression
println(total)

odd
12

Methods are defined with def name(param: Type): ResultType = body. The result type can often be left out (type inference). Unit is the result type of a method that returns nothing useful (like void in Java). n % m is the remainder, so n % m == 0 means "n is a multiple of m". Note that 0 % m == 0 is true: 0 is a multiple of every number.

Ranges. 1 to 5 includes both ends (1,2,3,4,5). 1 until 5 stops before the end (1,2,3,4). Mapping over a range gives a Vector, which is why some exam answers print as Vector(...).

println((1 to 5).toList)
println((1 until 5).toList)
println((1 to 3).map(_ * 2))
List(1, 2, 3).foreach(print)                 // no separators, no newline
println()
List(1, 2, 3).foreach(x => print(x + " "))   // a space after each element

List(1, 2, 3, 4, 5)
List(1, 2, 3, 4)
Vector(2, 4, 6)
123
1 2 3 

_ * 2 is short for x => x * 2, an anonymous function (Week 3 explains this placeholder notation fully). foreach(print) calls print on each element: everything comes out glued together.

return leaves the whole method, not just the loop. A for loop that contains a return in every iteration therefore only ever runs its first iteration. Compare these two methods: one small change, a different answer.

def firstBig(l: List[Int]): Int = {
  for (e <- l) {
    if (e > 10) return e      // returns only when the test holds
  }
  -1
}
def oops(l: List[Int]): Int = {
  for (e <- l) {
    return if (e > 10) e else 0   // returns in the very first iteration
  }
  -1
}
println(firstBig(List(3, 12, 40)))
println(oops(List(3, 12, 40)))

12
0

val r = { val a = 2; if (a > 1) a * 10 else 0 } + 1
println(r)
println((1 until 4).map(i => i * i))

21
Vector(1, 4, 9)

def g(l: List[Int]): Int = {
  for (e <- l) if (e % 2 == 0) return e * 10
  99
}
println((g(List(1, 3, 4, 6)), g(List(1, 3)), g(List())))

(40,99,99)

Reading pipelines and if-chains (the question 1 pattern)

A pipeline is a chain like range.map(f).filter(p).map(g). Each step makes a new collection from the previous one:

• map(f): replace every element x by f(x). Same number of elements.
• filter(p): keep only the elements for which p(x) is true. Order is kept.
• filter(!isMultipleOf(_, 3)): the ! flips the test, so it keeps the non-multiples.

The steps run left to right, and each step sees the values produced by the step before it, not the original numbers. That is the whole trick of these questions: the exam swaps the order of two steps and the answer changes.

Paper method: the pipeline table. One row per starting element, one column per step. Write the value after each step; when a filter rejects a value, write "x" and stop that row. At the end, read the last column top to bottom.

def squash(n: Int): Int = if (n % 4 == 0) 1 else n
println((0 until 10).map(_ + 1).map(squash).filter(_ > 2).map(_ * 10))
println((0 until 10).map(squash).map(_ + 1).filter(_ > 2).map(_ * 10))

In the second line squash runs before + 1, so it sees 0..9 instead of 1..10. Now 0, 4 and 8 become 1 (0 is a multiple of 4!), and then +1 makes them 2, which the filter drops. Same steps, different order, different output:

Vector(30, 50, 60, 70, 90, 100)
Vector(30, 40, 60, 70, 80, 100)

If-chains: the first true test wins. In if (A) .. else if (B) .. else if (C) .., Scala tests A, then B only if A was false, and so on. Later tests are never looked at once one matched. So the order of the tests matters when they overlap, as "multiple of 6" and "multiple of 2" do.

def isMultipleOf(n: Int, m: Int): Boolean = n % m == 0
def label(n: Int): String =
  if (isMultipleOf(n, 6)) "ab"
  else if (isMultipleOf(n, 2)) "a"
  else if (isMultipleOf(n, 3)) "b"
  else n.toString
def label2(n: Int): String =        // same tests, the 6-test moved last
  if (isMultipleOf(n, 2)) "a"
  else if (isMultipleOf(n, 3)) "b"
  else if (isMultipleOf(n, 6)) "ab"
  else n.toString
(1 to 7).map(label).foreach(print)
println()
(1 to 7).map(label2).foreach(print)

1aba5ab7
1aba5a7

In label2, 6 is caught by the "multiple of 2" test first, so the "ab" branch can never be reached.

def tag(n: Int): String =
  if (isMultipleOf(n, 10)) "T" else if (isMultipleOf(n, 5)) "F" else n.toString
(0 until 12).filter(_ % 2 == 1).map(_ + 4).map(tag).foreach(print)

F791113F

def half(n: Int): Int = if (isMultipleOf(n, 3)) n / 3 else n
(1 to 9).map(half).filter(_ >= 3).map(_ * 2).foreach(x => print(x + " "))
println()
(1 to 9).filter(_ >= 3).map(half).map(_ * 2).foreach(x => print(x + " "))

8 10 14 16 6
2 8 10 4 14 16 6 

println(List(3, 8, 1).map(_ + 2).filter(_ > 4).exists(_ % 5 == 0))
println(List(1, 2).map(_ + 2).filter(_ > 4).exists(_ % 5 == 0))

true
false

var vs val

A variable is a name with a value attached. Scala has two kinds:

• val x = ...: the name is bound once. Writing x = ... later is a compile error.
• var x = ...: the name can be re-bound with x = .... x += 3 is short for x = x + 3.

var b = 1
b = 2
b += 3
println(b)
val a = 1
a = 2          // does not compile

5
error: reassignment to val

Here is the part that matters for the exam. A val fixes which object the name points to, not what is inside that object. An Array is a mutable object (its slots can be changed), so a val holding an array still lets you change the slots:

val arr = Array(1, 2, 3)
arr(0) = 99           // fine: changes a slot inside the array object
println(arr.toList)
arr = Array(3)        // does not compile: re-binds the val

List(99, 2, 3)
error: reassignment to val

The opposite combination also exists: a var holding an immutable value. Then the name can move to a new value, but the old value never changes, so anyone who copied the old one keeps seeing it:

var v = Vector(1, 2)
val w = v            // w points to the same Vector(1, 2)
v = v :+ 3           // :+ builds a NEW vector; v now points to it
println((v, w))

(Vector(1, 2, 3),Vector(1, 2))

A subtle consequence: s += 3 on a var holding an immutable Set compiles, because Scala rewrites it to s = s + 3 (a new set). On a val holding an immutable set it does not compile, since there is neither a mutating += nor a variable to re-bind:

error: value += is not a member of scala.collection.immutable.Set[Int]
  Expression does not convert to assignment because receiver is not assignable.

Parameters of a method behave like vals: def reset(a: Array[Int]): Unit = a = Array(0) gives "reassignment to val".

var i = 0
for (i <- 0 until 3) {}
println(i)
for (j <- 0 until 3) i += j
println(i)

0
3

var s1 = Set(1, 2);  s1 += 3                              // (a)
val s2 = Set(1, 2);  s2 += 3                              // (b)
val s3 = scala.collection.mutable.Set(1, 2);  s3 += 3     // (c)

Scoping: which variable does this name mean?

The scope of a declaration is the part of the program where its name can be used. Scala uses lexical scoping: which variable a name refers to is decided by where the code is written, not by who happens to call it. The rule for finding it: start where the name is used and look outward, through the enclosing blocks, to the first declaration with that name.

A parameter (def p(a: Int)) and a local variable (var c = ... inside a method) are new variables that exist only during that call. If they have the same name as a global variable, they shadow it: inside that method the name means the local one, and the global one cannot be reached by that name. Without a declaration, a plain assignment like c = 5 or b += a changes the variable from the enclosing scope, usually the global one.

Paper method, two passes.

1. Label every name. For each method, list its parameters and the names it declares with val/var. Every other name in it is global (or belongs to an enclosing method). Write a small subscript on each use: b<sub>G</sub> for global, a<sub>p</sub> for p's own.
2. Run with a state table. One column per global, plus a column for the locals of the call that is running. Execute line by line. When a call returns, its locals disappear and its result goes into the assignment that called it. An assignment of the result happens after the call, so it overwrites whatever the call itself did to that variable.

var a = 2
var b = 10
var c = 0
def p(a: Int): Int = {      // a = p's parameter; b, c = global
  b += a
  c = a * 2
  a + 1
}
def q(b: Int, d: Int): Int = {   // b, d = parameters; a = global
  var c = b + d                  // NEW local c, hides global c
  a = p(c)
  c + b
}
def run(): Unit = {
  a = p(b)
  b = q(a, 1)
  println((a, b, c))
}
run()

(13,23,24)

Note the last row: p had raised the global b to 32, but the assignment b = q(...) runs after q returns and overwrites it with 23.

One small change. Delete the word var in q, so the line becomes c = b + d. Now that line writes the global c (12), p overwrites it with 24, and q returns c + b = global c 24 + b_q 11 = 35:

(13,35,24)

Lexical, not dynamic. A method only sees its own names and the names around its definition. It never sees the locals of whoever called it:

var k = 1
def h(x: Int): Int = k + x                  // k is ALWAYS the global k
def g(x: Int): Int = { var k = 100; h(x) }  // this local k is invisible to h
println(g(5))

6

Nested methods are the exception that proves the rule: a method defined inside another method sees the outer method's locals, because they are lexically around it.

var x = 0
def outer(y: Int): Int = {
  var x = y                                        // outer's local x
  def inner(z: Int): Int = { x -= z; z + 1 }       // this x is outer's x
  val r = inner(3)
  x + r
}
println(outer(10))
println(x)

11
0

inner(3) makes outer's x 7 and returns 4; outer returns 7 + 4 = 11. The global x is never touched.

var n = 1
var m = 0
def f(m: Int): Int = {
  n += m
  m * 2
}
def g(n: Int): Int = {
  val r = f(n + 1)
  m = r + n
  r
}
println((g(n), n, m))

(4,3,5)

var total = 0
def add(total: Int, x: Int): Int = total + x
def addAllWrong(): Unit = for (i <- 1 to 3) add(total, i)
def addAll(): Unit = for (i <- 1 to 3) total = add(total, i)
addAllWrong(); println(total)
addAll(); println(total)

0
6

var v = 3
def a(): Int = { v = v * 2; v }
def b(v: Int): Int = { val w = a(); v + w }
println(b(v))
println(v)

9
6

Classes and constructors

A class is a blueprint; an object (or instance) is one thing built from it with new. Each new builds a fresh, separate object with its own fields. A field is a variable that lives inside an object.

In Scala the class header is the main (primary) constructor: class Counter(start: Int) takes one argument when you write new Counter(5). All statements in the class body run once, top to bottom, when the object is built.

class Counter(start: Int) {
  var count: Int = start                     // a field, set during construction
  println("made a Counter at " + start)      // body runs at construction
  def inc(): Unit = count += 1
}
val c1 = new Counter(5)
c1.inc(); c1.inc()
val c2 = new Counter(5)
println(c1.count + " " + c2.count)

made a Counter at 5
made a Counter at 5
7 5

Three kinds of constructor parameter.

Auxiliary constructors are extra constructors written def this(...). Their first statement must call another constructor of the same class, so in practice they supply default values:

class Lamp(var on: Boolean) {
  def this() = this(false)        // new Lamp() means new Lamp(false)
  def toggle(): Unit = on = !on
}
val l1 = new Lamp()
val l2 = new Lamp(true)
l1.toggle()
println((l1.on, l2.on))

(true,true)

Identity. For an ordinary class, == asks "is this the very same object?". Two objects built separately with equal fields are not equal; two names pointing to one object are:

class PlainPoint(val x: Int, val y: Int)
val pa = new PlainPoint(1, 2)
val pb = new PlainPoint(1, 2)
println(pa == pb)        // two different objects
val pc = pa
println(pa == pc)        // same object

false
true

(Case classes, Week 2, change this: they compare fields.)

Nested classes. A class written inside another class (Week 3 covers these) can use the fields of the outer class. Every inner object remembers which outer object it was made from: new t1.Player(2) belongs to the object t1. Draw this as a hidden arrow from the inner object to its outer object. All inner objects of the same outer object change the same outer fields.

class Team(var score: Int) {
  class Player(var bonus: Int) {
    def scoreGoal(): Unit = { score += bonus; bonus += 1 }   // score = the outer Team's field
  }
}
val t1 = new Team(0)
val t2 = t1                    // same Team object, second name
val p = new t1.Player(2)
val q = new t2.Player(10)      // also belongs to that one Team
p.scoreGoal(); p.scoreGoal(); q.scoreGoal()
println(t1.score)
val t3 = new Team(0)
val r = new t3.Player(1)
r.scoreGoal()
println((t1.score, t3.score, p.bonus, q.bonus, r.bonus))

15
(15,1,4,11,2)

p scores 2 then 3 (its bonus grew), q scores 10, all into the one Team: 15. t3 is a different Team, so r only changes t3.

class Lamp(var on: Boolean) {
  def this() = this(false)
  def toggle(): Unit = on = !on
}
val a = new Lamp()
val b = a
val c = new Lamp()
b.toggle(); c.toggle(); c.toggle()
println((a.on, b.on, c.on))

Objects (singletons)

The keyword object defines a class and its one and only instance at the same time. This is called a singleton. You never write new for it; you use its name directly. Its fields are effectively global variables, and its methods are like static methods in Java. A program's entry point is a main method in an object: object Foo { def main(args: Array[String]): Unit = ... }.

object Settings {
  val Width = 10
  var clicks = 0
  def click(): Int = { clicks += 1; clicks }
}
Settings.click(); Settings.click()
println(Settings.clicks)
val s1 = Settings
val s2 = Settings
s1.click()
println(s2.clicks)         // s1 and s2 are the same single object

2
3

An object is created the first time it is used, not when the program starts. Its body then runs once:

object Logger {
  println("Logger created")
  def hi(): Unit = println("hi")
}
println("start")
Logger.hi()
Logger.hi()

start
Logger created
hi
hi

Companion objects

A companion object is an object with the same name as a class, written in the same file. The two may read each other's private members. The companion is the place for things that belong to the class as a whole rather than to one instance: constants, and factory methods that build instances.

A method named apply is special: Rational(1, 2) is short for Rational.apply(1, 2). That is how you can create objects without new.

class Rational(val n: Int, val d: Int) {
  def +(r: Rational): Rational = Rational(n * r.d + r.n * d, d * r.d)
  override def toString: String = n + "/" + d
}
object Rational {
  def apply(n: Int, d: Int): Rational = {      // factory: always simplifies
    val g = gcd(n.abs, d.abs)
    new Rational(n / g, d / g)
  }
  def apply(n: Int): Rational = apply(n, 1)
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  val Zero: Rational = new Rational(0, 1)
}
println(Rational(1, 2) + Rational(1, 3))
println(Rational(2, 4))
println(Rational.Zero)
println(new Rational(2, 4))      // new skips the factory

5/6
1/2
0/1
2/4

The Snake framework uses a companion for constants: GameLogic.FramesPerSecond and GameLogic.DefaultGridDims live in object GameLogic. A companion can also call a private constructor, so it can control how objects are made:

class Account private (val owner: String, private var balance: Int) {
  def deposit(x: Int): Unit = balance += x
}
object Account {
  def open(owner: String): Account = new Account(owner, 0)   // allowed: companion
  def balanceOf(a: Account): Int = a.balance                 // allowed: companion
}
val acc = Account.open("Sam")
acc.deposit(20)
println(Account.balanceOf(acc))

20

println(Rational(3, 6) + Rational.Zero)
println(Rational(4))

Named and default arguments

A parameter can have a default value: if the caller leaves it out, the default is used. A caller can also name an argument (height = 1), which lets them skip earlier parameters or give arguments in any order.

def box(width: Int = 3, height: Int = 2, fill: Char = '#'): String =
  ((fill.toString * width) + "\n") * height
print(box())
print(box(height = 1))
print(box(5, fill = '.'))
print(box(fill = '*', width = 2))

###
###
###
.....
.....
**
**

Positional arguments fill parameters from the left. Once you have named an argument out of its position, positional arguments may not follow: box(height = 1, 4) gives "positional after named argument".

def greet(name: String, greeting: String = "Hello", end: String = "!"): String =
  greeting + ", " + name + end
println(greet("Ann"))
println(greet("Ann", end = "?"))
println(greet(greeting = "Hi", name = "Bob"))
println(greet("Cy", "Hey"))

Hello, Ann!
Hello, Ann?
Hi, Bob!
Hey, Cy!

You met this in Snake: case class SnakeBody(distanceToHead: Float = 0f), which is why both SnakeBody() and SnakeBody(0.5f) appear in exam code. The copy method of case classes (Week 2) is built on named and default arguments: p.copy(y = 5).

Tuples

A tuple groups a fixed number of values, possibly of different types, without defining a class: (3, "three", true) has type (Int, String, Boolean). You read the parts with ._1, ._2, ... (counting from 1), or unpack them with a pattern. Tuples are immutable.

val t = (3, "three", true)
println(t._1 + 1)
println(t)
val (num, word, _) = t                 // unpack; _ ignores a part
println(word * 2)
def minMax(l: List[Int]): (Int, Int) = (l.min, l.max)   // return two results
val (lo, hi) = minMax(List(4, 1, 9))
println(hi - lo)
println((1, 2) == (1, 2))              // tuples compare their parts

4
(3,three,true)
threethree
8
true

t._1 = 5 gives "reassignment to val". Tuples show up in three exam situations:

• Printing: println((a, b)) prints (x,y) with no space after the comma.
• Pairs in loops and maps: for ((l, r) <- pairs) unpacks each pair; a Map is a collection of key/value pairs, and (k, v) and k -> v are the same pair.
• Types: the type of an if that returns tuples is computed per position (the Week 6 lesson on lub covers this). And a tuple can be the accumulator of a fold, so one pass computes two results.

val pairs = for (x <- List(1, 2); y <- List("a", "b")) yield (x, y)
println(pairs)
val joined = for ((k, s) <- pairs) yield s + k
println(joined)
println(List(1, 2, 3).foldLeft((0, 1))((acc, e) => (acc._1 + e, acc._2 * e)))

List((1,a), (1,b), (2,a), (2,b))
List(a1, b1, a2, b2)
(6,6)

println((1, 2).swap)
println((("x", 1), ("y", 2))._2._1)

(2,1)
y

Aliasing: references and the box-and-arrow picture

This is the most important topic of the block. The professor's slide says it in four words: everything is a reference.

An object lives somewhere in memory. Draw it as a box with its fields inside. A variable, a field, an array slot or a parameter does not contain the object; it contains a reference to it. Draw a reference as an arrow from the slot to the box. When two arrows point to the same box, the two names are aliases: different names for one object. A change made through one name is visible through the other, because there is only one box.

For immutable values like Int, Boolean and String the arrow can never be observed (nobody can change the box), so you may simply write the value in the slot.

The four rules of the picture.

1. Only new C(...) (or a case class call like Point(1,2)) draws a new box. Nothing else creates objects.
2. Assignment copies an arrow, never a box. x = y, arr(i) = y, passing y as an argument, putting it in a list, returning it: the target gets an arrow to the box y points to.
3. Re-pointing changes one slot. arr(1) = new Cell(5) or b = ... moves only that one arrow. Other arrows to the old box stay where they are.
4. Mutating changes a box. x.v += 1, arr(i).v = 3, buf.addOne(5): follow the arrow and change the box. Every name with an arrow to that box sees the change.

So for each line of code, ask: does it re-point an arrow (left side is a variable or slot), or change a box (left side has a dot: something.field, or calls a mutating method)?

class Cell(var v: Int)
val a = new Array[Cell](3)
val c = new Cell(0)
for (i <- a.indices) a(i) = c      // three arrows to ONE box
a(1) = new Cell(7)                 // re-point slot 1 only
a(0).v += 5                        // change the shared box
println(a.map(_.v).toList)

List(5, 7, 5)

Slots 0 and 2 (and c) still point to the one shared box, so the += 5 shows up twice. Slot 1 was re-pointed before the change, so it is not affected.

Copy the arrow vs copy the value. To get an independent copy you must build new boxes yourself:

val snap = new Array[Cell](3)
for (i <- snap.indices) snap(i) = new Cell(a(i).v)   // new boxes with the current values
a(2).v = 100                                          // the shared box again
println(a.map(_.v).toList)
println(snap.map(_.v).toList)

List(100, 7, 100)
List(5, 7, 5)

Chains. arr(i) = arr(i - 1) in a loop makes every slot point to the first box, so every += lands in that one box:

val chain = new Array[Cell](4)
chain(0) = new Cell(0)
for (i <- 1 until chain.length) { chain(i) = chain(i - 1); chain(i).v += 2 }
println(chain.map(_.v).toList)

List(6, 6, 6, 6)

Three increments of 2 into one box: 6. And because all four slots show that box, a sum over the array counts it four times (24).

Objects that hold references. A field can hold an arrow too. Re-pointing the field inside one object does not move any other arrow:

class Wallet(var euros: Int)
class Person(var wallet: Wallet) {
  def spend(x: Int): Unit = wallet.euros -= x                          // changes the box
  def newWallet(): Unit = wallet = new Wallet(wallet.euros + 1)        // re-points own field
}
val w = new Wallet(10)
val p = new Person(w)       // p.wallet and w: same box
p.spend(3)
println(w.euros)
p.newWallet()               // p.wallet now points to a NEW box (8); w still to the old (7)
p.spend(5)
println(w.euros)
println(p.wallet.euros)

7
7
3

Passing to a method copies the arrow. The method can change the box you passed, and the caller sees it:

def shout(words: Array[String]): Unit = { words(0) = words(0).toUpperCase }
val w1 = Array("hi", "there")
val w2 = w1
shout(w2)
println(w1.toList)
println(w2.toList)

List(HI, there)
List(HI, there)

Arrays also compare by identity: Array(1, 2) == Array(1, 2) is false (two boxes), while List(1, 2) == List(1, 2) is true (lists compare contents).

class Counter(var n: Int)
val k = new Counter(1)
val cs = Array(k, new Counter(1), k)
for (cc <- cs) cc.n *= 2
println(cs.map(_.n).toList)

List(4, 2, 4)

val ds = new Array[Counter](4)
for (i <- ds.indices) ds(i) = if (i % 2 == 0) new Counter(i) else ds(i - 1)
for (d <- ds) d.n += 1
println(ds.map(_.n).toList)

List(2, 2, 4, 4)

var u = new Counter(5)
val uu = u
u.n += 1          // mutate the box (both see 6)
u = new Counter(0)
u.n += 1          // mutate the NEW box
println((u.n, uu.n))

(1,6)

Reverse Polish notation and the calculator

Normal arithmetic is written infix: the operator goes between its operands, (3 + 4) * 2, and you need brackets and precedence rules. In reverse Polish notation (RPN, also called postfix) the operator comes after its two operands: 3 4 + 2 *. No brackets are ever needed.

Evaluation with a stack. A stack is a pile: you can only add (push) on top and take (pop) from the top. Read the tokens left to right:

• a number: push it;
• an operator: pop the top (that is the right operand), pop the next (the left operand), push left op right.

At the end the stack holds one number, the answer. The order of the pops matters for - and /: 10 4 - is 10 - 4 = 6.

def applyOp(op: String, l: Int, r: Int): Int =
  if (op == "+") l + r
  else if (op == "-") l - r
  else if (op == "*") l * r
  else l / r
def isOp(t: String): Boolean = t == "+" || t == "-" || t == "*" || t == "/"
def evalRPN(input: String): Int = {
  var stack: List[Int] = List()            // head of the list = top of the stack
  for (token <- input.split(" ")) {
    if (isOp(token)) {
      val r = stack.head
      val l = stack.tail.head
      stack = applyOp(token, l, r) :: stack.tail.tail
    } else stack = token.toInt :: stack
    println(token + "  stack: " + stack)
  }
  stack.head
}
println(evalRPN("10 2 3 * -"))

10  stack: List(10)
2  stack: List(2, 10)
3  stack: List(3, 2, 10)
*  stack: List(6, 10)
-  stack: List(4)
4

The list is printed with the top of the stack on the left. * pops 3 and 2 and pushes 6; - pops 6 (right) and 10 (left) and pushes 10 - 6 = 4. The infix version is 10 - 2 * 3. Move one operator and the meaning changes: 10 2 - 3 * is (10 - 2) * 3 = 24.

Note how this implementation uses an immutable List as the stack and a var that is re-pointed to a new list at every token: a typical Week 2 style (immutable data, the variable moves).

14

15

1

The Snake framework: "what does this GameLogic display?"

In assignment 2 you wrote only the class GameLogic. The framework (SnakeGame, which you did not change) owns the window and calls your methods. To answer the exam questions you need to know exactly when it calls what. Paraphrased from the real framework code:

// framework, at the start (once):
gameLogic = new GameLogic(random, gridDims)       // your constructor and class body run once

// framework, many times per second (draw):
if (it is time for the next frame) {              // FramesPerSecond = 5 in the real game
  gameLogic.step()                                // ONE step: update your state
}
for (p <- gridDims.allPointsInside)               // every cell, row by row
  paint(p, gameLogic.getCellType(p))              // SnakeBody = green, Empty = white

// framework, when a key is pressed:
gameLogic.changeDir(direction)                    // arrow keys

So the picture you see is always a function of the current state: step() changes the state once per frame, and getCellType(p) is asked, for every cell, "what is at position p right now?". It should only read the state; the framework calls it once per cell per frame (30 calls per frame on a 6 by 5 grid, as a counting run confirmed).

Coordinates. Point(x, y): x is the column, 0 at the left, growing to the right. y is the row, 0 at the top, growing downwards. So "y increases" means "moves down". gridDims.width is the number of columns, gridDims.height the number of rows; valid x are 0 to width - 1.

Cell types. SnakeBody(f) is a green cell; the number f (0 to 1) only chooses the shade of green (the distance to the head). It never moves anything. Empty() is a white cell. Older exams (2019, 2020) use the old API getCellType(x: Int, y: Int) or getGridType(x, y) and SnakeBody(1.0f): same idea.

Paper method: simulate a few frames.

1. State. List the vars and their start values (the class body runs once).
2. Time. Make a frame table: frame 0 = start state, frame k = state after k calls of step(). Fill in 4 to 6 frames, until you see a pattern (it repeats, bounces, or toggles). If there is no step or it changes nothing, the picture is static.
3. Space. For one frame, plug the state values into getCellType and read the condition as a shape, using the dictionary below. Draw it on a tiny 5 by 5 grid if in doubt.
4. Movie. Compare consecutive frames: what moves, blinks, grows or alternates? Match that with the options.

Worked example: a row that moves down and wraps around.

class RowLogic(val gridDims: Dimensions) {
  var r = 0
  def step(): Unit = r = (r + 1) % gridDims.height
  def getCellType(p: Point): CellType = if (p.y == r) SnakeBody() else Empty()
}

State: r. Frames: r = 0, 1, 2, 3, 4, then % height (height 5) makes it 0 again. Shape: p.y == r is true for every x in row r: one full row. Movie: a row moving down, jumping back to the top after the bottom. A small simulator that does exactly what the framework does (step, then ask every cell) prints these frames side by side (# = SnakeBody, . = Empty, grid 6 by 5):

######   ......   ......   ......   ......   ######
......   ######   ......   ......   ......   ......
......   ......   ######   ......   ......   ......
......   ......   ......   ######   ......   ......
......   ......   ......   ......   ######   ......

Small change 1: if (p.y == r || p.x == r). || means "either one": row r plus column r, a plus shape whose centre (r, r) moves diagonally.

######   .#....   ..#...   ...#..
#.....   ######   ..#...   ...#..
#.....   .#....   ######   ...#..
#.....   .#....   ..#...   ######
#.....   .#....   ..#...   ...#..

Small change 2: if (p.y == r && p.x == r). && means "both": only the crossing point, a single cell moving diagonally.

#.....   ......   ......   ......
......   .#....   ......   ......
......   ......   ..#...   ......
......   ......   ......   ...#..
......   ......   ......   ......

The shape dictionary (each checked on a 9 by 7 grid; c, s, r, b stand for state values):

Some of these as the simulator draws them:

x % 2 == 0 || y % 2 == 0     outline (s = 2)     band dy < 2
#########                    .........           .........
#.#.#.#.#                    ..#####..           .........
#########                    ..#...#..           #########
#.#.#.#.#                    ..#...#..           #########
#########                    ..#...#..           #########
#.#.#.#.#                    ..#####..           .........
#########                    .........           .........

The time dictionary (how step changes the state):

Old API scoping trap. With getCellType(x: Int, y: Int) the parameter x shadows the field x. Inside that method, x is the cell's column and this.x is the field. if (x == this.x) is a column at the field's position; if (x == x) would compare the parameter with itself and fill the whole screen.

class Stripes(val gridDims: Dimensions) {
  var b = 0
  def step(): Unit = b = 1 - b
  def getCellType(p: Point): CellType =
    if (p.y % 2 == b) SnakeBody() else Empty()
}

######   ......   ######
......   ######   ......
######   ......   ######
......   ######   ......
######   ......   ######

class Blink(val gridDims: Dimensions) {
  var on = true
  def step(): Unit = on = !on
  def getCellType(p: Point): CellType =
    if (on && p.x + p.y == gridDims.width - 1) SnakeBody() else Empty()
}

.....#   ......   .....#
....#.   ......   ....#.
...#..   ......   ...#..
..#...   ......   ..#...
.#....   ......   .#....

class Bounce(val gridDims: Dimensions) {
  var x = 0
  var dir = 1
  def step(): Unit = {
    x = x + dir
    if (x == 0 || x == gridDims.width - 2) dir = -dir
  }
  def getCellType(p: Point): CellType =
    if (x <= p.x && p.x < x + 2) SnakeBody() else Empty()
}

##....   .##...   ..##..   ...##.   ....##   ...##.   ..##..

class KeyLogic(val gridDims: Dimensions) {
  var pending = false
  var col = 0
  def changeDir(d: Direction): Unit = pending = true
  def step(): Unit = {
    if (pending) col = (col + 1) % gridDims.width
    pending = false
  }
  def getCellType(p: Point): CellType = if (p.x == col) SnakeBody() else Empty()
}

#.....   #.....   .#....   .#....   .#....

Two kinds of change

There are two completely separate ways something can "change" in a program, and most exam mistakes come from mixing them up:

1. The variable changes: a var is re-pointed to a different value (v = v :+ 3). Only that one name is affected.
2. The object changes: the contents of a mutable object are modified (arr(0) = 9, buf += 1, p.x += 1). Every name that points to that object sees it.

Immutable data is data that can only be created, never changed: List, Vector, the default Map and Set, String, Int, tuples, case classes with val fields. Mutable data can be changed in place: Array, ArrayBuffer, ListBuffer, mutable.Map/Set, classes with var fields. That gives four combinations:

var b1 = Vector(1, 2)
val bOld = b1
b1 = b1 :+ 3              // kind 1: re-point b1
println((b1, bOld))
val c1 = Array(1, 2)
val cAlias = c1
c1(0) = 9                 // kind 2: change the object
println((c1.toList, cAlias.toList))
var d1 = Array(1, 2)
val dAlias = d1
d1(0) = 9                 // kind 2: dAlias sees it
d1 = Array(5)             // kind 1: dAlias does not follow
println((d1.toList, dAlias.toList))

(Vector(1, 2, 3),Vector(1, 2))
(List(9, 2),List(9, 2))
(List(5),List(9, 2))

Why prefer immutable data (from the slides): easier to reason about, more flexible (you can keep every past version, as in Snake's reverse mode), fewer bugs (no hidden change, no forgotten copy), thread safe. The price: sometimes slower, since changing means building a new version.

Immutable data: "changing" means making a new version

An immutable object has no operation that changes it. Methods that sound like changes (updated, :+, +, map, filter) return a new object and leave the old one exactly as it was. The slide puts it as: state of object = object. A new state is a new object.

This means a call like l.updated(1, "X") on its own line does nothing useful: it builds a new list and throws it away.

val l = List("a", "b", "c")
l.updated(1, "X")            // result thrown away
println(l)
val l2 = l.updated(1, "X")   // result kept
println(l)
println(l2)

List(a, b, c)
List(a, b, c)
List(a, X, c)

A pair: same program, immutable vs mutable map.

var m1 = Map("NL" -> "Amsterdam", "BE" -> "Antwerp")    // immutable Map
val m2 = m1
m1 = m1.updated("BE", "Brussels")       // new map; m1 re-pointed, m2 unchanged
println(m1("BE") + " " + m2("BE"))

val mm1 = scala.collection.mutable.Map("NL" -> "Amsterdam", "BE" -> "Antwerp")
val mm2 = mm1
mm1("BE") = "Brussels"                  // changes the one shared map
println(mm1("BE") + " " + mm2("BE"))

Brussels Antwerp
Brussels Brussels

Immutability is shallow. An immutable container only promises that its own slots never change. If a slot holds an arrow to a mutable object, that object can still be changed by anyone who has an arrow to it. updated copies arrows, not the objects behind them.

import scala.collection.mutable.ArrayBuffer
val buf = ArrayBuffer(1)
val v = Vector(buf, buf)                    // two arrows to ONE buffer
val v2 = v.updated(1, ArrayBuffer(100))     // new vector: slot 0 still the old buf
for (bb <- v2) bb += 5                      // mutates the buffers, not the vectors
println(v)
println(v2)

Vector(ArrayBuffer(1, 5), ArrayBuffer(1, 5))
Vector(ArrayBuffer(1, 5), ArrayBuffer(100, 5))

The same with a List of mutable objects. The val and the immutable List protect the list's structure, not the boxes it points to:

class Score(var points: Int)
def doubleAll(l: List[Score]): List[Int] = {
  l.foreach(s => s.points *= 2)       // mutates the caller's boxes
  l.map(_.points)
}
val scores = List(new Score(1), new Score(2))
println(doubleAll(scores))
println(scores.map(_.points))          // the original boxes were changed

case class CScore(points: Int)
def doubleAllC(l: List[CScore]): List[CScore] = l.map(s => CScore(s.points * 2))   // new boxes
val cscores = List(CScore(1), CScore(2))
println(doubleAllC(cscores))
println(cscores)                       // untouched

List(2, 4)
List(2, 4)
List(CScore(2), CScore(4))
List(CScore(1), CScore(2))

The key pair: an array of points, mutable vs immutable. The array is mutable in both programs; what differs is the point objects.

case class P(x: Int, y: Int) { def +(o: P): P = P(x + o.x, y + o.y) }   // immutable
val pa = new Array[P](4)
val start = P(1, 3)
for (i <- pa.indices) pa(i) = start              // 4 arrows to one immutable box
for (i <- pa.indices) pa(i) = pa(i) + P(0, i)    // each slot re-pointed to a NEW box
println(pa.map(_.y).sum)
println(start)

class MP(var x: Int, var y: Int) { def move(dx: Int, dy: Int): Unit = { x += dx; y += dy } }
val ma = new Array[MP](4)
val mstart = new MP(1, 3)
for (i <- ma.indices) ma(i) = mstart             // 4 arrows to one mutable box
for (i <- ma.indices) ma(i).move(0, i)           // all 4 moves go into that box
println(ma.map(_.y).sum)
println(mstart.y)

18
P(1,3)
36
9

Immutable: the slots end up with y = 3, 4, 5, 6 (sum 18), and the start point is unchanged. Mutable: the one box gets y = 3 + 0 + 1 + 2 + 3 = 9, and all four slots show it (sum 36).

"Depends on the definition of f". Some questions call a function f you cannot see and ask what is printed afterwards. Follow the path from the printed name to the value: if every step on that path is immutable, no f can change it. If some box on the path is mutable and f can reach it (it was passed in, or is global), the answer depends on f.

val arr = new Array[P](1)
arr(0) = P(5, 5)
val keep = arr(0)      // keep points to the immutable P(5,5)
arr(0) = P(10, 10)     // re-points the slot, not keep
// f(arr) here could only re-point slots of arr; it cannot touch P(5,5)
println(keep)

P(5,5)

Had we printed arr(0) after calling f(arr), the answer would depend on f, because an array slot can be re-pointed by anyone holding the array. Same for m(0)("key") when m is an Array[Map[...]]: the maps are immutable but the array is not.

var m1 = Map("NL" -> "Amsterdam", "BE" -> "Antwerp")
val m2 = m1
m1 = m1.updated("BE", "Brussels")
println(m1("BE") + " " + m2("BE"))

val buf = ArrayBuffer(1)
val v = Vector(buf, buf)
val v2 = v.updated(1, ArrayBuffer(100))
for (bb <- v2) bb += 5
println(v)
println(v2)

Immutable and mutable collections

Scala has both kinds in its library, in scala.collection.immutable and scala.collection.mutable. Without an import, List, Vector, Map, Set and Seq are the immutable ones. Array is always mutable.

The slides compare the two interfaces. Read the result types:

class ArrayBuffer[A] {                       // mutable
  def apply(i: Int): A
  def update(index: Int, elem: A): Unit      // Unit: it must change this object
  def +=(elem: A): Unit
}
class Vector[+A] {                           // immutable
  def apply(i: Int): A
  def updated(index: Int, elem: A): Vector[A]   // returns the new version
  def :+(elem: A): Vector[A]
}

A method that "changes" something but returns Unit can only do its job by mutating the object, so it cannot exist on an immutable type. Query methods (contains, get, size, apply) do not change anything and exist on both. The mutable Set has the same interface as the immutable one plus extra mutating methods.

val vv = Vector(1, 2)
println(vv :+ 3)
println(0 +: vv)
println(vv.updated(0, 10))
println(vv ++ Vector(7, 8))
println(vv)                      // never changed
val im = Map(1 -> "one")
println(im + (2 -> "two"))
println(im - 1)
println(im.get(1))
println(im.get(5))
println(im)                      // never changed

Vector(1, 2, 3)
Vector(0, 1, 2)
Vector(10, 2)
Vector(1, 2, 7, 8)
Vector(1, 2)
Map(1 -> one, 2 -> two)
Map()
Some(one)
None
Map(1 -> one)

+= means two different things. On a mutable collection it is a method that changes the object. On a var holding an immutable collection, Scala rewrites s += 3 into s = s + 3: a new set, and the name is re-pointed.

var s = Set(1, 2)
val before = s
s += 3                     // s = s + 3
println(before)
println(s)
val ms = scala.collection.mutable.Set(1, 2)
val msBefore = ms
ms += 3                    // changes the one set
println(msBefore)
println(ms)

Set(1, 2)
Set(1, 2, 3)
HashSet(1, 2, 3)
HashSet(1, 2, 3)

A common idiom: build a result in a local ListBuffer (fast appends), then return buf.toList. The caller only ever sees the immutable list. This is "functional on the outside, imperative on the inside" (see pure functions).

Reading the type of a collection pipeline. Some questions ask the type of something like val f = l => l.map(_.map(_ + 1).sum).filter(_ % 2 == 0).sum. (Real Scala refuses this line with "missing parameter type", because l has no type; the question means "the type it must have".) Work from the operations to the layers:

• _.map(_ + 1) applied to each element means each element is itself a collection of Int: so l is List[List[Int]].
• map and filter keep the number of layers; flatMap and flatten remove one; sum, max, length, exists remove the collection entirely; map(x => List(x)) adds one.

val f1: List[List[Int]] => Int = ll => ll.map(_.map(_ * 2).sum).filter(_ > 3).sum
println(f1(List(List(1, 2), List(1), List(5))))
val f2: List[List[Int]] => List[Int] = ll => ll.filter(_.nonEmpty).flatMap(_.map(_ + 1))
println(f2(List(List(1, 2), List(), List(5))))
val f3: List[List[Int]] => List[List[Int]] =
  ll => ll.map(_.filter(_ > 1)).filter(_.length >= 1).map(x => List(x.max))
println(f3(List(List(1, 2, 3), List(1), List(5))))

16
List(2, 3, 6)
List(List(3), List(5))

These compile with exactly these type annotations, which confirms the layer counting.

Case classes

A case class is a class for plain immutable data. Writing case in front of class gives you, for free:

• constructor parameters are val fields (so the class is immutable by default);
• a companion apply, so you write Point(1, 2) without new;
• == that compares the fields (structural equality), with a matching hashCode, so it works as a Set element or Map key by value;
• a readable toString: Point(1,2);
• a copy method with named arguments: p.copy(y = 5);
• support for pattern matching (Week 5).

class PlainPoint(val x: Int, val y: Int)
case class Point(x: Int, y: Int)
val p = Point(1, 2)
println(p)
println(p == Point(1, 2))                 // fields equal
val pp1 = new PlainPoint(1, 2)
val pp2 = new PlainPoint(1, 2)
println(pp1 == pp2)                       // plain class: different objects
val q = p.copy(y = 5)                     // new object, p unchanged
println((p, q))
val Point(a, b) = q                       // pattern: take the fields out
println(a + b)
println(Set(Point(1, 2), Point(1, 2)).size)
println(Set(pp1, pp2).size)

Point(1,2)
true
false
(Point(1,2),Point(1,5))
6
1
2

p.x = 3 does not compile ("reassignment to val"). "Immutable by default" is the precise phrase: you can write case class Counter(var n: Int), and then it is mutable:

case class Counter(var n: Int)
val cnt = Counter(1)
cnt.n += 1
println(cnt)

Counter(2)

A small taste of pattern matching, which is the main reason case classes exist:

def describe(pt: Point): String = pt match {
  case Point(0, 0) => "origin"
  case Point(x, 0) => "on the x-axis at " + x
  case _ => "somewhere else"
}
println(describe(Point(0, 0)) + "; " + describe(Point(4, 0)) + "; " + describe(q))

origin; on the x-axis at 4; somewhere else

Side effects and side causes

A function has a main cause (its arguments, the inputs you see) and a main effect (its return value, the output you see). The professor's terms for everything else:

• Side effect = hidden output. Anything the function does to the world other than returning a value: changing a variable outside the function (a global, a field), mutating an object that was passed in, printing, writing a file, "launching rockets".
• Side cause = hidden input. Anything the result depends on other than the arguments: reading a global var or a field that can change, reading the contents of mutable data, the keyboard, a file, the clock, a random number generator.

Mutation is a side effect when anyone outside can see it. That is the link between Week 2's two halves: immutable data rules out a whole class of side effects.

Functions with memory. A function value (Week 3: closures) can capture a local var of the method that created it. That variable then lives on between calls, so calling the function changes hidden state: a side effect and a side cause at once. Each new call of the maker creates a new variable.

def makeCounter(): () => Int = {
  var count = 0
  () => { count += 1; count }
}
val c1 = makeCounter()
println(c1()); println(c1())
val c2 = makeCounter()          // a fresh count for c2
println(c2()); println(c1())    // c1 continues with its own count

1
2
1
3

Side effects make evaluation order visible. When an expression prints, it matters when and how often it is evaluated. That is why val, lazy val and def questions (Week 3 covers them in depth) use print: a val runs once at its definition, a lazy val once at its first use, a def at every use.

def show(tag: String, v: Int): Int = { print(tag + " "); v }
val v1 = show("val", 1)
lazy val l1 = show("lazy", 2)
def d1 = show("def", 3)
println("|")
val sum = d1 + l1 + d1 + l1 + v1
println("|")
println(sum)

val |
def lazy def |
11

def make(start: List[Int]): Int => Int = {
  var q = start
  x => { val h = q.head; q = q.tail :+ x; h }
}
var r = make(List(7, 8))
print(r(1)); print(r(2)); print(r(3))
r = make(List(9))
print(r(4)); println(r(5))

78194

var q = List(7, 8)
def make(): Int => Int = x => { val h = q.head; q = q.tail :+ x; h }
var r = make()
print(r(1)); print(r(2)); print(r(3))
r = make()
print(r(4)); println(r(5))

78123

var n = 10
def bump(): Int = { n += 1; n }
lazy val a = bump()
val b = bump()
def c = bump()
println((c, a, b, a, c))

(12,13,11,13,14)

Pure functions

A mathematical function f : A -> B maps each input to exactly one output: same input, same output. A pure function is a mathematical function in this sense and has no side effects and no side causes. In the professor's words: functional programming = more pure functions, imperative programming = more impure functions, and the advice is "pure when possible, impure when needed".

Paper method: the purity checklist.

1. Does the result depend on anything other than the arguments (global var, mutable array contents, random, time, input)? Then impure (side cause).
2. Does it print, or change anything that still exists after it returns (globals, fields, the contents of an argument)? Then impure (side effect).
3. Does it call an impure function? Then impure.
4. Otherwise pure, even if it uses local vars, while or for loops, local arrays or ListBuffers, return, or recursion.

That last point is the slide "use of impure constructs does not have to leak": a sort that uses an array internally is still pure. Functional on the outside, imperative on the inside.

var total = 0
def addToTotal(x: Int): Int = { total += x; total }       // side effect + side cause
println(addToTotal(5)); println(addToTotal(5))           // same input, different output

def peek(arr: Array[Int]): Int = arr(0)                    // side cause: mutable contents
val arr = Array(1)
println(peek(arr)); arr(0) = 50; println(peek(arr))       // same argument, different output

def bump(arr: Array[Int]): Int = { arr(0) += 1; arr(0) }  // side effect on the argument
val arr2 = Array(1)
println(bump(arr2)); println(bump(arr2))

def sumList(l: List[Int]): Int = {                         // pure: local var only
  var res = 0
  for (e <- l) res += e
  res
}
println(sumList(List(1, 2, 3))); println(sumList(List(1, 2, 3)))

def evens(n: Int): Seq[Int] = {                            // pure: local buffer only
  val buf = scala.collection.mutable.ListBuffer[Int]()
  for (i <- 0 until n) if (i % 2 == 0) buf += i
  buf.toList
}
println(evens(7)); println(evens(7))

5
10
1
50
2
3
6
6
List(0, 2, 4, 6)
List(0, 2, 4, 6)

Classifying typical exam functions.

What purity guarantees, and what it does not. Purity guarantees: evaluating f(x) twice gives the same result and changes nothing; f prints nothing; equal inputs give equal outputs; laws like xs.map(f).map(f) == xs.map(x => f(f(x))) hold. Purity says nothing about the mathematical shape of f:

val plus1: Int => Int = _ + 1          // pure
println((plus1(plus1(3)), plus1(3)))      // f(f(x)) == f(x)?  no: not idempotent
println((plus1(2 + 3), plus1(2) + plus1(3)))   // f(x+y) == f(x)+f(y)?  no
val zero: Int => Int = _ => 0           // pure
println((zero(1), zero(2)))               // f(x) == f(y) implies x == y?  no

(5,4)
(6,7)
(0,0)

One more guarantee that the exam likes: a call to a pure function can be moved past impure calls. In val y = f(x); val z = g(x); h(y, z) with pure f, swapping the first two lines changes nothing, because f neither reads what g might change nor changes what g might read.

var factor = 2
def scale(x: Int): Int = x * factor
def scale2(x: Int, factor: Int): Int = x * factor
println(scale(5)); factor = 3; println(scale(5))
println(scale2(5, 3)); println(scale2(5, 3))

10
15
15
15

def incr(a: Array[Int]): List[Int] = {
  for (i <- a.indices) a(i) += 1
  val res = scala.collection.mutable.ListBuffer[Int]()
  for (e <- a) res.addOne(e * 2)
  res.toList
}

Referential transparency

An expression is referentially transparent if you can replace it by its result without changing the meaning of the program. Math.sin(0) can be replaced by 0.0 everywhere. printId(9), which prints and returns 9, cannot be replaced by 9: you would lose the printing. Calls to pure functions on immutable values are referentially transparent; calls with side effects or side causes are not.

def printId(a: Int): Int = { println("printing " + a); a }
val r1 = printId(9) + printId(9)    // two prints
val nine = printId(9)
val r2 = nine + nine                // one print
println((r1, r2))

printing 9
printing 9
printing 9
(18,18)

The values are equal but the programs are not: one printed twice, the other once. So "compute once and reuse" is only safe for referentially transparent expressions.

Even e == e can be false. If evaluating e changes or reads changing state, the two sides of == are two different evaluations:

var n = 0
def next(): Int = { n += 1; n }
println(next() == next())          // 1 == 2
val once = next()
println(once == once)              // one evaluation, compared with itself
val dbl: Int => Int = _ * 2        // pure
n = 0
println(dbl(next()) == dbl(next()))  // pure outside does not help: 2 == 4
println(dbl(dbl(4)) == dbl(dbl(4)))  // only pure calls: always true

false
true
false
true

So, with f pure and g possibly impure: f(g(x)) == f(g(x)) may be false (a pure f faithfully maps two different g results to two different values), g(f(x)) == g(f(x)) may be false (g is still called twice), and f(f(x)) == f(f(x)) is always true.

Rewriting a function with pure and impure calls. Questions show a function like m below and ask which rewrites always give the same result. The rules: you may reuse, duplicate, or move calls to the pure function. You may not change the number or order of calls to the impure function, and you may not reuse one impure result in place of a second call. And purity does not relate different arguments: p(x + 1) is not p(x) + 1.

var calls = 0
def im(x: Int): Int = { calls += 1; x * calls }     // impure
def pz(x: Int): Int = x * 10                        // pure
def m(x: Int): Int  = { val a = pz(x); val b = im(x); val c = pz(x); a + b + c }
def m1(x: Int): Int = { val b = im(x); 2 * pz(x) + b }        // pure calls merged and moved
def m2(x: Int): Int = { val a = pz(x); val b = im(x); a + b + a }   // pure result reused
def m3(x: Int): Int = { val b = im(x); b + b + pz(x) }        // WRONG: im result used twice
def m4(x: Int): Int = pz(x) + im(x) + pz(x + 0)               // same calls, same order
// each called three times with x = 1, counter reset before each:

m: List(21, 22, 23)
m1: List(21, 22, 23)
m2: List(21, 22, 23)
m3: List(12, 14, 16)
m4: List(21, 22, 23)

Equational reasoning: laws for pure code

Equational reasoning means reasoning about programs like algebra: you replace equals by equals. Because a pure expression can be replaced by its value (referential transparency), you can rewrite pure code step by step and know the result does not change. The slide example: for all lists, (a ++ b) ++ c == a ++ (b ++ c).

The laws you need (f, g pure; p, q pure predicates, that is functions returning Boolean):

And the non-laws: l.map(f).map(g) is not l.map(g).map(f), and l.filter(p).map(f) is not l.map(f).filter(p) (the filter would test different values).

val xs = List(1, 2, 3, 4, 5, 6)
val f: Int => Int = _ + 1
val g: Int => Int = _ * 3
val even: Int => Boolean = _ % 2 == 0
val big: Int => Boolean = _ > 3
println(xs.map(f).map(g) + " " + xs.map(x => g(f(x))))
println(xs.map(f).map(g) + " " + xs.map(g).map(f))
println(xs.filter(even).filter(big) + " " + xs.filter(x => even(x) && big(x)))
println(xs.map(g).filter(big) + " " + xs.filter(x => big(g(x))).map(g))
println(xs.filter(even).map(f) + " " + xs.map(f).filter(even))

List(6, 9, 12, 15, 18, 21) List(6, 9, 12, 15, 18, 21)
List(6, 9, 12, 15, 18, 21) List(4, 7, 10, 13, 16, 19)
List(4, 6) List(4, 6)
List(6, 9, 12, 15, 18) List(6, 9, 12, 15, 18)
List(3, 5, 7) List(2, 4, 6)

Lines 1, 3 and 4 are laws (equal). Lines 2 and 5 are the non-laws (different).

Paper method for "which are equivalent?"

1. Types first. Does the candidate even have the same type? for (x <- l if f(x)) yield true is a List[Boolean], not a Boolean; a nested yield inside a yield gives a nested list where flatMap gives a flat one.
2. Rewrite with the laws until both sides look alike. Check the order of composition (g(f(x)) vs f(g(x))), && vs ||, exists vs forall.
3. Test small cases: an empty list, a list where the predicate holds for some but not all elements, and simple functions like _ + 1 and _ * 3. One counterexample kills a candidate.

println(List(4).map(f).filter(even).exists(big) + " " +
        List(4).exists(x => even(f(x)) && big(f(x))) + " " +
        List(4).exists(x => even(f(x)) || big(f(x))))
println(List(3, 4, 5, 6).filter(even).forall(big) + " " +
        List(3, 4, 5, 6).forall(x => !even(x) || big(x)) + " " +
        List(3, 4, 5, 6).forall(big))

false false true
true true false

The || candidate and the "forget the filter" candidate are each killed by one small list.

Loops versus library functions. The same method checks "which implementations equal this loop?":

def countIf[A](l: List[A], f: A => Boolean): Int = { var res = 0; for (e <- l) if (f(e)) res += 1; res }
println((countIf(xs, big), xs.filter(big).length, xs.count(big),
         xs.map(big).length, xs.map(x => if (big(x)) 1 else 0).sum))
def allOf[A](l: List[A], f: A => Boolean): Boolean = { for (e <- l) if (!f(e)) return false; true }
println((allOf(xs, big), xs.map(big).fold(true)(_ && _), xs.filter(big).length == xs.length))
println((allOf(List[Int](), big), List[Int]().forall(big), List[Int]().exists(big)))
println((List(1, 2).map(big).length > 0, List(1, 2).exists(big)))

(3,3,3,6,3)
(false,false,false)
(true,true,false)
(true,false)

xs.map(big).length is 6: map keeps the length, so it counts everything, and l.map(f).length > 0 only tests "is the list non-empty", ignoring f. On the empty list forall is true and exists is false, which is why fold(true)(_ && _) needs true as start value (with false it is always false).

Laws break for impure functions. With side effects, l.map(f).map(g) runs all f calls and then all g calls (f1 f2 f3 g1 g2 g3), while l.map(x => g(f(x))) interleaves them (f1 g1 f2 g2 f3 g3). The hidden state is different at each call:

var k = 0
def fi(x: Int): Int = { k += 1; x * k }
def gi(x: Int): Int = { k += 10; x + k }
val l3 = List(1, 2, 3)
k = 0
val fused = l3.map(x => gi(fi(x)))
k = 0
val separate = l3.map(fi).map(gi)
println(fused)
println(separate)

List(12, 46, 102)

List(14, 27, 42)

Filters break the same way, with one extra twist: in filter(x => p(x) && q(x)), && short-circuits: q is not called at all when p is false. So even the number of calls differs.

var t = 0
def ping(x: Int): Boolean = { t += 1; t % 2 == 0 }
def pong(x: Int): Boolean = { t += 1; t % 3 == 0 }
val l4 = List(1, 2, 3, 4, 5, 6)
t = 0
println((l4.filter(ping).filter(pong), t))
t = 0
println((l4.filter(x => ping(x) && pong(x)), t))

(List(6),9)
(List(2, 5),11)

Readable code (assignment grading, and why the exam code looks the way it does)

The professor's framing: assignments train you to write readable code, the exam trains you to read unreadable code. Exam programs deliberately use names like m1, b, nub and reuse names to test your scoping skills. For your own code, and for possible statement questions, these are the points from the slides:

• Easy to understand is hard to make. Code is mainly for people; readability beats performance in most contexts. Technical debt (quick and dirty now) costs more later.
• Constants instead of magic numbers: CellWidthInPixels instead of 10. Easier to read and to change in one place (avoids "shotgun surgery": one conceptual change, many edits).
• Meaningful, pronounceable names that say why something exists and how it is used. Short names for small scopes, longer names for large scopes. Standard abbreviations (gcd) are fine.
• Functions do one thing, at one level of abstraction, and their name mentions every effect (checkPassword that also initialises a session is a hidden side effect).
• Comments explain what code cannot (why, references to papers or bug numbers), never restate the code.
• Code smells: duplicated code, long functions, deep nesting, large classes, inappropriate intimacy with another class's internals.
• Common flaws (lecture 2): premature optimisation (needs a measurement), premature generalisation (YAGNI: "you ain't gonna need it"), reinventing the wheel (use the library's lists and sorts), global variables, the boolean antipattern if (bla) true else false instead of just bla, and not grouping data that belongs together into a class (Coordinate instead of separate x and y, a GameState class instead of a tuple of loose values). Mantras: DRY, KISS, YAGNI.

Local functions and scope

A local function (the exam also says nested function) is a def written inside the body of another def. It only exists inside that body, just like a local variable. The slides give two reasons to use one:

• It hides the helper from the rest of the program (a bit like private).
• It saves argument passing: the local function can read (and change) the parameters and local variables of the function around it, so you do not have to pass them in.

def report(name: String, limit: Int): Unit = {
  def check(score: Int): Unit =
    if (score > limit) println(s"$name: $score")   // uses name and limit from outside
  check(40); check(75)
}
report("Ann", 50)

Ann: 75

check only takes score. It reads name and limit straight from report. Those are called the surrounding scope: the region of code where a name is visible.

Which variable does a name mean? (shadowing)

When two variables have the same name, the one declared closest around the use wins. The outer one is shadowed: still there, untouched, just not reachable by that name. A parameter also counts as a declaration. This is where most exam questions about local functions hide their trick.

Paper method: arrows, then a state table. For every name in the code, draw an arrow to the declaration it means (search outward: own parameters, own locals, enclosing function, then top level). Then run the code with one column per declaration (not per name).

var a = 10
var b = 1
def outer(n: Int): Int = {
  var a = n                                    // a NEW local a, shadows the top-level a
  def inner(b: Int): Int = { a += b; b * 2 }   // b is inner's parameter; a is outer's local a
  b += inner(b)                                // here b is the top-level b
  b += inner(b)
  a                                            // outer's local a
}
val r = outer(5)
println(r + " " + a + " " + b)

9 10 9

Note that b += inner(b) means b = b + inner(b): the old b is read first, then inner runs. Here inner does not touch the top-level b (its own b is a parameter), so the order does not change anything.

var a2 = 10
var b2 = 1
def outer2(n: Int): Int = {
  a2 = n                                         // no var: assigns the top-level a2
  def inner(b2: Int): Int = { a2 += b2; b2 * 2 }
  b2 += inner(b2)
  b2 += inner(b2)
  a2
}
val r2 = outer2(5)
println(r2 + " " + a2 + " " + b2)

9 9 9

def g(): Int = {
  var base = 1
  def h(x: Int) = x + base
  val a = h(10)
  base = 5
  a + h(10)
}
println(g())

26

var y = 100
def outer(y: Int): Int = { def inner(x: Int) = x + y; inner(1) }
println(outer(2) + y)

103

First class functions: functions are values

A value is anything you can put in a variable: 3, "hi", a List. Saying functions are first class means a function is a value too. The slides list what you can then do with it:

• store it in a variable (var increase: Int => Int = plusOne),
• pass it as an argument (list.map(f), button.onClick(f)),
• return it as the result of a function (makeDiscount(0.9) returns a discount function),
• keep it as a field of a class (class KeyBinding(val key: String, var action: () => Unit)).

Function types

Every function value has a function type, written with an arrow:

Methods versus function values

A def double(x: Int): Int is a method. Scala turns it into a function value automatically when a function type is expected; this is called eta-expansion. If no function type is expected, Scala 2.13 refuses, and you write double _ or double(_).

def double(x: Int): Int = x * 2
val f1: Int => Int = double     // function type expected: fine
val f2 = double _                // explicit
val f3 = double(_)               // placeholder, same thing
println((f1(4), f2(4), f3(4)))

var op: (Int, Int) => Int = _ + _
println(op(3, 4))
op = _ * _                       // the variable now holds another function
println(op(3, 4))

(8,8,8)
7
12

Without the type annotation, val f = double does not compile: error: missing argument list for method double. Unapplied methods are only converted to functions when a function type is expected.

A function value of type () => Unit is only run when you write the brackets:

val hello: () => Unit = () => println("hi")
println(hello)     // prints the function object itself
hello()            // runs it

Main$$anon$1$$Lambda/0x000000d0014e5920@ee21292
hi

Data structures made of functions

The lecture builds a set as a function: type Set = Int => Boolean. A set is its membership test: "give me a number, I tell you whether it is in me". The exam reuses this idea for multisets (A => Int), maps (A => Option[B]), infinite lists (Int => A) and lists (case class FList(elems: Int => A, length: Int)). The method is always the same:

1. Write down what the function type means in words ("given an index, the element at that index").
2. The operation you have to build returns a new function, so its body is a lambda x => ... (or a local def that is returned).
3. Inside, answer the question for one argument x by asking the old functions about x (or about a shifted index).

type ISet = Int => Boolean
val evens: ISet = _ % 2 == 0
def range(lo: Int, hi: Int): ISet = x => lo <= x && x < hi
def diff(a: ISet, b: ISet): ISet = x => a(x) && !b(x)
val s = diff(range(0, 10), evens)
println((0 to 12).filter(s).toList)

List(1, 3, 5, 7, 9)

A list as a function, with an index shift (the same trick as "prepend" or "merge" questions):

case class Seq2[A](at: Int => A, size: Int) {
  def append(e: A): Seq2[A] = Seq2(i => if (i == size) e else at(i), size + 1)
  def reverse: Seq2[A] = Seq2(i => at(size - 1 - i), size)
  def toList: List[A] = (0 until size).map(at).toList
}
val sq = Seq2[Int](i => i * 10, 3)
println((sq.toList, sq.append(7).toList, sq.reverse.toList, sq.append(7).reverse.toList))

(List(0, 10, 20),List(0, 10, 20, 7),List(20, 10, 0),List(7, 20, 10, 0))

type Phone = String => Option[Int]
val empty: Phone = _ => None
def add(m: Phone, k: String, v: Int): Phone = x => if (x == k) Some(v) else m(x)
val book = add(add(empty, "ann", 1), "bob", 2)
val book2 = add(book, "ann", 9)
println((book("ann"), book("bob"), book("cy"), book2("ann"), book("ann")))

(Some(1),Some(2),None,Some(9),Some(1))

type Inf = Int => Int
val nat: Inf = i => i
def shift(a: Inf, k: Int): Inf = i => a(i + k)
def every2(a: Inf): Inf = i => a(2 * i)
println((0 to 4).map(every2(shift(nat, 1))).toList)

List(1, 3, 5, 7, 9)

type ISet = Int => Boolean
def single(e: Int): ISet = _ == e
def union(a: ISet, b: ISet): ISet = x => a(x) || b(x)
def inter(a: ISet, b: ISet): ISet = x => a(x) && b(x)
val u = union(single(3), x => x > 10)
println((u(3), u(4), u(11), inter(u, _ % 2 == 0)(12), inter(u, _ % 2 == 0)(3)))

(true,false,true,true,false)

Lambdas (anonymous functions, function literals)

A lambda is a function written directly as an expression, without a name. The slides also call it an anonymous function or function literal, just like 3 is an Int literal.

(x: Int) => x * x          // parameter list, arrow, body
(x: Int, y: Int) => x + y  // two parameters
() => println("BOOM!")     // no parameters

You can apply a lambda directly, store it, or pass it:

println(((x: Int) => x * x)(7))
println(List(1, 2, 3).map(x => x * x))     // type of x inferred from the List
val describe: Int => String = n => {
  val half = n / 2                          // a block: the last expression is the result
  s"$n has half $half"
}
println(describe(9))

49
List(1, 4, 9)
9 has half 4

Parameter types. You may leave out : Int only when Scala already knows which function type is expected (from a type annotation, or from the parameter type of the method you pass it to). val g = x => x + 1 alone gives error: missing parameter type.

The body runs on every call. Anything declared inside the lambda body is created fresh each time the lambda is called. Anything declared outside it, but captured by it, lives on between calls. This pair shows the difference:

def mk(): Int => Int  = { var t = 0; x => { t += x; t } }   // t outside the lambda
def mk2(): Int => Int = x => { var t = 0; t += x; t }        // t inside the lambda
val m1 = mk(); val m2 = mk2()
println((m1(5), m1(5), m2(5), m2(5)))

(5,10,5,5)

val f: Int => Int = x => { val y = x * 2; y + 1 }
println(f(f(1)))

7

Higher order functions

A higher order function is a function that takes a function as an argument, returns a function, or both. map, filter and exists take one. makeDiscount(0.9) returns one. The slides use two famous ones that the exam uses in almost every paper:

def andThen[A,B,C](f: A => B, g: B => C): A => C = x => g(f(x))   // first f, then g
def compose[A,B,C](g: B => C, f: A => B): A => C = x => g(f(x))   // g "after" f
val inc: Int => Int = _ + 1
val dbl: Int => Int = _ * 2
println(andThen(inc, dbl)(5))
println(compose(inc, dbl)(5))
println(((inc andThen dbl)(5), (inc compose dbl)(5)))   // the library versions

12
11
(12,11)

andThen(inc, dbl): first +1, then *2: (5+1)*2 = 12. compose(inc, dbl) means inc after dbl: 5*2+1 = 11. Do not trust the name: some exam versions define their own after, at or comp. Always look at the body. x => g(f(x)) runs f first, whatever the function is called.

Paper method: the pipeline

1. For each helper, read its body once and write it as a left to right pipeline. andThen(f, g) becomes f ; g. after(f, g) with body f(g(x)) becomes g ; f.
2. Expand from the inside out until you have one flat list of small steps. A repeat helper (iterate(f, 3), twice(f)) becomes f ; f ; f.
3. Push the number through the list, writing every intermediate value.

def times[A](f: A => A, n: Int)(a: A): A = if (n == 0) a else times(f, n - 1)(f(a))
println(times(andThen(dbl, (_: Int) - 3), 3)(4))

11

Count the repeats carefully. times(f, 3) applies f exactly 3 times (n goes 3, 2, 1, then 0 returns). for (i <- 0 until n) also runs n times, because until excludes n.

Recognise a higher order function by its shape

Some questions show a function with a meaningless name and ask "what is the name of this higher order function?". Look at the type and the body:

println(andThen(times(inc, 2), times(dbl, 3))(1))

24

def chain(fs: List[Int => Int]): Int => Int =
  if (fs.isEmpty) x => x else andThen(fs.head, chain(fs.tail))
println(chain(List(_ + 3, _ * 2, _ - 1))(1))

7

def swapEach[A](f: A => A, g: A => A, n: Int)(a: A): A =
  if (n == 0) a else swapEach(g, f, n - 1)(f(a))
println(swapEach[Int](_ + 10, _ * 2, 4)(1))
def until[A](f: A => A, stop: A => Boolean)(a: A): A = if (stop(a)) a else until(f, stop)(f(a))
println(until[Int](_ * 3, _ > 50)(2))

64
54

def mystery[A](l: List[A], p: A => Boolean): Boolean = l match {
  case h :: t => p(h) || mystery(t, p)
  case Nil => false
}
println((mystery(List(1, 2, 3), (_: Int) > 2), mystery(List[Int](), (_: Int) > 2)))

(true,false)

Placeholder (_) notation

The slides: "nth occurrence of _ = nth argument". It is a short way to write a lambda:

Rule 1: every _ is a new parameter. You cannot use one parameter twice with underscores. _ * _ takes two arguments, so it fits reduce but not map:

println(List(1, 2, 3).map(_ * 10))
println(List(1, 2, 3).reduce(_ * _))     // reduce wants (Int, Int) => Int
val sub = (_: Int) - (_: Int)
println(sub(10, 3))
println(List(1, 2, 3).map(_ + -2))       // _ + -2 is x => x + (-2)

List(10, 20, 30)
6
7
List(-1, 0, 1)

List(1, 2, 3).map(_ * _) does not compile: type mismatch; found: (?, ?) => ? required: Int => ?.

Rule 2: how far does the lambda reach? Find the _ and walk outward. The lambda is the first enclosing argument (or right-hand side of =) that is bigger than the _ itself. If the _ is a whole argument on its own, like in g(_), the lambda grows one level further and includes the call g(...).

println(List(-3, 2).map(math.abs(_) + 1))
println(List(List(2, 4), List(1)).filter(_.forall(_ % 2 == 0)))
val pairUp: (Int, Int) => Int = inc(_) + dbl(_)
println(pairUp(5, 1))

List(4, 3)
List(List(2, 4))
8

And the one that fails: List(1, 2).map(dbl(inc(_))) gives type mismatch; found: Int => Int required: Int, because dbl receives the function x => inc(x) instead of a number. To use a parameter in two places, or inside a nested call, write the lambda out: x => inc(x) + dbl(x), x => dbl(inc(x)).

34

Mutability and first class functions: closures

A lambda's body can mention variables it did not declare itself. In (x: Int) => x + diff, x is the lambda's own parameter, but diff comes from outside. The slides call diff a free variable: a variable introduced in an outer scope. The function value that exists at runtime is a closure: "the definition of the function + bindings of the free variables". The name comes from "closing" the function: giving its free variables a meaning.

The question the exam keeps asking is: what exactly is bound, the value or the variable? The slides answer it: "Variable itself is being captured, not its value."

Rule 1: a captured var is read when the function runs

var rate = 2
val pay: Int => Int = h => h * rate
println(pay(10)); rate = 3; println(pay(10))

20
30

The closure holds a link to the variable rate, not a copy of 2. At the second call the variable holds 3. Same code, one small change: capture a val copy instead.

var rate2 = 2
val frozen = rate2                  // copies the current value 2
val pay2: Int => Int = h => h * frozen
println(pay2(10)); rate2 = 3; println(pay2(10))

20
20

Parameters are vals too. In def adder(n: Int): Int => Int = x => x + n the value of n can never change, so adder(5) always adds 5. And a result that was already computed is just a number: after val snapshot = addK(0), changing k does not change snapshot.

Rule 2: each call of the maker creates a new variable

When a function declares a var and returns a lambda that uses it, every call of that function makes a new var and a new closure linked to it. The closure keeps that variable alive after the function has returned. Calling the closure changes its own variable and nobody else's.

def counter(): () => Int = { var c = 0; () => { c += 1; c } }
val c1 = counter()
val c2 = counter()
var c3 = c1                     // NOT a copy: c3 and c1 point to the same closure
println((c1(), c1(), c2(), c3(), c1()))
c3 = counter()                  // c3 now points to a brand new closure
println((c3(), c1()))

(1,2,1,3,4)
(1,5)

Paper method: boxes and arrows. Draw a box for every variable that a closure captures, created at the moment the maker runs. Draw every closure as a circle with an arrow to its box. Variables like c1 hold arrows to circles. Assignment c3 = c1 copies the arrow, never the circle or the box.

After the first line: closure #1 was called three times (twice through c1, once through c3), so its box went 1, 2, then 3 via c3, then 4. Closure #2 was called once.

Rule 3: where the var lives decides who shares it

var shared = 100
def mkShared(): () => Int = () => { shared += 1; shared }
val s1 = mkShared(); val s2 = mkShared()
println((s1(), s2(), s1()))

(101,102,103)

Another way to see it: a loop that captures

A for (i <- 1 to 3) loop makes a new val i for every round. A while loop with one var j has one variable for all rounds. If closures capture the loop variable, you see the difference when you call them later:

import scala.collection.mutable.ArrayBuffer
val fs = ArrayBuffer[() => Int]()
for (i <- 1 to 3) fs += (() => i)
println(fs.map(f => f()).toList)

val gs = ArrayBuffer[() => Int]()
var j = 1
while (j <= 3) { gs += (() => j); j += 1 }
println(gs.map(g => g()).toList)

List(1, 2, 3)
List(4, 4, 4)

All three closures in gs share the single j, and they read it when they are called, after the loop ended with j = 4.

The same rule for objects

A closure with a captured var is just an object with a private field. Iterators in past questions behave the same way: every call of r.iterator (or new PrmIterator()) creates a new object with its own cur, while val it2 = it1 is a second name for the same object, so both names advance one shared cursor. And a val that holds a mutable object (like an ArrayBuffer or an Array) still lets a closure change what is inside that object.

def rotor(start: List[Int]): Int => Int = {
  var q = start
  x => { val out = q.head; q = q.tail :+ x; out }
}
val ro = rotor(List(7, 8))
println((ro(1), ro(2), ro(3), ro(4)))

(7,8,1,2)

def window(n: Int): Int => Int = {
  val a = new Array[Int](n)
  var i = 0
  x => { a(i) = x; i = (i + 1) % n; a.sum }
}
val w = window(2)
println((w(5), w(6), w(7)))

(5,11,13)

def tickDef: () => Int = { var c = 0; () => { c += 1; c } }
val tickVal: () => Int = { var c = 0; () => { c += 1; c } }
println((tickDef(), tickDef(), tickVal(), tickVal()))

(1,1,1,2)

def acc(x: Int): Int => Int = {
  var total = x
  x => { total += x; total }
}
val ac = acc(100)
println((ac(1), ac(2)))

(101,103)

Nested classes

Just as you can put a def inside a def, you can put a class inside a class. The slides: "exact same rules". An object of the inner class can read and change the fields and methods of the outer object it was created from.

The key word is object. You create an inner object through a specific outer object: new ajax.Player(9). That inner object stays linked to ajax forever. Its type is ajax.Player; the slides call this a path dependent type: the type of an inner class depends on the enclosing object.

class Team(val name: String) {
  var goals = 0
  class Player(val nr: Int) {
    var own = 0
    def score(): Unit = { own += 1; goals += 1 }   // goals = the goals of MY team
  }
}
val ajax = new Team("Ajax"); val psv = new Team("PSV")
val p1 = new ajax.Player(9); val p2 = new ajax.Player(10); val p3 = new psv.Player(7)
p1.score(); p2.score(); p1.score(); p3.score()
println((ajax.goals, psv.goals, p1.own, p2.own, p3.own))

(3,1,2,1,1)

Paper method: boxes with an "outer" arrow. Draw a box per outer object with its fields. Draw a box per inner object with its own fields plus an arrow labelled "outer" to the box it was created from. A name in the inner class body that is not its own field follows the outer arrow. Variables that are aliases (val t2 = ajax) are just two arrows to the same box.

Each inner object has its own inner fields (own), and all inner objects of the same outer object share that outer object's fields (goals). Different outer objects (ajax, psv) have separate fields.

Aliasing the outer object does not make a new one:

val t2 = ajax
val p4 = new t2.Player(11)
p4.score()
println((ajax.goals, t2.goals, psv.goals))

(4,4,1)

The types really are different per object: val p: ajax.Player = new psv.Player(7) gives error: type mismatch; found: this.psv.Player required: this.ajax.Player.

Inner objects that change a function field of the outer object

This combines nested classes with closures. Watch the line val old = run: it saves the current function value before replacing it.

class Pipeline(var run: Int => Int) {
  class Stage(val step: Int => Int) {
    def attach(): Unit      = { val old = run; run = x => step(old(x)) }   // old first, then step
    def attachFront(): Unit = { val old = run; run = x => old(step(x)) }   // step first, then old
  }
}
val pa = new Pipeline(_ * 10)
new pa.Stage(_ + 1).attach()
new pa.Stage(_ * 2).attach()
println(pa.run(1))
val pb = new Pipeline(_ * 10)
new pb.Stage(_ + 1).attachFront()
new pb.Stage(_ * 2).attachFront()
println(pb.run(1))

22
30

pa: run becomes *10 ; +1, then *10 ; +1 ; *2: 1, 10, 11, 22. pb: each new stage goes in front: +1 ; *10, then *2 ; +1 ; *10: 1, 2, 3, 30. Both stages belong to the same outer object, so they both change the same run.

Now delete val old = run and write run = x => step(run(x)). The lambda captures the variable run, reads it at call time, and by then run is the lambda itself. It calls itself forever:

StackOverflowError

class Bank(var total: Int) {
  class Account(var bal: Int) {
    class Card(val limit: Int) {
      def pay(): Int = { bal -= limit; total -= limit; total }
    }
  }
}
val bk = new Bank(100)
val acc = new bk.Account(50)
val card = new acc.Card(10)
println(card.pay())
println(card.pay())
val card2 = new acc.Card(5)
println(card2.pay())
val acc2 = new bk.Account(20)
val card3 = new acc2.Card(1)
println(card3.pay())
println((bk.total, acc.bal, acc2.bal))

90
80
75
74
(74,25,19)

Additional argument lists

A method can have more than one pair of brackets with parameters. Each pair is an argument list (or parameter list). You call it with the same groups:

def plus(x: Int, y: Int): Int = x + y        // one list with two parameters: plus(2, 3)
def cplus(x: Int)(y: Int): Int = x + y       // two lists with one each:      cplus(2)(3)
def plus3(x: Int)(y: Int)(z: Int): Int = x + 10 * y + 100 * z
println(plus3(1)(2)(3))

321

The grouping is strict. The compiler rejects the other shape:

• plus(2)(3): not enough arguments for method plus: (x: Int, y: Int): Int. Unspecified value parameter y.
• cplus(2, 3): too many arguments (found 2, expected 1) for method cplus: (x: Int)(y: Int): Int

Why bother? The slides give three reasons. (1) It is the curried form (next topics). (2) It makes partial application easy. (3) It helps type inference: Scala works out the type parameters list by list, so a lambda in a later list already knows its parameter type.

def applyTo[A](a: A)(f: A => A): A = f(a)
println(applyTo(3)(x => x + 1))           // A = Int is known before the lambda is checked
println(applyTo("ab") { s => s + s })     // a last argument list can use braces

4
abab

With one list, def applyTo2[A](a: A, f: A => A), the call applyTo2(3, x => x + 1) fails with missing parameter type: A is not known yet when the lambda is checked.

def applyTo[A](a: A)(f: A => A): A = f(a)
def applyTo2[A](a: A, f: A => A): A = f(a)
applyTo(3)(x => x + 1)
applyTo2(3, x => x + 1)

Partially applied functions

Partial application means: give a function only some of its arguments, and get back a function that waits for the rest. The slides: cplus(2) is "a function with one argument filled in", equivalent to (y: Int) => 2 + y. The result is called a partially applied function.

def plus(x: Int, y: Int): Int = x + y
def cplus(x: Int)(y: Int): Int = x + y
def rplus(x: Int): Int => Int = y => x + y
val vplus: Int => Int => Int = x => y => x + y

val add2a: Int => Int = cplus(2)    // curried method + expected type
val add2b = cplus(2) _               // curried method + explicit _
val add2c = rplus(2)                 // method that returns a function: no _ needed
val add2d = vplus(2)                 // function value: no _ needed
val add2e = plus(2, _)               // non-curried: placeholder for the missing argument
println((add2a(10), add2b(10), add2c(10), add2d(10), add2e(10)))
val both = plus(_, _)
println(both(4, 5))

(12,12,12,12,12)
9

Note: val e1 = cplus(2) without type and without _ is refused in Scala 2.13: missing argument list for method cplus. With rplus(2) it is fine, because rplus(2) is a complete call that simply returns a function.

With three lists you can stop after any of them:

def plus3(x: Int)(y: Int)(z: Int): Int = x + 10 * y + 100 * z
val p1: Int => Int => Int = plus3(1)
val p12: Int => Int = plus3(1)(2)
println((p1(2)(3), p12(3)))

(321,321)

When is the given argument evaluated?

A subtle point about side effects. With cplus(next()) _, Scala evaluates next() once, when the partially applied function is made. With the placeholder form plus(next(), _), the whole call (including next()) is inside the lambda, so it runs on every call.

var n = 0
def next(): Int = { n += 1; n * 100 }
val g1 = cplus(next()) _
println((n, g1(1), g1(1), n))
val g2 = plus(next(), _)
println((n, g2(1), g2(1), n))

(1,101,101,1)
(1,201,301,3)

Currying and reading function types

A function of two arguments normally takes them together: plus: (Int, Int) => Int, "give me a pair of Ints, I give you an Int". The curried version takes them one at a time: cplus: Int => (Int => Int), "give me an Int, and I will give you a function from Int to Int". You call it as cplus(2)(3) instead of plus(2, 3). Every function of two arguments can be curried.

The arrow is right associative

The slides: "(=>) is right associative". That means missing brackets are always filled in from the right:

Paper method: peel off the top-level arrow. Find the first => that is not inside brackets. Left of it is the first argument (group); right of it is what you get back. Repeat on the right part. Each peel is one pair of call brackets.

Example: ((Int, Int) => Int) => Int => Int. Peel 1: argument (Int, Int) => Int, a two-argument function like _ + _. Peel 2: argument Int. Result Int. So the call shape is b(_ + _)(2).

Moving arguments across the = sign

The slides show that you can move each argument from the left of = (as a parameter) to the right (as a lambda), and the result is equivalent. All of these have the curried type (Int => Int) => Int => Int and are all called as h(f)(x):

def h1: (Int => Int) => Int => Int = f => x => f(f(x))   // both arguments on the right
def h2(f: Int => Int): Int => Int = x => f(f(x))           // f on the left, x on the right
def h3(f: Int => Int)(x: Int): Int = f(f(x))               // both on the left, two lists
val asType: List[(Int => Int) => Int => Int] = List(h1, h2, h3)
println(asType.map(h => h(_ + 1)(0)))
println((h1(_ * 3)(1), h2(_ * 3)(1), h3(_ * 3)(1)))

List(2, 2, 2)
(9,9,9)

Not equivalent: def h(f: Int => Int, x: Int): Int (one list: called h(f, x)) and def h: Int => Int => Int => Int (first argument is an Int, not a function).

The same works when the first group has two parameters. def b: (Int => Int, Int) => Int => Int peels to "first (f, x) together, then a", so its equivalents are def b(f: Int => Int, x: Int): Int => Int and def b(f: Int => Int, x: Int)(a: Int): Int, both called b(f, x)(a). Splitting f and x into separate lists changes the grouping and is not equivalent.

Which functions are "curried"?

(ab##,ab##,ab##)

def k1: ((Int, Int) => Int) => Int => Int = f => x => f(x, x)
def k2(f: (Int, Int) => Int): Int => Int = x => f(x, x)
println((k1(_ + _)(4), k2(_ * _)(4)))

(8,16)

Converting: curry and uncurry

You can write higher order functions that convert between the two forms. Look at their types, because the types decide what you may pass in:

def curry[A,B,C](f: (A, B) => C): A => B => C = a => b => f(a, b)     // in: uncurried, out: curried
def uncurry[A,B,C](f: A => B => C): (A, B) => C = (a, b) => f(a)(b)  // in: curried,   out: uncurried

curry only accepts a two-argument function; uncurry only accepts a curried one. A method is converted to the right function value automatically (eta-expansion), so curry(plus) and uncurry(rplus) and even uncurry(cplus) work.

val tl: (Int, Int) => Int = _ - _
val cl: Int => Int => Int = curry(tl)
println((cl(10)(3), uncurry(cl)(10, 3), curry(plus)(10)(3), uncurry(rplus)(10, 3), curry(uncurry(cl))(10)(3)))
val u2 = uncurry(cplus)
println(u2(1, 2))

(7,7,13,13,7)
3

Passing the wrong form does not compile. curry(cl) gives type mismatch; found: Int => (Int => Int) required: (?, ?) => ?.

Curry and uncurry are each other's inverse: curry(uncurry(f)) behaves like f for a curried f, and uncurry(curry(g)) behaves like g for a two-argument g. The slides call these "complicated identity functions".

You will see curry written in many equivalent ways, and they are all curry: def p[A,B,C](f: (A,B) => C)(a: A)(b: B): C = f(a, b); def p[A,B,C]: ((A,B) => C) => A => B => C = f => a => b => f(a, b); def p[A,B,C](f: (A,B) => C)(a: A): B => C = b => f(a, b); or a local def q(a: A)(b: B) = f(a, b) returned as q. The test is the shape: the input is a two-argument function, after it the arguments come one per bracket. If instead the input is A => B => C and the output takes (x, y) together, it is uncurry.

(The Scala library has these too: add3.curried on a function value, and Function.uncurried.)

Checking a claimed equivalence X :=: Y

1. Work out the type of each side. If one is curried and the other is not, they are not equivalent (unless a conversion is applied).
2. If a side passes the wrong form to curry/uncurry, it does not even compile, so the claim is false.
3. If types match, check behaviour on one example: both sides with arguments 10 and 3.

Laziness: def, val, lazy val

Eager evaluation: an expression is computed as soon as it is bound to a name. Lazy evaluation: it is computed only when it is needed. Scala is eager by default, but lets you choose per definition. The slides:

The body is usually a block with a print in it, so the printed letters tell you exactly when it ran. Remember: a block's value is its last expression, so {print("v"); 3} prints v and has value 3.

Paper method: a timeline. Go through the code line by line. At each declaration: val prints now; lazy val and def print nothing. At each line that uses names, go through the expression from left to right: every def use prints; the first lazy val use prints and you mark it "done"; later uses print nothing. Keep a column with running values.

def run1(): Unit = {
  def d: Int = { print("D"); 1 }
  val v: Int = { print("V"); 2 }
  lazy val l: Int = { print("L"); 3 }
  print("|")
  var s = l
  s += d
  s += l
  s += v
  s += d
  println("| s=" + s)
}
run1()

V|LDD| s=10

A lazy val that is only used in a branch that does not run is never computed at all:

def run2(): Unit = {
  lazy val l: Int = { print("L"); 3 }
  def d: Int = { print("D"); 1 }
  val v: Int = { print("V"); 2 }
  var s = 0
  if (v > 5) { s += l; s += l } else { s += d; s += d }
  println("| s=" + s)
}
run2()

VDD| s=2

Counters: values depend on the moment of evaluation

When the body bumps a shared counter, the value you get tells you when it ran. Expressions are evaluated left to right, and an eager val has already bumped the counter before the line that uses it.

var n = 0
def bump(): Int = { n += 1; n }
def run4(): Unit = {
  lazy val c = bump()
  def b = bump()
  val a = bump()                    // runs now: n = 1, a = 1
  val r = (c + c, b + b, a + a, n)
  println(r)
}
run4()

(4,7,2,4)

c + c: first use, bump gives 2, the second c reuses 2: 4. b + b: two runs, 3 + 4 = 7. a + a = 1 + 1 = 2. Finally n is 4.

Inside a class: one cache per object

A val field runs when the object is created (in the constructor), even if nobody reads it. A lazy val field is computed once per object, at that object's first use. A def (or a method p()) runs at every call.

class Report(val id: Int) {
  val made: Int = { print(s"made$id "); id }
  lazy val summary: Int = { print(s"sum$id "); id * 10 }
  def fresh: Int = { print(s"fresh$id "); id + 1 }
}
val r1 = new Report(1)
val r2 = new Report(2)
println("|")
println(r1.summary + r1.summary + r2.fresh + r2.fresh + r2.summary)

made1 made2 |
sum1 fresh2 fresh2 sum2 46

r2.summary prints again because r2 is a different object with its own cache. Sum: 10 + 10 + 3 + 3 + 20 = 46.

Same mechanism for parameters: by-name (=> Int)

The slides do not use this term, but it is the same idea and helps when you trace side effects. A normal parameter x: Int is by-value: the argument is computed once, before the call, like a val. A by-name parameter x: => Int is computed every time the body uses it, like a def. Storing it in a lazy val inside makes it "at most once".

def tick(tag: String): Int = { print(tag); 1 }
def byValue(x: Int): Int = x + x
def byName(x: => Int): Int = x + x
def cached(x: => Int): Int = { lazy val y = x; y + y + y }
def maybe(c: Boolean, x: => Int): Int = if (c) x else 0
println(" " + byValue(tick("v")))
println(" " + byName(tick("n")))
println(" " + cached(tick("c")))
println(maybe(false, tick("m")))
println(maybe(true, tick("M")))

v 2
nn 2
c 3
0
M1

This is also how a "control structure" with an additional argument list works: def repeat(k: Int)(body: => Unit), called as repeat(3) { print("hi ") }, prints hi hi hi .

Why laziness? (slides) It does not compute what is not needed, can save work, and allows infinite data structures. The price: the evaluation order is hard to follow, which is why lazy languages combine it with pure functions only.

def t1(): Unit = {
  val x: Int = { print("x"); 1 }
  lazy val y: Int = { print("y"); 2 }
  def z: Int = { print("z"); 3 }
  var s = z
  s += x
  s += y
  s += z
  s += y
  println(" s=" + s)
}
t1()

xzyz s=11

def t2(): Unit = {
  lazy val y: Int = { print("y"); 2 }
  def z: Boolean = { print("z"); false }
  val x: Int = { print("x"); 1 }
  var s = 0
  if (z) { s += y } else { s += x; s += x }
  println(" s=" + s)
}
t2()

xz s=2

var m = 0
def nxt(): Int = { m += 1; m }
def t3(): Unit = {
  def a = nxt()
  lazy val b = nxt()
  val c = nxt()
  println((b + a, b + a, c, m))
}
t3()

(5,6,1,4)

class Cfg(val k: Int) {
  lazy val big: Int = { print("B" + k + " "); k * 100 }
  def small: Int = { print("s" + k + " "); k }
}
val q1 = new Cfg(1); val q2 = new Cfg(2)
var acc = 0
acc += q1.small; acc += q1.big; acc += q2.big; acc += q1.big; acc += q2.small
println(acc)

s1 B1 B2 s2 403

Polymorphism: one piece of code, many types

Polymorphism is Greek for "many forms". Polymorphic code is code that works for more than one type. The goal is reuse: write speakTwice once and have it work for dogs, cats and parrots.

First some words you need for the whole block.

• A class is a blueprint (class Dog). An object (or instance) is one thing built from it with new Dog.
• A variable such as val a: Animal = new Dog does not contain the dog itself. It holds a reference: an arrow pointing to the dog object somewhere in memory.
• The static type of an expression is the type the compiler knows, from declarations alone, without running anything. Here the static type of a is Animal, because that is what you wrote.
• The dynamic type (or run-time class) is the class of the object the arrow really points to. Here it is Dog. It is only known when the program runs, and it can change if a var is reassigned.
• D is a subtype of A (written D <: A) means: a D can be used anywhere an A is expected. class Dog extends Animal makes Dog <: Animal.

The professor names three kinds of polymorphism:

class Animal { def speak: String = "..." }
class Dog extends Animal { override def speak = "woof" }
class Cat extends Animal { override def speak = "miauw" }

var pet: Animal = new Dog
println(pet.speak)
pet = new Cat
println(pet.speak)

woof
miauw

The static type of pet is Animal on every line: a declaration never changes. The dynamic type is Dog and then Cat. The output follows the dynamic type.

error: type mismatch;
 found   : Any
 required: Int

val things = List(true, "yes", 7)
val first = things(0)
val ok: Boolean = first

var pet: Animal = new Cat   // line 1
pet = new Dog               // line 2
val d: Dog = new Dog        // line 3

Generics (parametric polymorphism)

A type parameter is a placeholder for a type, written in square brackets. You use it when the code does not care what the type is, only that it is the same type in several places.

Generic functions

def swap[A, B](p: (A, B)): (B, A) = (p._2, p._1)
println(swap((42, "hello")))      // A = Int, B = String, result (String, Int)

(hello,42)

You almost never write swap[Int, String](...): the compiler infers A and B from the static types of the arguments. The signature then promises the result type: (B, A) becomes (String, Int).

Generic classes

class Stack[A] {
  private var elements: List[A] = Nil
  def push(x: A): Unit = elements = x :: elements
  def pop(): A = { val top = elements.head; elements = elements.tail; top }
}
val st = new Stack[String]
st.push("a"); st.push("b"); st.push("c")
print(st.pop()); print(st.pop()); println(st.pop())

cba

new Stack[String] "instantiates A with String": now push only accepts Strings and pop() has static type String.

The type of a call: read the signature, not the value

This is how "what is the (most specific) type of v" questions work. The static type of a call f(arg) is the declared result type of f, with any type parameters replaced by what was inferred from the argument's static type. What the body does at run time is irrelevant. Work inside out.

abstract class Animal { def speak: String }
class Dog extends Animal { def speak = "woof" }
class Cat extends Animal { def speak = "miauw" }
class Puppy extends Dog { override def speak = "yip" }

def anyId(x: Any): Any = x
def id[A](x: A): A = x
def animalId(x: Animal): Animal = x
def boundId[A <: Animal](x: A): A = x
def boundToAnimal[A <: Animal](x: A): Animal = x

(anyId(new Dog), id(new Cat), animalId(new Dog), boundId(new Puppy), boundToAnimal(new Cat))

(Any, Cat, Animal, Puppy, Animal)

(That line is the static type, printed with a TypeTag.) Only the functions whose result type is the type parameter (id, boundId) keep the precise type. A result type written as a concrete class (Any, Animal) forgets it, even if the function is generic.

Upper type bounds: A <: Animal

Suppose you want to return an animal together with its sound, without forgetting what kind of animal it was.

def withSound(a: Animal): (Animal, String) = (a, a.speak)      // forgets: result is Animal
def withSound[A](a: A): (A, String) = (a, a.speak)              // does not compile
def withSound[A <: Animal](a: A): (A, String) = (a, a.speak)   // keeps A and may call speak

The middle one fails with error: value speak is not a member of type parameter A: for an arbitrary A the compiler cannot know there is a speak. The bound A <: Animal means "A can be any subtype of Animal". That gives permission to call Animal methods, and the result is still typed as the precise A: withSound(new Puppy) has type (Puppy, String) and value (..., "yip").

Generic case classes and their fields

case class Cage(a: Animal)
case class GCage[A <: Animal](a: A)
(Cage(new Dog).a, GCage(new Dog).a)

(Animal, Dog)

Cage's field is declared Animal, so reading it gives Animal. GCage(new Dog) infers A = Dog, so its field has type Dog.

Generics plus inheritance: Comparable[A]

The slides combine both kinds of polymorphism. A generic trait gives default methods, and each class says "I am comparable to myself" by extending it with its own name:

trait Comparable[A] {
  def compareTo(rhs: A): Int                         // < 0, 0 or > 0
  def <(rhs: A): Boolean = compareTo(rhs) < 0        // inherited for free
}
case class Money(cents: Int) extends Comparable[Money] {
  def compareTo(rhs: Money): Int = cents - rhs.cents
}
case class Name(s: String) extends Comparable[Name] {
  def compareTo(rhs: Name): Int = s.length - rhs.s.length
}
case class Pair[A <: Comparable[A], B <: Comparable[B]](a: A, b: B)
    extends Comparable[Pair[A, B]] {
  def compareTo(rhs: Pair[A, B]): Int = {
    val c = a.compareTo(rhs.a)
    if (c != 0) c else b.compareTo(rhs.b)        // second field only breaks a tie
  }
}

A and B are separate parameters, so a pair of a Money and a Name is fine. The bound A <: Comparable[A] is what allows a.compareTo(rhs.a). The same pattern appears as def sort[A <: Ordered[A]](arr: Array[A]): "works for any A that has the Ordered[A] trait", so inside you may write arr(i) > arr(i+1).

def makeDog(x: Animal): Dog = new Puppy
val v = boundId(id(animalId(makeDog(new Cat))))
val w = id(makeDog(new Cat))

val pup = new Puppy
val asDog: Dog = pup
val t = (id(asDog), boundId(asDog), id(pup))

Pair(Money(500), Name("Ann")).compareTo(Pair(Money(500), Name("Bob")))
Pair(Money(500), Name("Anna")).compareTo(Pair(Money(500), Name("Bob")))
Pair(Money(300), Name("Anna")).compareTo(Pair(Money(500), Name("Bob")))
Pair(Money(1), Name("xyz")) < Pair(Money(2), Name("y"))

0
1
-200
true

Subtype polymorphism

Imagine you only had Any. A function that makes any animal speak would have to test the type of its argument:

def speak(animal: Any): String = animal match {
  case _: Dog    => "Woof woof!"
  case _: Cat    => "Miauw!!"
  case a: Parrot => a.line
  case _         => "<Silence>"
}

The slides list the downsides: users of your library cannot add a new animal without editing this function, and Any is far too loose a type. The fix is a common supertype that promises a speak method, with each subclass giving its own implementation:

abstract class Animal { def speak: String }          // a promise, no body
class Dog extends Animal { def speak = "Woof woof!" }
class Cat extends Animal { def speak = "Miauw!!" }
class Parrot(val line: String) extends Animal { def speak = line }

def speakTwice(animal: Animal): String = animal.speak + animal.speak

Now speakTwice compiles because every Animal is guaranteed to have speak, and it works for animals that do not exist yet. Which speak runs is decided per object, at run time.

What "subtype" means

D is a subtype of A (D <: A) means: D supports at least the interface of A, so a D can be used anywhere an A is expected. That is the substitution principle. Consequences:

• def f(x: A): B accepts any value whose type is a subtype of A, and may return any subtype of B.
• var v: A can hold any value of a subtype of A. A variable may have a trait type: var x: X = new B is fine when B extends trait X.
• The direction matters: var d: Dog = new Animal is an error (type mismatch; found: Animal, required: Dog). Not every animal is a dog.
• Every type is a subtype of itself, and of Any.
• Subtype is not the same as subclass: a subclass is a subtype, but traits and function types also create subtypes.

One value, many types

Because of substitution, a value has many types at once. A new Puppy is a Puppy, a Dog, an Animal, an AnyRef and an Any. A list of several objects therefore has every type that is a common supertype of all elements; the compiler infers the lowest one (the professor calls it the lub, least upper bound: the lowest common ancestor in the hierarchy diagram).

trait K; trait M; trait N
trait S extends K with M
class T extends S
class U extends M with N
class V extends S with N

List(new T, new U, new V)     // inferred type
List(new T, new V)

List[M]
List[S]

Method: draw the diagram, then for each element write the set of all its supertypes. T: {T, S, K, M}. U: {U, M, N}. V: {V, S, K, M, N}. The intersection is {M} (plus AnyRef and Any, which everyone has). So the list "has" the types List[M], List[AnyRef], List[Any], and as a value it is also simply Any. It does not have List[S] (U is not an S) or List[N] (T is not an N). The same reasoning answers "which return types can I write for a function that returns new A in one branch and new B in another".

val c: Boolean = ...
val a = if (c) new Dog else new Cat
val b = if (c) 1 else "one"

val l: List[M] = List(new T, new U, new V)
val l2: List[Any] = l
val l3: Any = l
val l4: List[AnyRef] = l
val l5: List[S] = l

Inheritance and dynamic dispatch

Inheritance means: a subclass automatically gets every definition of its superclass. You only write what is new or different. Writing a new body for an inherited method is overriding.

abstract class Shape {
  def sides: Int                                   // abstract: no body
  def name: String = "shape"                       // default
  def describe: String = name + " has " + sides + " sides"
}
class Triangle extends Shape { def sides = 3; override def name = "triangle" }
class Square extends Shape { def sides = 4 }
class Box extends Square { override def describe = "a box" }

val shapes: List[Shape] = List(new Triangle, new Square, new Box)
for (s <- shapes) println(s.describe)

triangle has 3 sides
shape has 4 sides
a box

describe is written once in Shape, but the name and sides it calls are filled in by each object. That is the main trick of this whole block.

Dynamic dispatch: "always use the deepest implementation"

Dispatch means choosing which body runs for a call. In Scala (and Java) every method call x.m() uses dynamic dispatch (also called late binding): at run time, look at the class of the object x points to, and use the deepest implementation of m for that class. "Deepest" means: start at the object's own class; if it defines m, use it; otherwise go to its parent, and so on up.

The crucial consequence: where the calling code is written does not matter. When Shape.describe says name, it means this.name, and this is the actual object (a Triangle). So the lookup for name starts at Triangle again.

Another way to see it: this is a hidden parameter

Think of every method as having an invisible first parameter this. t.describe is really describe(this = t). When describe's body says name, that is this.name, and this is still t, the Triangle. Being "inside Shape's code" does not turn the object into a Shape.

class T1 { def who: String = "T1"; def me: T1 = this; def hello: String = "I am " + this.who }
class T2 extends T1 { override def who = "T2" }
val t: T1 = new T2
println(t.hello + " " + t.me.who)

I am T2 T2

The trace method on a full example

class K { def f(x: Int): Int = x + 1; def g(x: Int): Int = x * 10 }
class L extends K { override def f(x: Int) = x + 100 }
class M extends L { override def g(x: Int) = x * 2 }
class N extends M
val ks: List[K] = List(new K, new L, new M, new N)
println(ks.map(k => k.f(1) + k.g(1)))

First make a method table: for each class, which body each method uses (look in the class, else take the parent's row).

Then the two columns per element. The static type is K for all of them (it only checks that f and g exist on K). The dynamic class picks the row: K: 2 + 10 = 12. L: 101 + 10 = 111. M: 101 + 2 = 103. N: same row as M, 103.

List(12, 111, 103, 103)

Note N: a class that overrides nothing behaves exactly like its parent, not like the root class.

Methods that return objects

When a method returns a new object, its declared result type is the static type, and the class after new is the dynamic type. Evaluate chains left to right, one object at a time.

class A { def mk: A = new B; def same: A = this; def x: String = "A" }
class B extends A { override def x = "B"; override def mk: A = new A }
val a: A = new A
val b: A = new B
println(a.mk.x + b.mk.x + b.same.x + a.mk.mk.x + b.mk.same.mk.x)

BABAB

Only the receiver is dispatched on

In x.pair(o), the object before the dot (the receiver) picks which pair runs. The argument o does not. Inside the body, y means this.y (the receiver's y) and o.y is a separate dynamic call on the argument.

class U { def y: String = "u"; def pair(o: U): String = y + o.y }
class W extends U { override def y = "w" }
class Z extends W { override def pair(o: U): String = o.y + y }
val u: U = new U; val w: U = new W; val z: U = new Z
println(u.pair(w) + "," + w.pair(z) + "," + z.pair(u))

uw,ww,uw

w.pair(z): W has no pair, so U.pair runs with this = the W: y is "w", o.y is Z's y, which Z inherits from W: "w". z.pair(u): Z's own pair, with the order swapped: o.y = "u", then y = "w".

Traits in the hierarchy

Traits (week 6) take part in the same lookup. An override in a trait beats the trait it extends, and the class's own definition beats everything it inherits.

trait Loud { def noise: String = "LOUD" }
trait Soft extends Loud { override def noise = "soft"; def extra = "+" }
trait Tagged { def tag = "t" }
class Speaker extends Tagged with Soft { override def tag = "T" }
val s = new Speaker
println(s.noise + s.extra + s.tag)

soft+T

The order in which traits are listed only matters when two of them define the same method; that is the week 6 rule "deepest first, last trait first".

Construction order: fields are not ready yet

When you write new Derived, Scala first runs the superclass constructor (the body of class Base { ... }, top to bottom), and only then the subclass body. Until a val line has run, the field holds its default: 0 for numbers, false, or null for objects. Dynamic dispatch still works during construction, so a superclass constructor that calls an overridden method can see the subclass's fields uninitialised.

class Base {
  println("Base body starts")
  val greeting: String = "hi from " + label
  def label: String = "Base"
  println("Base body ends")
}
class Derived extends Base {
  println("Derived body starts")
  val n: Int = 7
  val word: String = "seven"
  override def label: String = "Derived n=" + n + " word=" + word
  println("Derived body ends")
}
val d = new Derived
println(d.greeting)
println(d.label)

Base body starts
Base body ends
Derived body starts
Derived body ends
hi from Derived n=0 word=null
Derived n=7 word=seven

While Base computes greeting, label already dispatches to Derived's version (the object is a Derived from the first moment), but n and word have not been assigned yet. Constructor parameters, in contrast, are available immediately:

class Counter(start: Int) {
  var count: Int = start
  def inc(): Unit = count += step
  def step: Int = 1
}
class Fast(start: Int) extends Counter(start * 10) { override def step: Int = 5 }
val c: Counter = new Fast(2)
c.inc(); c.inc()
println(c.count)

30

new Fast(2) passes 2 * 10 = 20 to Counter, so count starts at 20. Each inc() is Counter's code, but step dispatches to Fast: 20 + 5 + 5 = 30.

The other choice: static dispatch

Some languages choose the body at compile time from the variable's type (static dispatch). That is the default in C++ and C# unless a method is marked virtual; it is cheaper because there is no run-time lookup. Scala and Java only have dynamic dispatch. With static dispatch, val a: Animal = new Dog; a.describe would print the generic animal text; in Scala it prints the dog's. If an exam answer looks like "every call uses the declared type's code", it is describing static dispatch, which is wrong for Scala.

The override keyword

• Replacing a method that already has a body: override is required. Without it: error: `override` modifier required to override concrete member.
• Implementing an abstract method (no body in the parent): override is optional. That is what the slide means by "override annotation optional".

class P1 { def a: String = "p"; def b: String = a + a }
class Q1 extends P1 { override def a = "q" }
class P2 { def a: String = "p"; def b: String = a + a }
class Q2 extends P2 { override def b = "q" }
val v1: P1 = new Q1
val v2: P2 = new Q2
println(v1.b + " " + v2.b)

qq q

class A { def x: String = "<" + y; def y: String = "-" + z; def z: String = "a" }
class B extends A { override def y: String = "=" + z }
class C extends B { override def z: String = "c" }
for (e <- List[A](new A, new B, new C)) print(e.x + " ")

<-a <=a <=c 

15 2

Calling the superclass: super

Sometimes an override wants to extend the parent's behaviour instead of replacing it. super.m runs the parent's version of m:

class Dog extends Animal { def speak: String = "Woof woof!" }
class GoldenRetriever extends Dog { override def speak: String = super.speak + " old chap!" }

new GoldenRetriever().speak gives Woof woof! old chap! (verified).

The two precise facts about super

1. super is static. super.m written inside class B always means "the m that B's parent has", decided by where the code is written, not by the object's class. That is why super chains do not loop forever.
2. super does not change this. The parent's code runs on the same object. Any call inside it without super is a normal dynamic call and starts from the object's real class again.

Trace with a call stack

class P { def tag: String = "p"; def show: String = "[" + tag + "]" }
class Q extends P { override def tag = "q"; override def show = super.show + "Q" }
class R extends Q { override def tag = "r"; override def show = "R" + super.show }
println(new P().show + " " + new Q().show + " " + new R().show)

[p] [q]Q R[r]Q

Write the pieces in the position the expression puts them: "R" + super.show puts R in front, super.show + "Q" puts Q at the end.

Where super is written decides which parent

class A0 { def f: String = "A" }
class B0 extends A0 { override def f = "B"; def g: String = super.f + f }
class C0 extends B0 { override def f = "C" }
println(new C0().g + " " + new B0().g)

AC AB

For the C0 object, g is B0's code, and super in B0 means A0, so super.f is "A", not "B" (the parent of the object's class). The plain f is dynamic: "C".

class A { def a: String = "1"; def b: String = a + "<" }
class B extends A { override def a = "2"; override def b = super.b + "B" }
class C extends B { override def a = "3"; override def b = "C" + super.b }
val all: List[A] = List(new A, new B, new C)
println(all.map(_.b))

List(1<, 2<B, C3<B)

abstract class Greeter { final def greet: String = hello + ", " + hello; def hello: String = "hi" }
class Loud extends Greeter { override def hello = "HI" }
class Louder extends Loud { override def hello = super.hello + "!" }
val gs: List[Greeter] = List(new Loud, new Louder)
println(gs.map(_.greet))

List(HI, HI, HI!, HI!)

AD

Abstract classes and abstract methods

An abstract method is a method declared without a body: def speak: String. It is a promise: "every concrete animal will have this". An abstract class is a class marked abstract; it may contain abstract methods and cannot be instantiated with new, because some of its methods might have no code.

abstract class Animal {
  def speak: String                           // abstract
  def twice: String = speak + speak           // concrete, calls the abstract one
}

A concrete method calling an abstract one is completely normal (it is the "template" pattern from the slides). By the time any object exists, it is of some concrete subclass that has implemented speak, and dynamic dispatch finds that implementation.

The rules, each with the real compiler message

Things that are allowed (the exam offers them as fake errors):

• An abstract class with only concrete methods, or with no abstract methods at all (it still cannot be instantiated).
• An abstract class with constructor parameters: abstract class A(var x: Int); subclasses pass them: class B(xi: Int) extends A(xi).
• An abstract subclass that does not implement the parent's abstract methods yet (abstract class Pouched extends Mammal).
• A trait with abstract methods. Traits never need the word abstract, may extend other traits, and an abstract class may extend a trait without implementing its methods.
• Implementing an abstract method with or without override.
• An abstract method with any return type (it does not have to "return an abstract type").
• A variable whose static type is abstract: val a: Animal = new Dog.

abstract class Shape(var size: Int) {
  def area(): Int
  final def grow(): Unit = size += 1
  def show(): String = "shape " + area()
}
final class Sq(s: Int) extends Shape(s) {
  override def show(): String = "square"
  override def grow(): Unit = size += 2
}
class BigSq extends Sq(10) {
  def area(): Int = size * size
}
object Use {
  val a: Shape = new Sq(3)
  val b: Shape = new Shape(1)
}

Final methods and final classes

final is about extension, not about values (for values you have val).

• A final method cannot be overridden in any subclass.
• A final class cannot have subclasses.

abstract class Mammal { final def hasNipples = true; def speak: String }
abstract class CatLike extends Mammal { def canPur = true; final def canRoar = !canPur }
class HouseCat extends CatLike { def speak = "Miauw" }
class Lion extends CatLike { override def canPur = false; def speak = "Wraaagh" }
println(new HouseCat().canRoar + " " + new Lion().canRoar + " " + new Lion().hasNipples)

false true true

From the slides: canRoar is final, so no cat can lie about roaring, but the canPur it calls is not final and is dispatched dynamically. The Lion overrides canPur, so the inherited final canRoar gives true.

What final does not mean

Real messages: extending a final class gives illegal inheritance from final class Leaf; overriding a final method gives cannot override final member: final def twice: String (defined in class Animal). Overriding a final method without writing override still gives the final error.

Sealed is not final

sealed (week 5) means: direct subclasses may only be defined in the same file. A sealed class normally has subclasses (case classes), can be abstract, and its methods can be overridden. The benefit is that the compiler knows all cases, so a pattern match over them can be checked for exhaustiveness without a default case.

trait Winged { def flap(): Unit = println("flap") }
abstract class Bird { final def sing: String = tweet + tweet; def tweet: String }
final class Robin(val n: Int) extends Bird with Winged {
  def tweet = "tjilp"
  def louder(): Unit = n += 1
}
class Baby extends Robin(1)

trait D { def h(): String; final def p(): String = "Hello" }
class C extends D { def h() = "h"; def p(): String = "Yo" }

Any: the root of all types

Every type is a subtype of Any. If you write a class without extends, it still extends Any (through AnyRef). Under Any there are two branches: value types (AnyVal: Int, Double, Boolean, Char, ...) which cannot be null, and reference types (AnyRef: String, List, every class you define) which can.

Because everything is an Any, these methods exist on every value:

toString is overridden like any other method

class Rational(val n: Int, val d: Int) {
  override def toString: String = if (d == 1) n.toString else n + "/" + d
}
val r: Any = new Rational(3, 4)
println(r)
println(new Rational(6, 1).toString + " and " + r.toString)

3/4
6 and 3/4

The static type of r is Any, but toString is dispatched dynamically, so Rational's version runs. The override is required because Any already has a toString with a body.

Type tests and casts

def describe(x: Any): String =
  if (x.isInstanceOf[String]) "string of length " + x.asInstanceOf[String].length
  else "not a string: " + x.toString
println(describe("hallo") + "; " + describe(9))

string of length 5; not a string: 9

isInstanceOf asks about the dynamic class; asInstanceOf tells the compiler "trust me, it is a String" and throws an exception at run time if it is not. The professor calls this the back door of the type system and says to avoid it: if you know the type and the compiler does not, redesign (use a common supertype with a method, or a match). Number conversions like toDouble are fine.

The bottom types (week 6 in detail)

Null is a subtype of every reference type (its one value is null). Nothing is a subtype of every type and has no values; an expression like throw new Error("x") has type Nothing, which is why it fits anywhere.

val l = List(false, "hallo", 3)
println(l)
val x: Boolean = l(0)

List(1/2, 5, five)

Iterators

An iterator is an object that hands out the elements of something one at a time. The interface has two methods:

abstract class Iterator[A] {
  def hasNext: Boolean      // is there another element?
  def next(): A             // give it, and move forward
}

It is a perfect example of subtype polymorphism: code written against Iterator[Int] works for any iterator, whether it comes from a List, a Set, a Range or your own class.

def addAll(it: Iterator[Int]): Int = {
  var res = 0
  while (it.hasNext) res += it.next()
  res
}
println(addAll(List(1, 2, 3).iterator) + " " + addAll(Set(1, 2, 3).iterator) + " " + addAll((0 until 10 by 2).iterator))

6 6 20

An iterator is a cursor with state

val it = List(10, 20, 30).iterator
it.hasNext   // true
it.next()    // 10
it.next()    // 20
it.hasNext   // true
it.next()    // 30
it.hasNext   // false
it.next()    // throws java.util.NoSuchElementException

(All verified.) hasNext only looks; next() returns the current element and moves the cursor. Once used up, an iterator stays used up.

Writing your own

class Countdown(var cur: Int) extends Iterator[Int] {
  def hasNext: Boolean = cur > 0
  def next(): Int = { val res = cur; cur -= 1; res }   // remember, move, return the remembered one
}
val cd = new Countdown(3)
for (i <- cd) print(i)
println()
for (i <- cd) print(i)     // prints nothing

321

This is the slides' "something funky": a for loop over an iterator consumes it, and the second loop finds cur = 0.

Iterable: something that can give a fresh iterator

class CountdownFrom(n: Int) extends Iterable[Int] {
  def iterator: Iterator[Int] = new Countdown(n)    // a NEW cursor every call
}
val cf = new CountdownFrom(3)
for (i <- cf) print(i)
for (i <- cf) print(i)

321321

Each loop over an Iterable calls iterator and gets its own cursor starting from the beginning. (The Iterable also inherits dozens of methods like map, sum, toList for free.)

Two iterators versus two names for one iterator

Draw boxes and arrows. cf.iterator called twice creates two separate cursor objects. val i3 = i1 creates no object; it is a second arrow to the same cursor (aliasing).

val i1 = cf.iterator
val i2 = cf.iterator
val i3 = i1
print(i1.next()); print(i2.next()); print(i3.next()); print(i2.next()); println(i1.next())

33221

Note that calling next() directly does not check hasNext: a RangeIterator with cur < end would happily keep returning values past end if you call next() by hand. Only loops (and library methods) check hasNext.

Anything that walks the iterator consumes it

val big = new Countdown(4)
println(big.size)       // walks to the end to count
println(big.toList)     // nothing left
val big2 = new Countdown(4)
println(big2.toList + " " + big2.toList)

4
List()
List(4, 3, 2, 1) List()

Generated sequences

An iterator does not need a collection behind it. It can compute each element from a state, even forever:

class Squares extends Iterator[Int] {
  var n = 1
  def hasNext = true                        // never ends
  def next(): Int = { val r = n * n; n += 1; r }
}
val sq = new Squares
println(sq.take(4).toList)
println(sq.next())

List(1, 4, 9, 16)
25

A general "state machine" iterator: keep a current state, return it, replace it by f(state), count down.

class StepIter[A](var cur: A, val f: A => A, var count: Int) extends Iterator[A] {
  def hasNext: Boolean = count > 0
  def next(): A = { val res = cur; cur = f(cur); count -= 1; res }
}
val pairs = new StepIter[(Int, Int)]((1, 0), p => (p._1 + 1, p._2 + p._1), 5)
for (e <- pairs.map(_._2)) print(e + " ")

0 1 3 6 10 

Trace with a state table. The returned value is the state before f is applied, so the very first element is the initial state.

With count = 5 you get exactly 5 values. The same idea as a recursive function on lists is unfold: the function returns Some((nextState, output)) to continue or None to stop.

def unfold[S, B](s: S)(f: S => Option[(S, B)]): List[B] =
  f(s) match {
    case Some((next, out)) => out :: unfold(next)(f)
    case None => Nil
  }
println(unfold(1)(x => if (x > 20) None else Some((x * 3, x))))
println(unfold(1)(x => if (x > 20) None else Some((x * 3, x * 3))))

List(1, 3, 9)
List(3, 9, 27)

One small change, different answer: emitting the old state x gives 1, 3, 9 (27 > 20 stops it); emitting the new state x * 3 gives 3, 9, 27. Always check which component of the tuple is the output and which is the next state; different exams put them in different orders.

val doubling = new StepIter[Int](1, x => x * 2, 5)
for (e <- doubling) print(e + " ")

1 2 4 8 16 

List((1,0), (2,1), (3,3), (4,6), (5,10))

unfold((5, 0))(p => if (p._1 == 0) None else Some(((p._1 - 1, p._2 + p._1), p._2 + p._1)))

List(5, 9, 12, 14, 15)

def scan[A, B](acc: B)(f: (B, A) => B)(l: List[A]): List[B] = l match {
  case h :: t => val nxt = f(acc, h); nxt :: scan(nxt)(f)(t)
  case Nil => Nil
}
scan[Int, Int](10)(_ - _)(List(1, 2, 3))

List(9, 7, 4)

Overloading (ad hoc polymorphism)

Overloading is defining several methods with the same name but different parameter types (or numbers of parameters). They are completely separate methods that happen to share a name.

object Overloading {
  def max(l: List[Int]): Int = l.max
  def max(a: Int, b: Int): Int = if (a > b) a else b
  def max(a: Any): Int = throw new Error("No max for any")
}

The key fact: which overload is called is decided by the compiler, from the static types of the arguments. The compiler collects all overloads that are applicable (each argument's static type is a subtype of the parameter type), and picks the most specific one (the one whose parameter types are subtypes of the others'). The run-time class of the argument plays no role at all.

class Vehicle { def sound: String = "..." }
class Car extends Vehicle { override def sound = "vroom" }
class Tesla extends Car { override def sound = "hum" }
def kind(v: Any): String = "thing"
def kind(v: Vehicle): String = "vehicle(" + v.sound + ")"
def kind(v: Car): String = "car(" + v.sound + ")"

val t1: Tesla = new Tesla
val t2: Car = new Tesla
val t3: Vehicle = new Tesla
val t4: Any = new Tesla
println(kind(t1) + " " + kind(t2) + " " + kind(t3) + " " + kind(t4))

car(hum) car(hum) vehicle(hum) thing

Same object every time, four different static types:

There is no kind(v: Tesla), so even t1 gets the Car overload: the most specific available one. Notice the two moments: the label ("car" or "vehicle") is chosen at compile time from the static type, and the sound ("hum") at run time from the object.

Reassigning a var does not re-choose

var v: Vehicle = new Car
println(kind(v))
v = new Tesla
println(kind(v))
val list: List[Vehicle] = List(new Car, new Tesla)
for (e <- list) print(kind(e) + " ")

vehicle(vroom)
vehicle(hum)
vehicle(vroom) vehicle(hum) 

The static type of v and of the loop variable e is Vehicle, so it is the Vehicle overload every time.

If you want a run-time choice, use a match

for (e <- list) e match {
  case c: Car => print("match car " + c.sound + " ")
  case _ => print("other ")
}

match car vroom match car hum 

A type pattern tests the dynamic class, unlike overloading.

this has a static type too

object Who { def who(x: Any) = "Any"; def who(x: Base) = "Base"; def who(x: Sub) = "Sub" }
class Base { def ask: String = Who.who(this) }
class Sub extends Base
println(new Sub().ask + " " + Who.who(new Sub))

Base Sub

Inside class Base, the compiler types this as Base, so the Base overload is fixed when Base is compiled, even when the object is a Sub.

Several parameters, and passing an overloaded function

sealed abstract class Coin
case class Head() extends Coin
case class Tail() extends Coin
def pick(a: Coin, b: Coin): Coin = a
def pick(a: Head, b: Coin): Coin = b
def pick(a: Tail, b: Tail): Coin = Head()

println(pick(Tail(), Tail()) + " " + pick(Head(), Tail()))
val h: Coin = Head()
println(pick(h, Tail()))
val coins: List[Coin] = List(Tail(), Tail(), Head())
println(coins.foldLeft(Tail(): Coin)(pick))

Head() Tail()
Head()
Tail()

pick(Tail(), Tail()): static types (Tail, Tail); applicable: (Coin,Coin) and (Tail,Tail); most specific (Tail,Tail): Head(). pick(Head(), Tail()): (Head,Coin) is most specific: returns b. pick(h, Tail()): h is a Coin, only (Coin,Coin) applies: returns a, the Head. In the fold, pick is passed as a function where a (Coin, Coin) => Coin is expected. The compiler chooses once, from that expected type: the (Coin, Coin) version, which always returns its first argument, so the accumulator stays the initial Tail(). It never re-chooses per element.

What does not count as overloading

• Differing only in the return type: def f(a: Int): Int and def f(a: Int): String give method f is defined twice.
• No unique most specific overload: with f(a: A, b: Any) and f(a: Any, b: A), the call f(new A, new A) gives ambiguous reference to overloaded definition.

object Talk {
  def talk(a: Animal): String = "animal:" + a.speak
  def talk(d: Dog): String = "dog:" + d.speak
}
val pets: List[Animal] = List(new Dog, new Cat)
println(pets.map(p => Talk.talk(p)))
val d: Dog = new Dog
println(Talk.talk(d))

List(animal:woof, animal:miauw)
dog:woof

car(vroom) thing thing

var x: Vehicle = new Car
var y: Car = new Car
print(kind(x)); y = new Tesla; print(kind(y))

vehicle(vroom)car(hum)

Overloading vs overriding (and the == trap)

The two words sound alike and mean opposite things.

The two-step rule for any call

1. Compile time: using the static type of the receiver and the static types of the arguments, pick the signature (the overload).
2. Run time: for that exact signature, start at the receiver's dynamic class and take the deepest body.

class Printer { def p(x: Any): String = "Printer.any"; def p(x: String): String = "Printer.str" }
class Fancy extends Printer { override def p(x: Any): String = "Fancy.any" }
val pr: Printer = new Fancy
val s: Any = "hi"
println(pr.p(s) + " " + pr.p("hi") + " " + new Printer().p(s))

Fancy.any Printer.str Printer.any

The value of s is a String at run time, but step 1 already fixed p(Any). The overridden p(Any) in Fancy is a different method from p(String).

The classic trap: equals(other: Point)

class Point(val x: Int, val y: Int) {
  def equals(other: Point): Boolean = x == other.x && y == other.y   // OVERLOAD, not override
}
val p1 = new Point(1, 2)
val p2 = new Point(1, 2)
val p2any: Any = p2
println(p1.equals(p2))            // static type Point: picks equals(Point)
println(p1.equals(p2any))         // static type Any: picks Any's equals(Any)
println(p1 == p2)                 // == is Any's final method, calls equals(Any)
println(List(p1).contains(p2))    // library code calls equals(Any)
println(p1 == p1)                 // same object

true
false
false
false
true

Because the parameter type is Point and not Any, this method does not replace Any.equals(that: Any); it is a new overload next to it. Anything that calls equals with static type Any (the == operator, contains, Sets, Maps) still gets the inherited version, which compares references (same object?). Only a direct p1.equals(p2) with a Point-typed argument reaches your method. If you add override, the compiler catches it: method equals overrides nothing. Note: the super classes of class Point contain the following, non final members named equals: def equals(x$1: Object): Boolean.

The correct version overrides with parameter type Any:

class GoodPoint(val x: Int, val y: Int) {
  override def equals(other: Any): Boolean = other match {
    case p: GoodPoint => x == p.x && y == p.y
    case _ => false
  }
  override def hashCode: Int = (x, y).##
}
val g1 = new GoodPoint(1, 2)
val g2: Any = new GoodPoint(1, 2)
println(g1.equals(g2) + " " + (g1 == g2) + " " + List(g1).contains(g2))

true true true

A case class generates exactly this equals (and hashCode and toString) for you: CPoint(1,2) == CPoint(1,2) is true.

"Overriding" == is really overloading it

The slides ask: was the Rational example overriding ==, which is final on Any? No. A method def ==(rhs: Rational) has a different parameter type, so it is an overload.

case class Rational(n: Int, d: Int) extends Comparable[Rational] {
  def compareTo(rhs: Rational): Int = n * rhs.d - rhs.n * d
  def ==(rhs: Rational): Boolean = compareTo(rhs) == 0       // overload of ==
}
val r1 = Rational(1, 2)
val r2 = Rational(2, 4)
val r2any: Any = r2
println((r1 == r2) + " " + (r1 == r2any) + " " + r1.equals(r2))

true false false

r1 == r2: argument typed Rational, so your overload: 1*4 - 2*2 = 0, true. r1 == r2any: argument typed Any, so Any's final ==, which calls the case-class equals comparing fields (1,2) vs (2,4): false. (Side note: the slide version puts def ==(rhs: A) in the generic class Comparable[A]; Scala 2.13 rejects that with "name clash between defined and inherited member ... have same type after erasure", because a type parameter becomes Object at run time. The non-generic version above compiles.)

Both mechanisms in one call

val t2: Car = new Tesla
kind(t2)                          // "car(hum)"

Overload chosen from the static type (Car), then inside the body v.sound is an overridden method chosen from the object (Tesla). Exam answers that mix these up ("tesla", or "car(vroom)") are the distractors.

class Shop { def price(x: Any): String = "S-any"; def price(x: Int): String = "S-int" }
class Outlet extends Shop { override def price(x: Int): String = "O-int" }
val sh: Shop = new Outlet
val five: Any = 5
println(sh.price(5) + " " + sh.price(five) + " " + new Shop().price(5))

O-int S-any S-int

class A { def x: String = "a" }
class B extends A { override def x = "b" }
class C extends B { override def x = "c" }
def over(v: Any) = "any"; def over(v: A) = "A"; def over(v: B) = "B"
val q: B = new C
(over(q), q.x)

(B,c)

2 true

What a higher order function is, and how to read one

In Scala a function is a value, just like 3 or "hi". You can store it in a val, pass it as an argument and return it. A higher order function is a function that takes another function as an argument (or returns one). map, filter and the folds are all higher order: you hand them a small function and they apply it to the elements of a collection for you.

You write a small function inline as a lambda: x => x + 1 means "given x, return x + 1". The placeholder form _ + 1 means exactly the same thing. Each _ stands for a new parameter, in order, so _ + _ is a function of two arguments, (a, b) => a + b, not x => x + x.

A function that returns a Boolean, like _ > 10, is called a predicate. Most functions in this block take either a predicate (exists, forall, filter, count, takeWhile) or a transformation (map, flatMap) or a combining operator (the folds).

val twice = (f: Int => Int) => (x: Int) => f(f(x))   // takes a function, returns a function
println(twice(_ + 3)(1) + " " + twice(_ * 2)(5))
val isBig: Int => Boolean = _ > 10
println(List(5, 50).map(isBig) + " " + List(5, 50).filter(isBig))
println(List(1, 2, 3).map(x => x + x))

7 20
List(false, true) List(50)
List(2, 4, 6)

All the functions in this block work on immutable collections: they never change the list you call them on, they build and return a new value. List(1,2,3) is a list. A range like 0 until 9 (0 to 8, end excluded) or 1 to 4 (1 to 4, end included) is a Range; when you map or filter a range you get a Vector back, which is why answers often print as Vector(...).

val g = (x: List[List[Int]]) => x.map(_.filter(_ > 0)).filter(_.nonEmpty).map(_.max).map(n => List(n, n))

def applyAll(fs: List[Int => Int], x: Int): List[Int] = fs.map(f => f(x))
println(applyAll(List(_ + 1, _ * 2, x => x * x), 4))

List(5, 8, 16)

exists and forall

l.exists(p) asks: "is there at least one element for which p is true?" l.forall(p) asks: "is p true for every element?" Both return a single Boolean, not a list.

The empty list is where people go wrong. exists needs a witness, an element that proves the claim; an empty list has none, so List().exists(p) is false. forall is false only if you can find a counterexample, an element that breaks the claim; an empty list has none, so List().forall(p) is true. This is called vacuous truth: "every element of an empty list is even" is true because there is nothing to check.

val nums = List(3, 8, 5, 10)
println(nums.exists(_ > 9) + " " + nums.forall(_ > 2) + " " + nums.forall(_ % 2 == 0))
println(List[Int]().exists(_ > 0) + " " + List[Int]().forall(_ > 0))
println(List(List(1, 3), List()).exists(_.forall(_ % 2 == 0)))
println(List(List(1, 3), List()).forall(_.exists(_ % 2 == 0)))

true true false
false true
true
false

Line 3: the outer exists looks for one inner list where all elements are even. List(1,3) fails, but List() passes vacuously, so the answer is true. Line 4: the outer forall needs every inner list to contain an even number; List() contains nothing, so it fails, and the answer is false.

Another way to see it. exists is a chain of || starting from false, and forall is a chain of && starting from true:

// List(a, b, c).exists(p)  ==  false || p(a) || p(b) || p(c)
// List(a, b, c).forall(p)  ==  true  && p(a) && p(b) && p(c)
def ex[A](p: A => Boolean, l: List[A]): Boolean = l match {
  case Nil    => false
  case h :: t => p(h) || ex(p, t)
}

With zero elements only the start value is left: false for exists, true for forall. If you see recursion with case Nil => true and p(head) && rec(tail), that is forall; with Nil => false and || it is exists.

Short circuit. Both stop as soon as the answer is known: exists at the first true, forall at the first false. You only see this when the predicate has a side effect, such as printing:

def loud(x: Int): Boolean = { print(s"[$x]"); x > 4 }
val r1 = List(1, 7, 2, 9).exists(loud); println(" " + r1)
val r2 = List(1, 7, 2, 9).forall(loud); println(" " + r2)
val r3 = List(1, 7, 2, 9).filter(loud).nonEmpty; println(" " + r3)

[1][7] true
[1] false
[1][7][2][9] true

val grid = List(List(2, 4), List(), List(3, 6))
println(grid.exists(_.forall(_ % 2 == 0)) + " " + grid.forall(_.exists(_ % 2 == 0)) + " " +
        grid.forall(_.forall(_ % 2 == 0)) + " " + grid.exists(_.exists(_ % 2 == 1)))

true false false true

println(List(1, 2, 3).filter(_ > 1).map(_ * 2).exists(_ > 5))
println(List(1, 2, 3).map(_ * 2).filter(_ > 1).forall(_ > 3))

true
false

map

l.map(f) applies f to every element and returns a new collection of the results, same length, same order. The slide shows it as a machine that puts a smiley face on every shape: three shapes in, three smiley shapes out. If f: A => B then List[A].map(f): List[B].

println(List("hi", "scala", "fp").map(_.length))
println(List(List(1,2), List(3)).map(_.map(_ * 10)))
println(List(List(1,2), List(3)).map(_.sum))
println((1 to 4).map(_ * 2))

List(2, 5, 2)
List(List(10, 20), List(30))
List(3, 3)
Vector(2, 4, 6, 8)

As a recursive function, map is recognisable by its shape: one output element per input element, built with ::.

def mp[A, B](f: A => B, l: List[A]): List[B] = l match {
  case Nil    => Nil
  case h :: t => f(h) :: mp(f, t)
}

map on other containers. map exists on anything that "holds" values. Option holds zero or one value (Some(x) or None); Either holds a Left or a Right, and in Scala 2.13 map only touches a Right. The rule is always the same: the shape (the constructor) stays, only the value inside changes.

println(Some(2).map(_ * 4) + " " + (None: Option[Int]).map(_ * 4))
val e1: Either[String, Int] = Right(2)
val e2: Either[String, Int] = Left("oops")
println(e1.map(_ * 4) + " " + e2.map(_ * 4))

Some(8) None
Right(8) Left(oops)

Map fusion (slide): for pure f and g, l.map(f).map(g) == l.map(f andThen g). Two passes give the same list as one pass that does f then g. This is an example of equational reasoning: replacing code by code that is equal. The professor adds a condition: only if f and g are pure. A pure function has no side effects (no printing, no changing variables). With side effects the results are equal but the order of the effects differs:

def f(x: Int) = { print(s"f$x "); x + 1 }
def g(x: Int) = { print(s"g$x "); x * 10 }
val a = List(1, 2, 3).map(f).map(g); println("=> " + a)
val b = List(1, 2, 3).map(x => g(f(x))); println("=> " + b)

f1 f2 f3 g2 g3 g4 => List(20, 30, 40)
f1 g2 f2 g3 f3 g4 => List(20, 30, 40)

Paper method for chains: the pipeline table. Write one row per input element and one column per stage. A filter crosses out a row; a map rewrites the value. Never filter on the original values when the filter comes after a map.

println((0 until 6).map(_ * 3).map(n => if (n % 2 == 0) n / 2 else n).filter(_ > 3).map(_ - 1))

Vector(8, 5, 14)

var log = List[String]()
def f(x: Int) = { log = log :+ s"f$x"; x * 2 }
def g(x: Int) = { log = log :+ s"g$x"; x + 1 }
val r1 = List(1, 2).map(f).map(g); println(r1 + " " + log)
log = Nil
val r2 = List(1, 2).map(x => g(f(x))); println(r2 + " " + log)

List(3, 5) List(f1, f2, g2, g4)
List(3, 5) List(f1, g2, f2, g4)

foreach

l.foreach(f) calls f on every element, in order, only for its side effect, and returns Unit. Unit is Scala's "no useful value" type; it has one value, written (). So whatever f returns is thrown away. foreach is what you use to print or to update a var.

val u = List(1, 2, 3).foreach(x => x * 100)
println(u)
var total = 0
List(4, 5, 6).foreach(x => total += x)
println(total)
List("a", "b", "c").foreach(print); println()

()
15
abc

Compare with map, which keeps the return values. If you map a printing function you get the prints and a list of units:

val mapped = List(1, 2).map(x => println("side " + x))
println(mapped)

side 1
side 2
List((), ())

var n = 0
List(3, 4, 5).foreach(x => if (x % 2 == 1) n += x)
println(n)

8

var acc = ""
for (w <- List("a", "bb", "ccc"); if w.length != 2) acc = w + acc
println(acc)

ccca

filter, takeWhile, dropWhile

All three take a predicate and return a sub-list, keeping the original order. They differ in when they look:

• filter(p) looks at every element and keeps those where p is true. (filterNot(p) keeps those where it is false.) The slide picture is a coffee filter: everything is poured through, the grounds stay behind.
• takeWhile(p) walks from the front and keeps elements until the first one where p is false, then stops for good. Later elements are never kept, even if they pass.
• dropWhile(p) walks from the front and throws away elements until the first one where p is false; that element and everything after it is kept.

So takeWhile(p) ++ dropWhile(p) is always the whole list (that pair is span). On a sorted list takeWhile and filter often agree; on an unsorted list they do not.

val xs = List(1, 2, 5, 1, 7, 2)
println(xs.filter(_ < 3))
println(xs.takeWhile(_ < 3))
println(xs.dropWhile(_ < 3))
println(xs.filterNot(_ < 3))
println(xs.takeWhile(_ > 3) + " " + xs.dropWhile(_ > 3))
println(xs.span(_ < 3))
println(List(1,2,3,4,5).takeWhile(_ < 3) + " " + List(1,2,3,4,5).filter(_ < 3))

List(1, 2, 1, 2)
List(1, 2)
List(5, 1, 7, 2)
List(5, 7)
List() List(1, 2, 5, 1, 7, 2)
(List(1, 2),List(5, 1, 7, 2))
List(1, 2) List(1, 2)

Line 5 is the subtle one: the very first element, 1, fails _ > 3, so takeWhile takes nothing and dropWhile drops nothing.

val strs = List("apple", "fig", "kiwi", "banana")
println(strs.takeWhile(_.length > 3) + " " + strs.dropWhile(_.length > 3) + " " + strs.filter(_.length > 3))

List(apple) List(fig, kiwi, banana) List(apple, kiwi, banana)

println(List(4, 1, 6, 3, 8).dropWhile(_ % 2 == 0).takeWhile(_ < 5))
println(List(4, 1, 6, 3, 8).filter(_ % 2 == 0).takeWhile(_ < 7))

List(1)
List(4, 6)

count

l.count(p) returns how many elements satisfy p, as an Int. It is the same as l.filter(p).length, but without building the intermediate list. The exam mostly asks you to recognise correct and incorrect ways to write count, so here are both kinds side by side.

val ys = List(3, 8, 5, 10, 6)
println(ys.count(_ > 5))                                          // library
println(ys.filter(_ > 5).length)                                  // keep the matches, measure
println(ys.map(x => if (x > 5) 1 else 0).sum)                     // 1 per match, add up
println((for (y <- ys if y > 5) yield 1).sum)                     // guard, then 1 per match
println(ys.foldLeft(0)((c, y) => if (y > 5) c + 1 else c))        // accumulator
println(ys.map(_ > 5).length)                                     // WRONG
println((for (y <- ys) yield y > 5).length)                       // WRONG
println(ys.foldLeft(0)((c, y) => if (y > 5) 1 else 0))            // WRONG
println(ys.map(_ > 5))

3
3
3
3
3
5
5
1
List(false, true, false, true, true)

Why are the last three wrong? map(_ > 5) produces one Boolean per element (last line), and length counts the falses too, so you get the length of the list. A for ... yield without a guard is just a map, same problem. The broken fold returns 0 or 1 for the current element and ignores the accumulator c, so the result only describes the last element (6 > 5, so 1).

val l = List(7, 2, 9); val p: Int => Boolean = _ > 5
println(l.filter(p).size + " " + l.map(p).length + " " +
        l.foldLeft(0)((c, e) => c + (if (p(e)) 1 else 0)) + " " + l.foldLeft(0)((c, e) => if (p(e)) 1 else c))

2 3 2 1

println(List("apple", "fig", "kiwi", "banana").count(_.contains("a")))

2

For loop desugaring: the whole recipe

Syntactic sugar is nicer syntax for something you could already write. A Scala for loop is sugar: the compiler rewrites ("desugars") it into calls to foreach, map, flatMap and withFilter before doing anything else. The slides summarise: for loop = foreach, filter and for yield loop = map, filter, flatten, flatMap.

Vocabulary: in for (x <- l; if x > 1; y <- m) yield x * y, each name <- collection is a generator, each if cond is a guard (the ; before an if may be left out), and yield e says "collect the values of e".

You do not have to trust me on the rewrite: Scala can print what it turns a for into. This is real compiler output (only the noise prefixes $anon. and `package`. are removed):

for (x <- l) println(x)
for (x <- l if x > 1) println(x)
for (x <- l) yield x * 2
for (x <- l if x > 1) yield x * 2
for (x <- l; y <- m) yield x + y
for (x <- l; if x > 1; y <- m) yield x + y
for (x <- l; y <- m; z <- List(x, y)) yield z
for (x <- l; y <- m) println(x + y)

l.foreach(((x) => Predef.println(x)))
l.withFilter(((x) => x.>(1))).foreach(((x) => Predef.println(x)))
l.map(((x) => x.*(2)))
l.withFilter(((x) => x.>(1))).map(((x) => x.*(2)))
l.flatMap(((x) => m.map(((y) => x.+(y)))))
l.withFilter(((x) => x.>(1))).flatMap(((x) => m.map(((y) => x.+(y)))))
l.flatMap(((x) => m.flatMap(((y) => List.apply(x, y).map(((z) => z))))))
l.foreach(((x) => m.foreach(((y) => Predef.println(x.+(y))))))</code>

The recipe, applied from left to right:

1. No yield: every generator becomes foreach, nested inside the previous one.
2. With yield: the last generator becomes map; every earlier generator becomes flatMap.
3. A guard becomes .withFilter(cond) on the generator just before it. For the result, withFilter is the same as filter (it only skips building an in-between list), so exam answers write filter.
4. The body (after yield, or the loop body) goes inside the innermost lambda.
5. yield for (...) yield ... is not a second generator: the inner for is the body. The outer generator then becomes map (it is the last generator of the outer loop), and the result is nested.

Why flatMap for the earlier generators? For each x, the rest of the loop produces a whole collection (all the y results for that x). map would give a list of those collections; flatMap glues them into one flat collection, which is what a single for with several generators returns.

The result type follows the first generator. The outermost call is a method of the first collection, so a for over a List gives a List, over a Range gives an IndexedSeq (prints as Vector), over an Option gives an Option.

l.flatMap(((x) => m.withFilter(((y) => x.>(1))).map(((y) => x.*(y)))))

l.withFilter(((x) => x.>(1))).map(((x) => m.withFilter(((y) => y.>(x))).map(((y) => Tuple2.apply(x, y)))))

For loop without yield becomes foreach

A for without yield runs its body for its side effect and returns (). Each generator becomes a foreach, nested in the order written, so the first generator is the outer loop and the last one changes fastest, like the digits of an odometer.

val l = List(1, 2, 3)
val m = List(10, 20)
for (x <- l; y <- m) print(s"($x,$y)"); println()
l.foreach(x => m.foreach(y => print(s"($x,$y)"))); println()
val unitResult = for (x <- l) x * 2
println(unitResult)

(1,10)(1,20)(2,10)(2,20)(3,10)(3,20)
(1,10)(1,20)(2,10)(2,20)(3,10)(3,20)
()

A for works on anything that has these methods, not only lists. An Iterator (a one-pass producer of values, see the iterators lesson) has foreach and map, so for (x <- Iterator(5, 6, 7).map(_ * 2)) print(x) becomes Iterator(5, 6, 7).map(_ * 2).foreach(x => print(x)) and prints 101214 (run).

The same nesting order holds for for ... yield; only the method names change. So the odometer method below also answers "what is the value" questions with several generators.

Paper method: the odometer table. One column per generator, left to right. The rightmost column runs through all its values before the column to its left moves one step. Evaluate each guard as soon as all the names it uses are known; if it is false, skip that row and everything nested under it. Write down the yielded value for each surviving row, top to bottom.

println(for (i <- 1 to 3; j <- 1 to 3; if i <= j) yield (i, j))
println(for (j <- 1 to 3; i <- 1 to 3; if i <= j) yield (i, j))

Vector((1,1), (1,2), (1,3), (2,2), (2,3), (3,3))
Vector((1,1), (1,2), (2,2), (1,3), (2,3), (3,3))

Same pairs, different order: in the second loop j is the outer generator, so the pairs are grouped by j.

println(for (i <- 1 to 3; j <- i to 3) yield i * j)

Vector(1, 2, 3, 4, 6, 9)

println(for (a <- List(3, 6, 9); if a % 2 == 1; b <- 1 to 2) yield a + b)

List(4, 5, 10, 11)

for ... yield with one generator: map and filter (withFilter)

With one generator, for (x <- l) yield e is l.map(x => e). Add a guard and it becomes l.withFilter(x => cond).map(x => e), which gives the same result as l.filter(x => cond).map(x => e). The filter always comes before the map, because the guard tests the original element x, not the yielded value.

val l = List(1, 2, 3)
println(for (x <- l if x != 2) yield x * 10)
println(l.withFilter(_ != 2).map(_ * 10) + " " + l.filter(_ != 2).map(_ * 10))

List(10, 30)
List(10, 30) List(10, 30)

What is withFilter? filter builds a new, shorter list right away. withFilter does not build anything: it remembers the condition and applies it during the following map/flatMap/foreach. That saves one intermediate list. The values that come out are the same, so for "which expression is equivalent" questions filter and withFilter are interchangeable.

Nested yield for. If the yielded expression is itself a for ... yield, the outer loop maps each element to a whole inner collection. Result: a collection of collections.

println(for (i <- 1 to 3) yield for (j <- 1 to 3 if i < j) yield (i, j))

Vector(Vector((1,2), (1,3)), Vector((2,3)), Vector())

Note the empty Vector() for i = 3: the outer loop has no guard, so every i produces one inner vector, even an empty one. Desugared: (1 to 3).map(i => (1 to 3).filter(j => i < j).map(j => (i, j))).

println(for (a <- List(List(1, 2), List(5), List(7, 8, 9)) if a.length > 1) yield a.map(_ * 2))

List(List(2, 4), List(14, 16, 18))

val opt: Option[Int] = Some(5)
println(for (x <- opt if x > 9) yield x)

None

flatten (and flatMap = map then flatten)

flatten removes exactly one layer of nesting: it takes a list of lists and glues the inner lists together, in order. Its signature is def flatten[A](l: List[List[A]]): List[A]. Empty inner lists simply disappear, and a list of Options keeps only the Some values.

println(List(List(1, 2), List(), List(3)).flatten)
println(List(Some(1), None, Some(3)).flatten)
println(List(List(List(1), List(2)), List(List(3))).flatten)

List(1, 2, 3)
List(1, 3)
List(List(1), List(2), List(3))

flatMap(f) is map(f) followed by flatten. So f must return a collection (f: A => List[B]), and the result is List[B]. Compare the two signatures the exam uses:

def map[A, B]    (l: List[A], f: A => B)       : List[B]
def flatMap[A, B](l: List[A], f: A => List[B]) : List[B]
def flatten[A]   (l: List[List[A]])            : List[A]

println(List(1, 3).flatMap(x => List(x, x + 1)) + " " + List(1, 3).map(x => List(x, x + 1)))
println(List(1, 3).map(x => List(x, x + 1)).flatten)
println(List(1, 2, 3).flatMap(x => if (x > 1) Some(x) else None))

List(1, 2, 3, 4) List(List(1, 2), List(3, 4))
List(1, 2, 3, 4)
List(2, 3)

If f does not return a collection, flatMap does not compile: List(1, 2).flatMap(x => x * 2) gives error: type mismatch; found: Int, required: scala.collection.IterableOnce[?].

Flatten with folds. Gluing lists is ++, and the empty list is the neutral start, so all three folds flatten correctly: l.foldLeft(List[A]())(_ ++ _), l.foldRight(List[A]())(_ ++ _) and l.fold(List[A]())(_ ++ _). The fold sections explain why they agree (++ is associative and List() is its identity element). But swapping the operands does change the result, because ++ is not commutative:

println(List(List(1,2), List(3)).foldRight(List[Int]())(_ ++ _) + " " + List(List(1,2), List(3)).foldLeft(List[Int]())((a, x) => x ++ a))

List(1, 2, 3) List(3, 1, 2)

flatMap on your own types. Any type can define flatMap: "replace every element by a structure of the same kind, then merge". On a binary tree, it replaces every leaf by a whole tree:

sealed abstract class Tree[A] {
  def flatMap[B](f: A => Tree[B]): Tree[B] = this match {
    case Node(l, r) => Node(l.flatMap(f), r.flatMap(f))
    case Leaf(x)    => f(x)
  }
  def reduce(f: (A, A) => A): A = this match {
    case Node(l, r) => f(l.reduce(f), r.reduce(f))
    case Leaf(x)    => x
  }
}
case class Node[A](l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](x: A) extends Tree[A]
def split(x: Int): Tree[Int] = Node(Leaf(x - 1), Leaf(x * 10))
val t1 = Leaf(3).flatMap(split)
val t2 = t1.flatMap(split)
println(t1 + " " + t1.reduce(_ + _))
println(t2 + " " + t2.reduce(_ + _))

Node(Leaf(2),Leaf(30)) 32
Node(Node(Leaf(1),Leaf(20)),Node(Leaf(29),Leaf(300))) 350

The second flatMap hits both leaves: 2 becomes (1, 20) and 30 becomes (29, 300). reduce then combines the leaves following the tree: (1 + 20) + (29 + 300) = 350.

println(List(1,2,3).flatMap(x => List.fill(x)(x)) + " " + List(1,2,3).map(x => List.fill(x)(x)))

List(1, 2, 2, 3, 3, 3) List(List(1), List(2, 2), List(3, 3, 3))

println(List(List(3), List(1, 2), List()).flatten.map(_ + 1) + " " + List(List(3), List(1, 2), List()).map(_.map(_ + 1)))

List(4, 2, 3) List(List(4), List(2, 3), List())

for ... yield with several generators: flatMap

With two generators in the same for, the result is flat: for (x <- l; y <- m) yield e = l.flatMap(x => m.map(y => e)). Each x produces the list m.map(y => e), and flatMap glues those lists in the order of x.

val l = List(1, 2, 3)
val m = List(10, 20)
println(for (x <- l; y <- m) yield x + y)
println(l.map(x => m.map(y => x + y)))
println(l.map(x => m.map(y => x + y)).flatten)
println(for (x <- l) yield for (y <- m) yield x + y)

List(11, 21, 12, 22, 13, 23)
List(List(11, 21), List(12, 22), List(13, 23))
List(11, 21, 12, 22, 13, 23)
List(List(11, 21), List(12, 22), List(13, 23))

Lines 1 and 3 are the same flat list; lines 2 and 4 are the same nested list. So: two generators in one for = flatMap + map; a for nested in the yield = map + map.

Where does the guard go? A guard filters the generator just before it. With the guard between the generators, the outer list is filtered; with the guard at the end, the inner list is filtered (even if the condition mentions only x).

println(for (x <- l; if x > 1; y <- m) yield x * y)     // l.filter(_ > 1).flatMap(x => m.map(y => x * y))
println(for (x <- l; y <- m; if x > 1) yield x * y)     // l.flatMap(x => m.filter(y => x > 1).map(y => x * y))

List(20, 40, 30, 60)
List(20, 40, 30, 60)

Three generators: the first two become flatMap, the last map: l.flatMap(x => m.flatMap(y => List(x, y).map(z => z))) (compiler output above).

Mixing List and Option. The outermost method belongs to the first generator, so the first generator decides the result type. A List first and an Option inside works: List.flatMap accepts anything iterable, and an Option counts as a collection of 0 or 1 elements.

val opt: Option[Int] = Some(5)
println(for (x <- l; y <- opt) yield x + y)                                    // l.flatMap(x => opt.map(y => x + y))
println(for (x <- l; y <- (if (x % 2 == 1) Some(x) else None)) yield y * 100)
println(for (x <- opt; y <- Some(x + 1)) yield x * y)
println(for (x <- Option(3); y <- (None: Option[Int])) yield x * y)

List(6, 7, 8)
List(100, 300)
Some(30)
None

The other way round fails. Option.flatMap requires the function to return an Option, so an Option first with a List inside does not compile:

println(for (x <- Some(1); y <- List(1, 2)) yield x + y)

error: type mismatch;
 found   : List[Int]
 required: Option[?]

println(for (a <- List(1, 2); b <- List("x", "y")) yield s"$a$b")

List(1x, 1y, 2x, 2y)

println(for (x <- List(1, 2, 3); y <- List(x, x * 10) if y != 2) yield y)

List(1, 10, 20, 3, 30)

println(for (s <- List("ab", "cde"); c <- s) yield c.toUpper)

List(A, B, C, D, E)

Folds: the general idea, signatures and recursion shapes

A fold collapses a whole collection into one value by repeatedly combining an accumulator (the result so far) with the next element, using an operator you supply, starting from a start value z (often called the "zero"). Sum, product, max, count, exists, forall, map, filter, flatten: all of them are folds with a particular z and operator.

There are three folds, and they differ only in where the brackets go (the order in which the operator is applied). For List(a, b, c) and operator op:

Read the operator type to recognise the fold: the accumulator B sits on the left in foldLeft and on the right in foldRight. fold has only one type: the start value, the elements and the result must all be the same type (or a common supertype). That is why fold cannot turn strings into an Int:

println(List("ab", "cde").foldLeft(0)(_ + _.length) + " " + List("ab", "cde").foldRight(0)(_.length + _))
println(List("ab", "cde").fold(0)(_ + _.length))

5 5
error: value length is not a member of Any

(The common supertype of Int and String is Any, the top type, and Any has no length.)

The slides draw the three as trees with 7 elements. Here they are with 4 elements, op at every inner point, evaluated from the bottom up:

Recognising a fold from its recursion. The exam shows a recursive definition and asks which function it is. Learn the shapes:

def foldL[A, B](l: List[A], z: B, f: (B, A) => B): B = l match {
  case Nil    => z
  case h :: t => foldL(t, f(z, h), f)        // combine FIRST, then recurse with the new accumulator
}
def foldR[A, B](l: List[A], z: B, f: (A, B) => B): B = l match {
  case Nil    => z
  case h :: t => f(h, foldR(t, z, f))        // recurse FIRST, then combine the head with that result
}
println(foldL[Int, Int](List(1, 2, 3), 0, _ - _) + " " + foldR[Int, Int](List(1, 2, 3), 0, _ - _))

-6 2

Relatives: scanLeft and unfold. A scan is a foldLeft that writes down every intermediate accumulator. The library scanLeft includes the start value; a hand written one in an exam may not, so read its code. An unfold is the opposite of a fold: it starts from one seed value and produces a list. A step function returns Some((element, nextSeed)) to emit an element and continue, or None to stop.

println(List(1, 2, 3, 4).scanLeft(0)(_ + _) + " " + List(1, 2, 3, 4).scanLeft(10)(_ - _))
def unfold[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
  case None            => Nil
  case Some((a, next)) => a :: unfold(next)(f)
}
println(unfold(1)(n => if (n > 20) None else Some((n, n * 3))))

List(0, 1, 3, 6, 10) List(10, 9, 7, 4, 0)
List(1, 3, 9)

println(unfold(10)(n => if (n <= 0) None else Some((n % 3, n - 4))))

List(1, 0, 2)

foldLeft

l.foldLeft(z)(op) walks the list from left to right, carrying an accumulator. It starts with acc = z, and for each element x does acc = op(acc, x). At the end it returns acc. That is exactly this loop:

def fl[A, B](z: B)(op: (B, A) => B)(l: List[A]): B = {
  var acc = z
  for (x <- l) acc = op(acc, x)
  acc
}

Paper method: the accumulator table. Write z, then one row per element with the new accumulator. With a print in the operator you can watch Scala do the same:

def tl(acc: Int, x: Int) = { print(s"op($acc,$x) "); acc - x }
val k = List(1, 2, 3).foldLeft(0)(tl); println("=> " + k)

op(0,1) op(-1,2) op(-3,3) => -6

As brackets: ((0 - 1) - 2) - 3 = -6. String building shows the bracket structure directly:

println(List("a", "b", "c").foldLeft("z")(_ + _))
println(List("a", "b", "c").foldLeft("z")((acc, x) => s"($acc $x)"))

zabc
(((z a) b) c)

The accumulator can be any type, including a list, a tuple or a function. Building a list with foldLeft by prepending (::) reverses it; appending (:+) keeps the order:

println(List(1, 2, 3).foldLeft(List[Int]())((acc, x) => x :: acc))
println(List(1, 2, 3).foldLeft(List[Int]())((acc, x) => acc :+ (x * 10)))

List(3, 2, 1)
List(10, 20, 30)

Implementing the other functions with foldLeft. Pick the start value that is correct for the empty list, then write the step "old answer + one more element gives new answer":

def myCount[A](xs: List[A])(p: A => Boolean)  = xs.foldLeft(0)((c, x) => if (p(x)) c + 1 else c)
def myExists[A](xs: List[A])(p: A => Boolean) = xs.foldLeft(false)((b, x) => b || p(x))
def myForall[A](xs: List[A])(p: A => Boolean) = xs.foldLeft(true)((b, x) => b && p(x))
def myMap[A, B](xs: List[A])(f: A => B)       = xs.foldLeft(List[B]())((acc, x) => acc :+ f(x))
def myFilter[A](xs: List[A])(p: A => Boolean) = xs.foldLeft(List[A]())((acc, x) => if (p(x)) acc :+ x else acc)
def myFlatten[A](xs: List[List[A]])           = xs.foldLeft(List[A]())(_ ++ _)
val ns = List(4, 7, 2, 9)
println(myCount(ns)(_ > 3) + " " + myExists(ns)(_ > 8) + " " + myForall(ns)(_ > 1) + " " + myMap(ns)(_ + 1) + " " +
        myFilter(ns)(_ % 2 == 0) + " " + myFlatten(List(List(1), List(2, 3))))
println(myExists(List[Int]())(_ > 0) + " " + myForall(List[Int]())(_ > 0))

3 true true List(5, 8, 3, 10) List(4, 2) List(1, 2, 3)
false true

The operator is fixed before the fold starts. If you pass an overloaded method name like wins to foldLeft, Scala picks one overload at compile time from the static types ((Roshambo, Roshambo) => Roshambo), and that one is used for every step, whatever the runtime classes are. If instead you pass _.wins(_), each step is a method call on the accumulator, and dynamic dispatch picks the override of the accumulator's runtime class. (Overloading and dispatch are taught in the polymorphism lesson; for the fold, just trace step by step with the right method.)

println(List(4, 1, 3).foldLeft(2)((a, x) => a * x - 1))

17

println(List(2, 3, 4).foldLeft(1)((a, x) => a * 10 + x))

1234

sealed trait Hand
case object R extends Hand
case object P extends Hand
case object S extends Hand
def beats(a: Hand, b: Hand) = (a, b) match {
  case (P, R) | (R, S) | (S, P) => true
  case _ => false
}
def winner(a: Hand, b: Hand): Hand = if (beats(a, b)) a else b
println(List(P, S, R).foldLeft(P: Hand)(winner))

R

println((1 to 4).foldLeft(List[Int]())((acc, x) => if (x % 2 == 0) x :: acc else acc :+ x))

List(4, 2, 1, 3)

foldRight

l.foldRight(z)(op) puts the brackets on the right: a op (b op (c op z)). The start value z is combined with the last element first, and the operator takes the element first, accumulator second: op: (A, B) => B. The elements keep their left to right positions in the expression; only the grouping changes. So foldRight does not reverse the list.

Paper method: write the brackets, then evaluate from the innermost bracket outwards. The innermost bracket is (last op z).

def tr(x: Int, acc: Int) = { print(s"op($x,$acc) "); x - acc }
val k = List(1, 2, 3).foldRight(0)(tr); println("=> " + k)

op(3,0) op(2,3) op(1,-1) => 2

As brackets: 1 - (2 - (3 - 0)) = 1 - (2 - 3) = 1 - (-1) = 2. Compare foldLeft on the same list: -6. Side by side with strings:

println(List("a", "b", "c").foldLeft("z")(_ + _) + " " + List("a", "b", "c").foldRight("z")(_ + _))
println(List("a", "b", "c").foldLeft("z")((acc, x) => s"($acc $x)"))
println(List("a", "b", "c").foldRight("z")((x, acc) => s"($x $acc)"))

zabc abcz
(((z a) b) c)
(a (b (c z)))

Building a list with foldRight and :: keeps the order (it copies the list), while foldLeft with :: reverses:

println(List(1, 2, 3).foldLeft(List[Int]())((acc, x) => x :: acc) + " " + List(1, 2, 3).foldRight(List[Int]())((x, acc) => x :: acc))

List(3, 2, 1) List(1, 2, 3)

Folding functions. The accumulator can be a function. With andThen(f, g)(x) = g(f(x)) (first f, then g), foldLeft puts z at the start of the pipeline and foldRight at the end:

val fs: List[Int => Int] = List(_ * 2, _ + 3, _ * 4)
def andThen[A, B, C](f: A => B, g: B => C)(x: A): C = g(f(x))
val minus1: Int => Int = _ - 1
val left  = fs.foldLeft[Int => Int](minus1)(andThen(_, _))   // ((minus1 then *2) then +3) then *4
val right = fs.foldRight[Int => Int](minus1)(andThen(_, _))  // *2 then (+3 then (*4 then minus1))
println(left(1) + " " + right(1))

12 19

left(1): 1-1 = 0, *2 = 0, +3 = 3, *4 = 12. right(1): 1*2 = 2, +3 = 5, *4 = 20, -1 = 19.

println(List(4, 1, 3).foldRight(2)((x, a) => a * x - 1))

15

def stepL(acc: (Int, Int), x: Int): (Int, Int) = (acc._1 + x, acc._2 * 2 - x)
def stepR(x: Int, acc: (Int, Int)): (Int, Int) = (acc._1 + x, acc._2 * 2 - x)
println(List(1, 2, 3).foldLeft((0, 1))(stepL) + " " + List(1, 2, 3).foldRight((0, 1))(stepR))

(6,-3) (6,-9)

println(List(8, 4, 2).foldLeft(64)(_ / _) + " " + List(8, 4, 2).foldRight(1)(_ / _))

1 4

fold (order not specified)

l.fold(z)(op) also combines all elements, but it makes no promise about the grouping. It may group like foldLeft, like foldRight, or like a balanced tree (the slide picture), and it may use z more than once. Why would you want that? The slides give two reasons: it is easier to read (it says "the tree does not matter"), and the library can use that freedom to optimise, in particular to run in parallel: split the list into chunks, fold each chunk on a different processor starting from z, then combine the chunk results. That is the idea behind l.map(f).reduce(op) and MapReduce.

The price: the result is only well defined if the grouping and the number of zs cannot matter. The slide's fold requirement:

• z must be an identity element for op: a op z == z op a == a for all a.
• op must be associative: a op (b op c) == (a op b) op c for all a, b, c.

With both, every grouping gives the same answer, so fold, foldLeft and foldRight all agree. The slide examples are all of this kind:

def sum(x: List[Int])         = x.fold(0)(_ + _)
def product(x: List[Int])     = x.fold(1)(_ * _)
def maxL(x: List[Int])        = x.fold(Int.MinValue)(_ max _)
def minL(x: List[Int])        = x.fold(Int.MaxValue)(_ min _)
def all(x: List[Boolean])     = x.fold(true)(_ && _)
def any(x: List[Boolean])     = x.fold(false)(_ || _)

What a parallel fold does, simulated so you can see it. Split into chunks, foldLeft each chunk from z, then combine the chunk results with op:

def chunkedFold[A](xs: List[A], chunks: Int)(z: A)(op: (A, A) => A): A = {
  val size = math.max(1, (xs.length + chunks - 1) / chunks)
  xs.grouped(size).toList.map(_.foldLeft(z)(op)).reduce(op)
}
val six = List(1, 2, 3, 4, 5, 6)
for (c <- List(1, 2, 3))
  println(s"$c chunks: sum0=" + chunkedFold(six, c)(0)(_ + _) + " sum1=" + chunkedFold(six, c)(1)(_ + _) +
          " minus0=" + chunkedFold(six, c)(0)(_ - _))

1 chunks: sum0=21 sum1=22 minus0=-21
2 chunks: sum0=21 sum1=23 minus0=9
3 chunks: sum0=21 sum1=24 minus0=15

With (0, +), a monoid, the answer is always 21. With start 1, which is not an identity for +, each chunk adds an extra 1. With -, which is not associative, every split gives a different number.

On an ordinary List, Scala 2.13 happens to run fold as a foldLeft:

println(List(1, 2, 3).fold(0)(_ - _) + " " + List(1, 2, 3).foldLeft(0)(_ - _) + " " + List(1, 2, 3).foldRight(0)(_ - _))

-6 -6 2

Do not build on that. The contract of fold says the order is unspecified, so with a non-monoid you must treat the result as "not determined". Exam questions are written so that this does not matter: they compare fold with both foldLeft and foldRight, or ask which implementations are correct given the laws.

for (c <- List(1, 2, 3))
  println(s"$c chunks: max0=" + chunkedFold(List(-4, -2, -7, -1), c)(0)(_ max _) +
          " maxMin=" + chunkedFold(List(-4, -2, -7, -1), c)(Int.MinValue)(_ max _))

1 chunks: max0=0 maxMin=-1
2 chunks: max0=0 maxMin=-1
3 chunks: max0=0 maxMin=-1

val letters = List("a", "b", "c", "d", "e", "f")
for (c <- List(1, 2, 3))
  println(s"$c chunks: cat=" + chunkedFold(letters, c)("")(_ + _) + " x=" + chunkedFold(letters, c)("x")(_ + _))
println(List("a","b","c").foldLeft("x")(_ + _) + " " + List("a","b","c").foldRight("x")(_ + _))

1 chunks: cat=abcdef x=xabcdef
2 chunks: cat=abcdef x=xabcxdef
3 chunks: cat=abcdef x=xabxcdxef
xabc abcx

Associativity

An operator ⊕ is associative if the grouping of a chain does not matter: a ⊕ (b ⊕ c) == (a ⊕ b) ⊕ c for all a, b, c. The order of the operands stays the same; only the brackets move. Because foldLeft, foldRight and fold differ only in brackets (look at the trees), associativity is what makes them agree, provided the start value also behaves (next section).

Associative is not commutative. Commutative means you may swap operands: a ⊕ b == b ⊕ a. String and list concatenation are associative but not commutative ("ab" != "ba"), and they still work with fold, because no fold ever swaps operands; folds only regroup.

println(List(1.0, 2.0, 3.0).foldLeft(0.0)((a, b) => (a + b) / 2) + " " + List(1.0, 2.0, 3.0).foldRight(0.0)((a, b) => (a + b) / 2))

2.125 1.375

val id: Int => Int = x => x
val left2  = fs.foldLeft[Int => Int](id)(andThen(_, _))
val right2 = fs.foldRight[Int => Int](id)(andThen(_, _))
println(left2(1) + " " + right2(1))

20 20

Identity element

An identity element (also called unit or neutral element) for ⊕ is a value 𝟘 that changes nothing: a ⊕ 𝟘 == 𝟘 ⊕ a == a for every a. It must work on both sides. The start value of a fold should be an identity, because foldLeft puts z on the left of the first element, foldRight on the right of the last element, and a parallel fold may insert it many times. Only an identity is harmless in all those places.

def foldEquiv[A](z: A, f: (A, A) => A, xs: List[A]) =
  xs.fold(z)(f) == xs.foldLeft(z)(f) && xs.foldLeft(z)(f) == xs.foldRight(z)(f)
println(foldEquiv[Int](0, _ + _, six) + " " + foldEquiv[Int](0, _ - _, six) + " " +
        foldEquiv[String]("", _ ++ _, List("a","b")) + " " + foldEquiv[String]("bla", _ ++ _, List("a","b")) + " " +
        foldEquiv[Int](1, _ * _, six) + " " + foldEquiv[Int](0, _ max _, List(-3, -1)) + " " +
        foldEquiv[Int](Int.MinValue, _ max _, List(-3, -1)) + " " + foldEquiv[Int](0, _ - _, List()) + " " +
        foldEquiv[Int](0, _ - _, List(5)))

true false true false true true true true false

Two results need a comment. (0, max) on List(-3, -1) gives true: all three folds agree on the wrong answer 0 (max is associative and commutative, so 0 just sits in the comparison everywhere). Agreement is not the same as correctness; for "is this a correct max" the answer is still no. And (0, -) passes on the empty list (all give 0) but fails on List(5): foldLeft gives 0 - 5 = -5, foldRight gives 5 - 0 = 5. One element is enough to expose a one-sided identity.

println(List(2, 3).fold(0)(_ * _) + " " + List(2, 3).fold(1)(_ * _))

0 6

Monoid

The slide's "math aside": in abstract algebra a monoid is a set A together with an associative operator ⊕ and an identity element 𝟘, such that

• associativity: ∀ a b c, a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
• identity: ∀ a, a ⊕ 𝟘 = 𝟘 ⊕ a = a

"... exactly the arguments and requirements for fold!" A call l.fold(𝟘)(⊕) is well defined precisely when (A, ⊕, 𝟘) is a monoid. So when the exam asks whether fold is safe, or whether two folds always agree, it is asking: is this a monoid?

The first six rows are on the slide; the last three follow from the same two laws, and the exam uses all of them. Not monoids: (Int, -, 0), (Int, /, 1), (String, ++, "bla"), (Int, max, 0), averaging.

println(List(1, 2, 3, 4).fold(0)(_ + _) + " " + List(1, 2, 3, 4).fold(1)(_ * _) + " " + List(3, 9, 2).fold(Int.MinValue)(_ max _) + " " +
        List(true, false).fold(true)(_ && _) + " " + List(true, false).fold(false)(_ || _))
println(List("ab", "c", "de").fold("")(_ + _) + " " + List(List(1), List(2, 3)).fold(List[Int]())(_ ++ _))

10 24 9 false true
abcde List(1, 2, 3)