Functional programming principles in Scala (notes)

Cheat sheet

Based on this cheatsheet and tour of Scala

Evaluation rules (eager vs. lazy)

Constants

def example = 2      // evaluated when called
val example = 2      // evaluated immediately
lazy val example = 2 // evaluated once when needed

Method definitions

Call by value evaluates the arguments before calling the fn
Call by name evaluates the arguments after it has been called (i.e. when it is accessed) ~ lazy arguments

def square(x: Double)    // call by value
def square(x: => Double) // call by name
def myFct(bindings: Int*) = { ... } // bindings is a sequence of int, containing a varying # of arguments.

Higher order functions

Functions that take a fn as a parameter or return functions. Here, urlBuilder has a type of (Boolean, String) => (String, String) => String

def urlBuilder(ssl: Boolean, domainName: String): (String, String) => String = {
  val schema = if (ssl) "https://" else "http://"
  (endpoint: String, query: String) => s"$schema$domainName/$endpoint?$query"
}
// Let's call urlBuilder:
urlBuilder(true, "somedomain.com")("users", "id=1") // "https://somedomain.com/users?id=1": String

Here, sum is a fn which applies a computation f to two numbers and then adds them. It has a type of (Int => Int) => (Int, Int) => Int

def sum(f: Int => Int): (Int, Int) => Int = {  
  def sumf(a: Int, b: Int): Int = f(a) + f(b)  
  sumf  
} 
// Same as above, different syntax:
def sum(f: Int => Int)(a: Int, b: Int): Int = { ... } 
// Let's call sum:
def cube(x: Int) = x * x * x  
sum(x => x * x * x)(1, 10) // sum of 1 cubed and 10 cubed
sum(cube)(1, 10) // same as above

Currying

Converting a fn with multiple args into a fn with a single argument that returns another fn (allows partial application)

def f(a: Int, b: Int): Int // uncurried version (type is (Int, Int) => Int)
def f(a: Int)(b: Int): Int // curried version (type is Int => Int => Int)

We may use someFn.curried in order to transform a fn to its curried version, and Function.uncurried(someFn) to go back to the uncurried version

Classes

OOP concept. Blueprint of objects, they are templates containing fields and methods

See scala.Predef to learn more about require, assume, and assert

class MyClass(x: Int, val y: Int, var z: Int) {
// x will not be available outside MyClass
// val will generate a getter for y
// var will generate a getter and a setter for z
  require(y > 0, "y must be positive") // precondition, triggering an IllegalArgumentException if not met  
  def this (x: Int) = { ... } // auxiliary constructor   
  def nb1 = x // public method computed every time it is called    
  private def test(a: Int): Int = { ... } // private method  
  val nb3 = x + y // computed only once
  override def toString = x + ", " + y // overridden method
}
new MyClass(1, 2, 3) // creates a new object of type

Class hierarchies

abstract class TopLevel { // abstract class  
  def method1(x: Int): Int // abstract method  
  def method2(x: Int): Int = { ... }  
}

class Level1 extends TopLevel {  
  def method1(x: Int): Int = { ... }  
  override def method2(x: Int): Int = { ... } // TopLevel's method2 needs to be explicitly overridden
}

object MyObject extends TopLevel { ... } // defines a singleton object. No other instance can be created

To create a runnable app in Scala, either:

create an object with a method def main(args: Array[String])
create an object which extends App

Packages and imports

Classes and objects are organized in packages. They can be referenced through import statements

import myPackage.MyClass // 1 class
import myPackage._ // whole pkg
import myPackage.{MyClass1, MyClass2} // named import
import myPackage.{MyClass1 => A} // renamed

All members of packages scala and java.lang as well as all members of the object scala.Predef are automatically imported

Traits

Traits are used to share interfaces and fields between classes. They are similar to Java 8’s interface, except they can have concrete members (methods or fields). Classes and objects can extend traits.

trait Planar { ... }
class Square extends Shape with Planar

Object hierarchy (types)

Any is the supertype of all types. Defines equals, hashCode, toString. It has two direct subclasses:
- AnyVal represents value types, namely Double, Float, Long, Int, Short, Byte, Char, Unit, Boolean
  - Unit is a value type which carries no meaningful information, similar to void, sometimes declared as ()
- AnyRef represents reference types. All non-value types are reference types.
  - Every user-defined type is a subtype of AnyRef
Nothing is a subtype of all types (bottom type). It is used as return type for thrown exception, infinite loops, program exits
Null is a subtype of all reference types. It has a single value: null. Note: null is provided for interop purposes and should not be used.

Operators

myObject myMethod 1 is the same as calling myObject.myMethod(1)

Scala allows the omission of parentheses on methods of arity-0 (no arguments) which have no side effects. isEmpty ~ isEmpty()

Higher-order fn chaining: names map { _.toUpperCase } filter { _.length > 5 }

Type parameters

Similar to Java generics (A is used as a convention instead of T):

