# Programming in Scala

by Luu Gia Thuy / @luugiathuy
April 12, 2015

### Functional Programming Functions are *first class citizens*: - they can be defined anywhere, including inside other functions - like any other value, they can be passed as parameters to functions and returned as results → *higher-order functions* - as for other values, there exists a set operators to compose functions
### Definitions A *definition* can be: - A *function definition* `def square(x: Int) = x * x` - A *value definition* `val y = square(2)` A *parameter*can be: - A *call-by-value* parameter, like `(x: Int)` - A *call-by-name* parameter, like `(y: => Int)`
### Blocks in Scala - A block is delimited by braces { ... }. - It contains a sequence of definitions or expressions. - *The last element of a block is an expression that defines its value.* - The definitions inside a block are only visible from within the block. - The definitions inside a block *shadow* definitions of the same names outside the block.
### Tail Recursion If a function calls itself as its last action, the function's stack frame can be reused. *Tail recursive* functions are iterative processes. One can require that a function is tail-recursive using a `@tailrec` annotation: ```scala @tailrec def gcd(a: Int, b: Int): Int = ... ```
### Higher-Order Function ```scala def sum(f: Int => Int, a: Int, b: Int): Int = if (a > b) 0 else f(a) + sum(f, a + 1, b) def sumInts(a: Int, b: Int) = sum(id, a, b) def sumCubes(a: Int, b: Int) = sum(cube, a, b) def sumFactorials(a: Int, b: Int) = sum(fact, a, b) def id(x: Int): Int = x def cube(x: Int): Int = x * x * x def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1) ``` The type `A => B` is the type of a function that takes an argument of type `A` and returns a result of type `B`.
### Anonymous Functions ```scala def sumInts(a: Int, b: Int) = sum(x => x, a, b) def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b) ```
### Currying ```scala 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 } def sumInts = sum(x => x) def sumCubes = sum(x => x * x * x) def sumFactorials = sum(fact) sumFactorials(10, 20) + sum(cube)(1, 10) ```
### Currying #### Multiple Parameter Lists ```scala def sum(f: Int => Int)(a: Int, b: Int): Int = if (a > b) 0 else f(a) + sum(f)(a + 1, b) ``` What is the type of `sum`? ```scala (Int => Int) => (Int, Int) => Int ```
### Classes and Objects ```scala class Rational(x: Int, y: Int) { def numer = x def denom = y } ``` This definition introduces 2 entities: - A new type, named `Rational` - A *constructor* `Rational` to create elements of this type. We call the elements of a class type *objects*. Objects of the class `Rational` have two *members*, `numer` and `denom`.
### Classes #### Preconditions ```scala class Rational(x: Int, y: Int) { require(y > 0, ”denominator must be positive”) ... } ``` #### Auxiliary Constructors ```scala class Rational(x: Int, y: Int) { def this(x: Int) = this(x, 1) ... } new Rational(2) > 2/1 ```
### Abstract Classes ```scala abstract class IntSet { def incl(x: Int): IntSet def contains(x: Int): Boolean } 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 } ```
### Object Definition ```scala object Empty extends IntSet { def contains(x: Int): Boolean = false def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty) } ``` This defines a *singleton object* named `Empty`. Singleton objects are values, so `Empty` evaluates to itself.
### Traits ```scala trait Planar { def height: Int def width: Int def surface = height * width } ``` Classes, objects and traits can inherit from at most one class but arbitrary many traits. ```scala class Square extends Shape with Planar with Movable ... ``` Traits resemble interfaces in Java, but are more powerful because *they can contains fields and concrete methods*. Traits cannot have constructor parameters. Traits are fully interoperable with Java only if they do not contain any implementation code.