class MyClass[A](arg1: A) { ... }  
new MyClass[Int](1)  
new MyClass(1) // the type is being inferred

Upper and lower type bounds:

def myFct[A <: TopLevel](arg: A): A = { ... } // A must derive from TopLevel or be TopLevel
def myFct[A >: Level1](arg: A): A = { ... }   // A must be a supertype of Level1
def myFct[A >: Level1 <: TopLevel](arg: A): A = { ... }

Variance

Given A <: B (A is a subtype of B)

If C[A] <: C[B], C is covariant
If C[A] >: C[B], C is contravariant

Functions must be contravariant in their argument types and covariant in their result types. Note: Variance will be covered in the course

Pattern matching

Pattern matching is a mechanism for checking a value against a pattern. A successful match can also deconstruct a value into its constituent parts

// 1st example: match on value
val x: Int = Random.nextInt(10)

def matchTest(x: Int): String = x match {
  case 1 => "one"
  case 2 => "two"
  case _ => "other"
}
matchTest(3)  // prints other
matchTest(1)  // prints one

// 2nd example: match on type
def goIdle(device: Device) = device match {
  case p: Phone => p.screenOff
  case c: Computer => c.screenSaverOn
}

// 3rd example: match on case classes (~ Java records)
def showNotification(notification: Notification): String = {
  notification match {
    case Email(sender, title, _) =>
      s"You got an email from $sender with title: $title"
    case SMS(number, message) =>
      s"You got an SMS from $number! Message: $message"
    case VoiceRecording(name, link) =>
      s"You received a Voice Recording from $name! Click the link to hear it: $link"
  }
}

// 4th example: match on list
(someList: List[A]) match {
  case Nil => // empty list
  case x :: Nil => // list with only one element
  case List(x) => // same as above
  case x :: xs => // a list with at least one element. xs could be Nil or some other list
  case 1 :: 2 :: cs => ... // lists that starts with 1 and then 2
  case (x, y) :: ps => // a list where the head element is a pair
  case _ => ...            // default case if none of the above matches
}

// 5th example: match on Options
val myMap = Map("a" -> 42, "b" -> 43)
def getMapValue(s: String): String = {
  myMap get s match {
    case Some(nb) => "Value found: " + nb
    case None => "No value found"
  }
}
getMapValue("a")  // "Value found: 42"
getMapValue("c")  // "No value found"

// which can be expressed in terms of the Option type:
def getMapValue(s: String): String = myMap.get(s).map("Value found: " + _).getOrElse("No value found")

// 6th example: match using lambdas
val pairs: List[(Char, Int)] = ('a', 2) :: ('b', 3) :: Nil
val chars: List[Char] = pairs map {
  case (ch, num) => ch
}

Collection

Base classes

Iterable (collections you can iterate on)
Seq (ordered sequences)

Immutable collections

List (linked list, provides fast sequential access)
- Can be instantiated as List(1,2,3) or 1 :: 2 :: 3:: Nil (cons head-tail definition)
- Most operations can take a time of O(n)
Stream (same as List, except that the tail is evaluated only on demand)
- x #:: xs ~ Stream.cons(x, xs) the tail is a call by name param, hence it will be evaluated only when needed
- Infinite sequence of integers starting at start: def integers(start: Int = 0): Stream[Int] = start #:: integers(start + 1)
Vector (array-like type, implemented as tree of blocks, provides fast random access)
- Implemented as tree of blocks. Fast random access. O(log n) updates
Range (ordered sequence of integers with equal spacing). Understands until, to, by
String (Java type, implicitly converted to a character sequence, so you can treat every string like a Seq[Char])
Map (collection that maps keys to values)
Set (collection without duplicate elements)

Mutable collections

Array (native JVM arrays at runtime, performant)
Mutable maps and sets (more performant)

Pairs or tuples. Destructuring

val pair = ("answer", 42) // type: (String, Int)
val (label, value) = pair // label = "answer", value = 42
pair._1 // "answer"  
pair._2 // 42

Ordering

In order for a type to implement its single natural ordering, it should inherit from the trait scala.math.Ordered[A]. Ordering is a trait whose instances each represent a strategy for sorting instances of a type

val pairs = Array(("a", 5, 2), ("c", 3, 1), ("b", 1, 3))
// sort by 2nd element
Sorting.quickSort(pairs)(Ordering.by[(String, Int, Int), Int](_._2))

For comprehensions

A for comprehension is syntactic sugar for map, flatMap and filter operations on collections

The general form is for (s) yield e

s is a sequence of fields (generators and filters)
p <- e is a generator
if f is a filter
e is an element of the resulting collection
If there are several generators (nested loop) the last generator varies faster than the first
You can use a for-comprehension for your own type, as long as you define map, flatMap, and filter

Example:

// list all combinations of numbers x and y where x is drawn from
// 1 to M and y is drawn from 1 to N
for (x <- 1 to M; y <- 1 to N)
  yield (x,y)

which is equivalent to

(1 to M) flatMap (x => (1 to N) map (y => (x, y)))

Translation rules

for (x <- e1) yield e2 is translated to e1.map(x => e2)
for (x <- e1 if f; s) yield e2 is translated to for (x <- e1.withFilter(x => f); s) yield e2
for (x <- e1; y <- e2; s) yield e3 is translated to e1.flatMap(x => for (y <- e2; s) yield e3)

Note: for comprehensions will be covered later.

Style guide

Avoid casts and type tests

Do not cast
Do not use isInstanceOf or asInstanceOf

Avoid using `return`

Because in Scala control structures are expressions, you can assume the last expression evaluated will be returned

IDE Best practices

Indent with 2 spaces, no tabs
Use whitespace
Avoid long lines
Use local values
Choose meaningful names
Semicolons not required

Avoid mutability

Do not use side-effecting operations
Use helper functions

Common subexpressions

Avoid unnecessary invocations of methods

// bad: calls `this.findMin` twice
this.remove(this.findMin).ascending(t + this.findMin)
// better
val min = this.findMin
this.remove(min).ascending(t + min)

Course introduction

Sum a List of Int

def sum(xs: List[Int]): Int = {
  if(xs.isEmpty)
    0
  else
    xs.head + sum(xs.tail)
}

Max number in a List (tail recursion)

// Compare the first two elements and keep the max, keep going until tail is empty
def max(xs: List[Int]): Int = {
  if (xs.isEmpty) throw new NoSuchElementException
  else auxMax(xs.head, xs.tail)
}

def auxMax(head: Int, tail: List[Int]): Int = {
  if(tail.length == 0)
    head
  else
    auxMax(head max tail.head, tail.tail)
}

1.1 - Programming paradigms

Paradigms quick review

Imperative programming

Modifying mutable variables
Assignments
Control structures
Processor <=> memory
- Mutable variables ~ memory cells
- Variable dereferences ~ load instructions
- Variable assignments ~ store instructons
- Control structures ~ jumps
Problem 1 => scaling word-by-word programs => solved by using math, high-level abstractions (collections, documents, polynomials, strings)
Problem 2 => mutability is not defined in math theory. Example: String
Corollary: avoid mutations, favour abstraction and composition

Functional programming

Restricted sense: program without mutability, assignments, loops, etc (Haskell without IO monad)
Wider sense: focus on functions (first-class citizens) which can be:
- Produced
- Consumed
- Composed
- Defined, passed and returned like any other value
Not only has simpler reasoning and better modularity: it is good for exploiting parallelism in multicore and cloud computing (stateless)

1.2 - Elements of programming (elementary)

Primitive expressions which can be combined and abstracted

To evaluate a primitive expression, i.e. (2 * pi) * radius:

Take the leftmost operator
Evaluate its operands (left before right)
Apply the operator to the operands

Functions (evaluated in a similar way):

def power(x: Double, y: Int): Double = ...

Substitution model (reduction): all evaluations reduce an expression to a value, without side effects

Side effects cannot be expressed by the substitution model

1.3 - Evaluation Strategies and Termination

Call-by-value vs. call-by-name

Call-by-value: evaluates every function argument only once, at the beginning

CBV avoids repeated computations of the same argument
x: Int
val is by-value, evaluated at the point of definition

Call-by-name: a fn argument is not evaluated if it is not used inside the fn

CBN avoids computing unused parameters
x: => Int
def is by-name, it is evaluated on each use

Both strategies reduce to the same final values as long as:

The reduced expression consists of pure functions
Both evaluations terminate

What if termination is not guaranteed?

CBV evaluation terminates => CBN evaluation terminates (material conditional, so not true the other way around)

Example:

def first(x: Int, y: Int) = x
first(1, loop)
//
def x = loop // OK
val x = loop // infinite loop

1.4 - Conditionals and value definitions

if-else is used for expressions, not statements

def abs(x: Int) = if (x >= 0) x else -x

Boolean expressions use short-circuit evaluation

if (b) e1 else e2
// rewritten using boolean expressions:
(b && e1) || e2
// write short-circuiting `and` and `or` without && and ||
def and(x: Boolean, y: => Boolean): Boolean = if (x) y else false
def or(x: Boolean, y: => Boolean): Boolean = if (x) true else y
// note that the 2nd param is CBN

1.5 - Example: square roots with Newton's method

Write a function which calculates de square root of a parameter x, using Newton's method (start with an estimate y0 and improve it by taking y(n + 1) = (y(n) + x / y(n)) / 2 and so on)

def abs(x:Double) = if (x < 0) -x else x

def improve(guess: Double, x: Double) = (guess + x / guess) / 2

def isGoodEnough(guess: Double, newGuess: Double) = abs(guess - newGuess) / guess < 0.001

def sqrtIter(guess: Double, x: Double): Double = {
  val currentGuess = improve(guess, x)
  if (isGoodEnough(guess, currentGuess)) guess
  else sqrtIter(currentGuess, x)
}