### Scala's class hierarchy ### Top Types ||| |---|---| |`Any`|The base type of all types. Methods: `==`, `!=`, `equals`, `hashCode`, `toString`| |`AnyRef`|The base type of all reference types; Alias of `java.lang.Object`| |`AnyVal`|The base type of all primitive types.|
### Types #### The `Nothing` Type - `Nothing` is at the bottom of Scala’s type hierarchy. It is a subtype of every other type. - There is no value of type `Nothing`. - To signal abnormal termination - As an element type of empty collections
### Types #### The `Null` Type - Every reference class type also has `null` as a value. - The type of `null` is `Null`. - `Null` is a subtype of every class that inherits from `Object`; it is *incompatible* with subtypes of `AnyVal`.
### Type Parameters ```scala trait List[T] { def isEmpty: Boolean def head: T def tail: List[T] } class Cons[T](val head: T, val tail: List[T]) extends List[T] { def isEmpty = false } class Nil[T] extends List[T] { def isEmpty = true def head = throw new NoSuchElementException("Nil.head") def tail = throw new NoSuchElementException("Nil.tail") } ``` Like classes, functions can have type parameters too.
### Polymorphism We have seen two principal forms of polymorphism: - subtyping: instances of a subclass can be passed to a base class - generics: instances of a function or class are created by type parameterization.
### Type Bounds - `S <: T ` means: `S`is a subtype of `T` - `S >: T ` means: `S` is a supertype of `T`, `T` is a subtype of `S` Mixed Bounds: ```scala [S >: NonEmpty <: IntSet] ``` The *Liskov Substitution Principle*: ``` If A <: B, then everything one can to do with a value of type B one should also be able to do with a value of type A. ```
### Variance Say `C[T]` is a parameterized type and `A,B` are types such that `A <: B` ||| |---|---| |`C[A] <: C[B]`|`C` is *covariant*| |`C[A] >: C[B]`|`C` is *contravariant*| |neither `C[A]` or `C[B]` is a subtype of the other|`C` is *nonvariant*| Declare the variance of a type ```scala class C[+A] { ... } class C[-A] { ... } class C[A] { ... } ```
### Case Class ```scala trait Expr case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr ``` It also *implicitly* defines companion objects with apply methods. ```scala object Number { def apply(n: Int) = new Number(n) } object Sum { def apply(e1: Expr, e2: Expr) = new Sum(e1, e2) } ``` so we can write `Number(1)` instead of `new Number(1)`.
### Case Class - Pattern Matching Pattern matching is a generalization of switch from C/Java to class hierarchies. ```scala def eval(e: Expr): Int = e match { case Number(n) => n case Sum(e1, e2) => eval(e1) + eval(e2) } ``` A `MatchError` exception is thrown if no pattern matches the value of the selector.
### Forms of Patterns Patterns are constructed from: - constructors, e.g. Number, Sum, - variables, e.g. n, e1, e2, - wildcard patterns _, - constants, e.g. 1, true. Variables always begin with a lowercase letter. The same variable name can only appear once in a pattern. So, `Sum(x, x)` is not a legal pattern. Names of constants begin with a capital letter, with the exception of the reserved words `null`, `true`, `false`.

### Scala's Collection Hierarchy  ### For Expressions Let `persons` be a list of elements of class `Person`, with fields `name` and `age`. ```scala case class Person(name: String, age: Int) ``` To obtain the names of persons over 20 years old: ```scala for (p <- persons if p.age > 20) yield p.name ``` which is equivalent to: ```scala persons filter (p => p.age > 20) map (p => p.name) ```
### The Option Type ``` trait Option[+A] case class Some[+A](value: A) extends Option[A] object None extends Option[Nothing] ``` The expression `map get key` returns - `None` if `map` does not contains the given `key`, - `Some(x)` if `map` associates the given `key` with the value `x`.
### Lazy Evaluation ```scala def expr = { val x = { print(”x”); 1 } lazy val y = { print(”y”); 2 } def z = { print(”z”); 3 } z+y+x+z+y+x } expr ``` "`xzyz`" will be printed.
### Monad A monad is a parametric type `M[T]` with two operations, `flatMap` and `unit`, that have to satisfy some laws. ```scala trait M[T] { def flatMap[U](f: T => M[U]): M[U] } def unit[T](x: T): M[T] ```
### Monad Laws To qualify as a nomad, a type has to satify three laws: #### Associativity ```scala m flatMap f flatMap g == m flatMap (x => f(x) flatMap g) ``` #### Left unit ```scala unit(x) flatMap f == f(x) ``` #### Right unit ```scala m flatMap unit == m ```
### Example of Monads - List is a monad with `unit(x) = List(x)` - Set is monad with `unit(x) = Set(x)` - Option is a monad with `unit(x) = Some(x)` - Generator is a monad with `unit(x) = single(x)`
## References * [Functional Programming Principles in Scala - Coursera](https://www.coursera.org/course/progfun) * [Principles of Reactive Programming - Coursera](https://www.coursera.org/course/reactive)