def sqrt(x: Double) = sqrtIter(1.0, x)

1.6 - Blocks and Lexical Scope

Block

Delimited by {}
The last element of a block is an expression that defines its value => blocks are expressions
The definitions inside a block shadow definitions of the same names outside it, i.e.

val x = 0
def f:(y: Int) = y + 1
val result = {
val x = f(3)
x * x
} + x // 16

If a line ends in an infix operator, the compiler will asume the next line is part of the same expression

aVariable +
anotherVariable // interpreted as one-liner

1.7 - Tail recursion

Application rewriting rule

To evalute a function application f(e1, ..., en):

Evaluate e1, ..., en resulting in values v1, ..., vn (reduce params to values)
Replace the application with the body of f
The values replace the parameters of f

This means a function is a substitution in the code

If a function calls itself as its last action, the stack frame can be reused. This is called tail recursion

Tail recursive functions are iterative processes
Tail recursive functions are executed in constante stack space

In general, if the last action of a function consists of calling itself, one stack frame is sufficient for both functions. Such calls are called tail-calls

Tail vs. non-tail recursion

def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

This gcd recursive function calls itself as its last action (else case), it is tail recursive

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
// classic example
factorial(4)
-> if (4 == 0) 1 else 4 * factorial(4 - 1)
=> 4 * factorial(3)
=> 4 * (3 * factorial(2))
=> 4 * 3 * 2 * 1 == 120

In this classic factorial example, our expression becomes bigger and bigger until we can reduce it to the final value. These calls are not tail-calls because the reduction needs of all the intermediate results we need to keep => factorial is not tail recursive

Tail recursion in Scala

In Scala, only direct recursive calls to the current fn are optimized.

You can require that a fn is tail recursive using the @tailrec annotation

@tailrec
def gcd(a: Int, b: Int): Int =

If the annotation is given, and the implementation of gcd is not tail recursive, an error would be issued (SUPER OP)

Tail recursive factorial:

@tailrec
def factorialTail(total: Int, n: Int): Int = if (n == 1) total else factorialTail(total * n, n - 1)

def factorial(n: Int): Int = factorialTail(1, n)

Week 1 assignment

Github repo (private)

2.1 - Higher-order functions

Functional languages treat functions as first-class values => a function can be passed as a parameter and returned as a result. Example:

// sum of f(n) where n goes from a to b
def sum(f: Int => Int, a: Int, b: Int): Int = if (a > b) 0
else f(a) + sum(f, a + 1, b)
// first approach
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def cube(x: Int) = x * x * x
// using lambdas, which infer types
(x: Int) => x * x * x
def sumCubes(a: Int, b: INt) = sum(x => x * x * x, a, b)

Bonus: anonymous functions (lambdas) are syntactic sugar, because any lambda can be written as a block with a def f(...) = ... and an immediate reference to it

2.2 - Currying

Now sum returns a function which then does the rest (take 2 Int, etc)

def sum(f: Int => Int): (Int, Int) => Int {
  def sumF(a: Int, b: Int): Int = 
    if (a > b) 0
    else f(a) + sumF(a + 1, b)
  sumF
}
//
sum (cube) (1, 10) ~ (sum(cube) (1,10)

There is a special syntax which is equivalent:

def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b)
  0
else
  f(a) + sum(f)(a + 1, b)

This syntax creates a new function every time a parameter list (...) is applied

If this process is repeated n times, we will end with n nested functions, applying currying

Exercise

// what is the type of sum?
def sum(f: Int => Int)(a: Int, b: Int): Int
// type: (Int => Int) => (Int, Int) => Int
// write a product fn
def product(f: Int => Int)(a: Int, b: Int): Int =
  if(a > b) 1
  else f(a) * product(f)(a + 1, b)
// write a function which generalizes product, sum, and other operators (call it mapReduce)
def mapReduce(f: Int => Int, operator: (Int, Int) => Int, neutralElement: Int)(a: Int, b: Int): Int =
  if (a > b)
    neutralElement
  else
    operator(f(a), mapReduce(f, operator, neutralElement)(a + 1, b))
// writing factorial using this function
def factorial(n: Int) = mapReduce((x => x), (a, b) => a * b, 1)(1, n)

Important: notice how mapReduce has f as a mapper fn and operator as a reduce function

Bonus: functional types associate to the right

2.3 - Example: finding fixed points

Find fixed points of functions. A number x is called a fixed point of a function f if f(x) = x

For some functions, the fixed point is calculated as f(f(f...f(x)...))
sqrt(x) = y | y * y = x => y = x / y

From (1) and (2), sqrt(x) is a fixed point of y = x / y (because this equality is satisfied)

Remembering lesson 1.5, we could plug in this function and find the fixed point:

def sqrt(x: Double) = sqrtIter(1.0, x)
~
def sqrt2(x: Double) = fixedPoint(y => x / y)(1.0)

But it turns out that sqrt2 does not converge, because the estimate keeps varying too much and oscillates. We need to make better estimates, taking the mean value of x and f(x)

To do this, we can use HOF:

def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

This function averageDamp makes any f make better estimates, thus making sqrt2 converge when applied to fixedPoint

2.4 - Scala syntax summary

BNF notation review:

| alternative
[...] option (0 or 1)
{...} repetition (0 or more)

What can a type be? For now:

Type = SimpleType | FunctionType
SimpleType = Ident
FunctionType = SimpleType '=>' Type
    | '(' [Types] ')' '=>' Type
Types = Type { ',' Type }

This means

A Type can be a SimpleType or a FunctionType
A FunctionType has an arrow and its left type can be a simple Type or a set of Types

What can an expression be? Some examples:

An identifier x, isGood or literal 0, "abc"
A function sqrt(x) or operator -x application
A block { val x = math.abs(y); x * 2 }
An anonymous function x => x + 1

What can a definition be?

Def = FunDef | ValDef
FunDef = def ident { '(' [Parameters] ')' } // function definition
ValDef = val ident [':' Type] '=' Expr

Parameter = ident ':' [ '=>' ] Type // notice the optional '=>' for call by name
Parameters = Parameter {',' Parameter }

This means a definition can be:

A function def square(x: Int) = x * x
A value val y = square(2)

A parameter can be:

Call by value x: Int
Call by name y: => Double

2.5 and 2.6 - Functions and data

Let's design a package por doing rational arithmetic (a rational number are two integers x/y). For infix operators see 2.7

class Rational(x: Int, y: Int) {
  val numer = x
  val denom = y

  def toString: String = numer + "/" + denom

  def add(that: Rational): Rational =
  new Rational(
    numer * that.denom + that.numer * denom,
    denom * that.denom
  )
  def negate: Rational = new Rational(-numer, denom)
  def sub(that: Rational): Relational = add(that.neg) // DRY
}
val x = new Rational(1, 2)
x.numer // 1

The constructor is given with the class definition. Notice that Rational's methods return new instances of Rational

Now, let's make it so that any operation under Rational returns a simplified fraction:

class Rational ... {
private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
private val g = gcd(x, y)
val numer = x / g
val denom = y / g
...
}

This is good because we're defining the simplification on the constructor, so we're being DRY. Notice g is a val so it can be reused and not recalculated

Add a less method which returns if a rational smaller than other one, and a max method:

def less(that: Rational) = numer * that.denom < that.numer * denom

def max(that: Rational) = if (this.less(that)) that else this

Inside a class, this represents the object on which the current method is executed

Restrictions on objects

require
- Is used to enforce a precondition on the caller of a function
- Throws IllegalArgumentException
assert
- Is used to check the code of the function
- Throws AssertionError

val strange = new Rational(1, 0) // prevent this!

class Rational ... {
require(y != 0, "denominator must be nonzero") // throws on false
}

val x = sqrt(y)
assert(x >= 0) // throws on false

Constructors

The primary constructor takes the parameters of the class and is defined next to the class keyword and identifier

Secondary constructors:

def this(x: Int) = this(x, 1) // takes a single argument and calls the primary

Modify the Rational class so that numbers are unsimplified internally, but it is applied in toString:

class Rational(x: Int, y: Int) {
...
def toString = numer / g + "/" + denom / g
}

2.7 - Evaluation and operators

Let's extend the substitution model to classes and objects

How is an instantiation of the class new C(e1, ..., en) evaluated?

=> It is evaluated like a normal function. new C(v1, ..., vn) is already a value

How is the expression new C(v1, ..., vn).f(w1, ..., wn) (call a method on a class) evalated?

=> There are three substitutions here:

Replace the parameters of f with the arguments w (same as a function)
Replace the formal parameters of the class C with the arguments v
Important: replace this by the value of the object new C(...)

Operators

Let's write x + y instead of x.add(y)

Any method with a parameter can be used as an infix operator. x add y
Use a symbolic operator
Make sure of operator precedence looking at the precedence table

// notice the space between the operators and args/return type
def < (that: Rational) = ...
def + (that: Rational) = ...
def unary_- : Rational = // infix neg must use unary_ to avoid colliding with infix minus (-)
def - (that: Rational) = this + -that

Week 2 assignment

Github repo (private)

type FunSet = Int => Boolean // does a number belong to a set?
def contains(s: FunSet, elem: Int): Boolean = s(elem)
...
def union(s: FunSet, t: FunSet): FunSet = (x: Int) => contains(s, x) || contains(t, x)

def singletonSet(elem: Int): FunSet = (x: Int) => x == elem
def lessThanSet(elem: Int): FunSet = (x: Int) => x < elem
def greaterThanSet(elem: Int): FunSet = not(union(lessThanSet(elem), singletonSet(elem)))
...
val bound = 1000

def filter(s: FunSet, p: Int => Boolean): FunSet = (x: Int) => contains(s, x) && p(x)
def forall(s: FunSet, p: Int => Boolean): Boolean = {
  val filterSet = diff(s, p)
  @tailrec
  def iter(a: Int): Boolean = {
    if (math.abs(a) > bound) true
    else if (contains(filterSet, a)) false
    else iter(a + 1)
  }
  iter(-bound)
}
def exists(s: FunSet, p: Int => Boolean): Boolean = !forall(s, !p(_)) // make it short circuit inside and reverse the result
def map(s: FunSet, f: Int => Int): FunSet = (x: Int) => exists(s, y => f(y) == x) // *chef's kiss*

3.1 - Class hierarchies

Exercise: consider a class which implements sets of integers

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other: IntSet): IntSet
}

A way of implementing sets is using binary trees. There are two types of possible trees:

A tree for the empty set
A tree with and integer and two sub-trees

The right nodes always have greater values that their parent, and the left nodes, less. This is a persistent data structure, because changes do not delete old data

class Empty extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
  def union(other: IntSet): IntSet = other
}

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
  def contains(x: Int): Boolean =
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true
  def incl(x: Int): IntSet =
    if (x < elem) new NonEmpty(elem, left incl x, right)
    else if (x > elem) new NonEmpty(elem, left, right incl x)
    else this
  def union(other: IntSet): IntSet = ???
}

It would be better to have only a single empty IntSet, since we don't need many instances of it (we won't mutate it, ever). Let's use a singleton object for Empty:

object Empty extends IntSet {
  ...
  def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
}

Dynamic binding

The code invoked by a method call depends on the runtime type of the object that contains the method

3.2 - How classes are organized

Classes and objects are organized in packages

You can import a class in many ways:

import package.Class // import Class
import package._ // import everything from a package
import package.{Class1, Class2} // import both Class1 and Class2

Some entities are automatically imported, i.e. assert and require come from the scala.Predef package

Traits

Traits resemble interfaces in Java + they can contain fields and concrete methods

Traits cannot have parameters

A trait is declared like an abstract class:

trait Planar {
  def height: Int
  def width: Int
  def surface = height * width
}

class Square extends Shape with Planar with Movable

Classes, objects, and other traits can inherit from many traits

Class hierarchy

Top types

Any the base type of all types. hashCode, equals, toString, ==
AnyRef the base type of all reference types. Alias for java.lang.Object
AnyVal the base type of all primitive types

Nothing type

There is no value of type Nothing. It is used to:

signal abnormal termination
represent empty sets

Null type

Every reference class (under AnyRef) is also of type Null
null is the only value in the class Null
=> every reference has null as a value

Exceptions

throw Exc is used to throw an exception. The return type of Exception is Nothing

3.3 - Polymorphism

Polymorphism:

A function can be applied to arguments of many types (subtyping). Instances of a base class can be passed to a base class
The type can have instances of many types (generics). Instances of a function or class are created by type T parametrization

Type parametrization: classes and methods can have types as parameters (like List[Int])

A list is constructed from two building blocks:

Nil the empty list
Cons a cell containing an element and a pointer to the rest of the list

List(1, 2, 3) ~ 1 :: 2 :: 3 :: Nil

trait List[T] { 
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}
// using val in the constructor adds a field
// for Cons, val head is a valid implementation of the trait's def head
class Nil[T] extends List[T] {
  def isEmpty = true
  def head: Nothing = throw new NoSuchElementException("Nil.head") // exceptions' return type is Nothing. Remember Nothing is a bottom type => a T is a Nothing
  def tail = throw new NoSuchElementException("Nil.tail")
  def nth(Int: n) = ???
}

class Cons[T](val head: Int, val tail: List[T]) extends List[T] {
  def isEmpty = false
  def nth(Int: n) =
    if (n < 0) throw new IndexOutOfBoundsException("boom")
    if (n == 0) head else tail.take(n - 1)
}

Important note: the difference between val and def is mostly initialization. val fields are special cases of methods, so they can override methods and implement traits

The trait List takes a type parameter T. Cons has a head of type T and a tail of type List[T]

Sometimes type parameters can be left out when instantiating a class having type parameters

Type erasure

All type parameters and type arguments are removed before evaluating the program. This is called type erasure

Week 3 assignment

Github repo (private)

Objects everywhere

In a pure OOP language, every value is an object. In a class-based language, the type of each value is a class

This could mean Scala is not a pure OOP language (primitives don't appear to be objects). Int and Boolean map to Java's representation, but they can be treated as objects:

abstract class Boolean {
  def ifThenElse[T](t: =>, e: => T): T
  // ifThenElse(t, e) => cond ? t : e
  def && (x: Boolean): Boolean = ifThenElse(x, false)
  def || (x: Boolean): Boolean = ifThenElse(true, x)
  def unary_!: Boolean = ifThenElse(false, true)

  def == (x: Boolean): Boolean = ifThenElse(x, x.unary_!)
  def != (x: Boolean): Boolean = ifThenElse(x._unary_!, x)
  // false < true
  def < (x: Boolean) :Boolean = ifThenElse(false, x)
}

object true extends Boolean {
  def ifThenElse[T](t: => T, e: => T) = t
}
object false extends Boolean {
  def ifThenElse[T](t: => T, e: => T) = e
}

Another interesting case is Peano numbers, which can be implemented as classes for lazy operations

4.2 - Functions as objects

Functions in Scala are treated as objects. Functions are objects with apply methods. They are internally represented as classes which can be instantiated anonymously. This is important:

// here A is the input type parameter, B is the output type parameter
trait Function1[A, B] {
  def apply(x: A): B
}
...
// Scala defines this up to Function22, for 22 input parameters
trait Function22[A, ...] = ???
//*********
(x: Int) => x * x
// this anonymous function maps to the following block:
{ class Lambda extends Function1[Int, Int] {
    def apply(x: Int) = x * x
  }
  new Lambda
}
// using anonymous class syntax:
new Function1[Int, Int] {
  def apply(x: Int) = x * x
}
//*********
f(a, b)
// maps to:
f.apply(a, b)
//*********

Bonus eta-expansion: if we def f(x: Int), then f is not a function value. If f is used in a place where a Function type is expected, it is automatically converted to a lambda (x: Int) => f(x) which is then converted to what we see above

How to make List act as a constructor for a single element or empty list:

object List {
  def apply[T](x: T): List[T] = new Cons(x, new Nil) // x:Nil
  def apply[T]() = new Nil

}


### 4.3 - Subtyping and Generics
We have already seen two forms of polymorphism (subtyping - OOP, and generics - FP)

In Scala, you can combine **subtyping and generics**. How can they interact?

* **Type bounds:** type parameters `A` can be subject to subtype constraints
* **Variance:** how parametrized types behave under subtyping

##### Type bounds
Let's implement `assertAllPos`, which takes an `IntSet` and returns it if all elements are positive, throws an exception if not. This is the first *naive* declaration:

```scala
def assertAllPos(s: IntSet): IntSet

But there may be a better way. Consider:

If an IntSet is Empty, return it
Otherwise, if it is NonEmpty: if it passes the test, return it. If it does not, throw an exception

def assertAllPos[S <: IntSet](r: S): S

where S <: IntSet means S is a subtype of IntSet. IntSet is an upper bound of S

Upper bound: S <: T means S is a subtype of T
Lower bound: S >: T means S is a supertype of T
Mixed: S >: NonEmpty <: IntSet

Covariance

We know NonEmpty is a subtype of IntSet. But is List[NonEmpty] a subtype of List[IntSet]?

Yes. That is why the relationship between this two types is covariant: their subtyping relationship varies like the type parameter. List is a covariant type

Typing problem

// this is Java:
// create an array of NonEmpty
NonEmpty[] a = new NonEmpty[]{new NonEmpty(1, Empty, Empty)}
// reference it from IntSet array
IntSet[] b = a
b[0] = Empty
// remember b[0]'s reference == a[0]'s
NonEmpty s = a[0]

We just assigned an Empty set to a NonEmpty variable.

Java protected against this using a special RuntimeException called ArrayStoreException. Java stores in every array a type tag, which checks types at runtime when operating with arrays. If the type tags don't match, the exception is raised

Why does this happen with Array and not with List? Because Array is mutable and List is immutable

List is covariant, while Array is nonvariant

Liskov Substitution Principle

If A <: B, everything one can do with a value of type B one should be able to do with a value of type A

Function example

Let A and B be two function types

type A = IntSet => NonEmpty
type B = NonEmpty => IntSet

Then A <: B, because A satisfies the contract of B (you may pass a NonEmpty to both), but A can also take other types such as Empty, so A is a true subtype of B

4.4 Variance

Roughly, a type which accepts mutations of its elements should not be covariant. Immutable types can be covariant if some conditions are met

Definition of variance

Let C[T] be a parametrized type of A and B, and A <: B

If C[A] <: C[B] => C is covariant -> C[+A]
If C[A] >: C[B] => C is contravariant -> C[-A]
Neither are subtypes of the other => C is nonvariant -> C[A]

Typing rule for functions

If A2 <: A1 and B1 <: B2 => A1 => B1 <: A2 => B2 (see Function example)

Functions are contravariant in their argument types and covariant in their result type

trait Function1[-T, +U] ...

Variance checks

The compiler will check there are no problematic combinations, such as the Array problem. The rules are:

Covariant type parameters can only appear in method results
Contravariant type parameters can only appear in method parameters
Invariant type parameters can appear everywhere

Additionaly,

Covariant type parameters may appear in lower bounds of method type parameters
Contravariant type parameters may appear in upper bounds of method

Usage of lower bounds

Lower bounds are useful if we want to define a method such as:

def prepend(elem: T): List[T] new Cons(elem, this)

This method will not variance-check, because we are using T as a method parameters, and T is covariant (violation of rule 1). This is because prepend would violate the LSP:

List[IntSet] xs = new List[IntSet]
xs.prepend(Empty) // ok!
List[NonEmpty] ys = new List[NonEmpty]
ys.prepend(Empty) // type mismatch: required NonEmpty, found Empty

Now if we use a lower bound type, we can make it so that the input type parameter is variance-correct:

def prepend [U >: T] (elem: U): List[U] = new Cons(elem, this)

ys.prepend(Empty) // List[IntSet], the compiler found the best supertype as the return type for this operation!
List(1, "2", true) // List[Any]

Using the additional rule 1, this prepend method will now return a list of the closest supertype: List[IntSet]

4.5, 4.6 - Decomposition, Pattern matching

Suppose we want to write an interpreter for arithmetic expressions (numbers and addition). Let Expr be a base trait, and two subclasses, Number and Sum. Later, we will want to implement more expressions, such as Var and Prod

More generally, we want to access objects in an extensible class hierarchy

Case classes

A case class is similar to a normal class.

trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

It automatically defines companion objects with the apply method, so we can write Number(1) without the new keyword. We can use case classes with pattern matching:

def eval(e: Expr): Int = e match {
  case Number(n) => n
  case Sum(e1, e2) => eval(e1) + eval(e2)
  case Sum(Number(1), Var(x)) => x...
}

// in general:
e match {
  case (pattern1) => expr1
  ...
  case (patternN) => exprN
}
// if no match is found, a MatchError exception is thrown

Example:

eval(Sum(Number(1), Number(2)))
=>
Sum(Number(1), Number(2)) match { ... }
=>
eval(Number(1)) + eval(Number(2))
=>
Number(1) match { ... } + eval(Number(2))
=>
1 + eval(Number(2)) => 3

In pattern matching, a pattern can be:

Constructors
Variables (they get binded)
Wildcard patterns _
Constants
Composition of all the above

Traits and pattern matching

A nicer way of exposing a mathod in a base trait:

trait Expr {
  def eval: Int = this match { ... }
}

4.7 - Lists

Lists are immutable and recursive (Nil, Cons structure). Arrays are mutable and flat

nums = 1 :: (2 :: (3 :: (4 :: Nil))) ~ List(1, 2, 3, 4)
nums2 = 1 :: 2 :: 3 :: 4 :: Nil ~ List(1, 2, 3, 4)
empty = Nil

nums.head // 1
nums.tail // List(2, 3, 4)
nums.tail.head // 2

The :: operator is called cons (construction operator), and has right associativity. Methods ending in : are tipically right-hand operators

Lists and pattern matching

Nil or List() => matches empty list
p :: ps or p1 :: p2 :: ps => matches head and tail
List(x) => a list of length 1

Lists, sorting, and pattern matching

Insertion sort (quadratic time complexity):

def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case y :: ys => insert(y, isort(ys))
}

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List() => List(x)
  case y :: ys => if (x <= y) x :: xs else y :: y :: insert(x, ys)
}

Week 4 assignment

Github repo (private)

Functional programming principles in Scala (notes)

Cheat sheet

Evaluation rules (eager vs. lazy)

Higher order functions

Currying

Classes

Class hierarchies

Packages and imports

Traits

Object hierarchy (types)

Operators

Type parameters

Variance

Pattern matching

Collection

Base classes

Immutable collections

Mutable collections

Pairs or tuples. Destructuring

Ordering

For comprehensions

Translation rules

Style guide

Avoid casts and type tests

Avoid using return

IDE Best practices

Avoid mutability

Common subexpressions

Course introduction

Sum a List of Int

Max number in a List (tail recursion)

1.1 - Programming paradigms

Imperative programming

Functional programming

1.2 - Elements of programming (elementary)

1.3 - Evaluation Strategies and Termination

Call-by-value vs. call-by-name

1.4 - Conditionals and value definitions

1.5 - Example: square roots with Newton's method

1.6 - Blocks and Lexical Scope

1.7 - Tail recursion

Application rewriting rule

Tail vs. non-tail recursion

Tail recursion in Scala

Week 1 assignment

2.1 - Higher-order functions

2.2 - Currying

Exercise

2.3 - Example: finding fixed points

2.4 - Scala syntax summary

2.5 and 2.6 - Functions and data

Restrictions on objects

Constructors

2.7 - Evaluation and operators

Operators

Week 2 assignment

3.1 - Class hierarchies

Dynamic binding

3.2 - How classes are organized

Traits

Class hierarchy

Top types

Nothing type

Null type

Exceptions

3.3 - Polymorphism

Type erasure

Week 3 assignment

Objects everywhere

4.2 - Functions as objects

Covariance

Typing problem

Liskov Substitution Principle

Function example

4.4 Variance

Definition of variance

Typing rule for functions

Variance checks

Usage of lower bounds

4.5, 4.6 - Decomposition, Pattern matching

Avoid using `return`