# Week 1

## lecture "Recap: Functions and Pattern Matching"

recursive function + case classes + pattern matching: example JSON printer (Scala -> JSON)
pattern matching in Scala SDK: `PartialFunction` is a Trait with `def isDefinedAt(x: A): Boolean`

## lecture "Recap: Collections"
* `Iterable` (base class)
  * `Seq`
  * `IndexedSeq` concrete implems below :
    * `Vector`
    * etc.
  * `LinearSeq` concrete implems below :
    * `List` : concrete implem
    * etc.
 * `Set`
    * etc.
 * `Map`
    * etc.

All collections have *`map`, `flatMap`, `filter`, `foldLeft`, `foldRight`*
Idealized implementation of these functions use pattern matching.

*For expressions*:
* are interesting for simplifying combinations of `map`, `flatMap` and `filter`.
* can use pattern matching in the left-hand side. Example:
```scala
val data: List[JSON] = ...
for {
  JObj(bindings) <- data // implicit filter
  JSeq(phones) = bindings("phoneNumbers")
  JObj(phone) <- phones
  JStr(digits) = phone("number")
  if digits starstWith "212"
} yield (bindings("lastname"))
```

## lecture "Lecture 1.1 - Queries with For"

For expressions used as a DSL for database queries.

```scala
case classe Book(title: String, authors: List[String])

// mini database:
val book: List[Book] = List(
 Book(title="Effective Java", authors = List("Joshua Bloch"))

# queries:
// find books whose author's name is "Bird"
for (b <- books ; a <- b.authors if a startsWith "Bird")
yield b.title


// find names of all authors who have written at least 2 books
 {
  for {
   b1 <- books
   b2 <- books
   // if b1 != b2 # would return dupes
   if b1.title < b2.title
   a1 <- b1.authors
   a2 <- b2.authors
   if a1 == a2
 } yield a1
} distinct // otherwise, would return dupes

// or better, fix our model so that we don't need to use distinct in queries:
val book: List[Book] = Set( # use a Set instead of a List
 Book(title="Effective Java", authors = List("Joshua Bloch"))
```

## lecture "Translation of For"

`map`, `flatMap` and `filter` can be implemented with for expressions.
But the compiler implement for expresions with higher-order functions `map`, `flatMap` and `filter`.

```scala

// case 1:
for (x <- e1) yield e2
// is translated to: e1.map(x => e2)

// case 2:
for (x <- e1 if f; s) yield e2
// is translated to: for (x <- e1.withFilter(x => f); s) yield e2
// withFilter is a lazy variant of filter that does not produce intermediate list

// case 3:
for (x <- e1; y <- e2; s) yield e3
// is translated to:
// e1.flatMap(x => for (y <- e2; s) yield e3)
// and the translation continues...
```

This translation is not onyly done for collections.
It is useful for parsers, databases, etc.
Examples :
- ScalaQuery and Slick Scala libraries
- Microsoft LINQ (C#)
If you provide `map`, `flatMap` and `filter` in your own type, you can use for expressions.

## Functional random generators
Another *use of for expressions*: random value generator (strings, numbers, etc.)
```
trait Generator[T+] {
  def generate: T
}

val integers = new Generator[Int] {
 val rand = new java.util.Random
 def generate = rand.nextInt()
}

val booleans = new Generator[Boolean] {
 def generate = integers.generate > 0
}

val pairs = new Generator[(Int, Int)] {
 def generate = (integers.generate, integers.generate)
}

//etc.
```

How to reduce boiler-plate code?
```
trait Generator[T+] {

  self => // alias for 'this'

  def generate: T

  def map[S](f: T => S): Generator[S] {
   def generate = f(self.generate) // this.generate would lead to never-ending recursive call
   // other way : f(Generator.this.generate
  }

  def flatMap[S](f: T => Generator[S]: Generator[S] = new Generator[S] {
   def generate = f(self.generate).generate
  }

}

val booleans = for (x <- integers) yield x > 0

val pairs = for{
 x <- t
 y <- u
} yield (x, y)
```

```
def single ...

def oneOf[T](xs: T*) { //vararg
}

def lists: Generators[List[Int]] = for{
 isEmpty <- booleans
 list <- if (isEmpty) emptyLits else nonEmptyLists
} yield list

def emptyList = single(Nil)

def nonEmptyLists = for {
 head <- integers
 tail <- lists
} yield head :: tail
```

example: *tree generator*
application: *random testing* via property-based testing (cf. ScalaCheck library)

## Monads
*Monad* is a design pattern
A monad M is a parametric type M[T]:
- with 2 operations: *`flatMap`* (or *`bind`*) and *`unit`*
  having both of them gives `map` operation
- that statify *laws*

Examples:
 List is a monad with unit(x) = List(x)
 Set is a monad with unit(x) = Set(x)
 Option is a monad with unit(x) = Some(x)
 Generator is a monad with unit(x) = single(x)

 *3 laws*:
 - *associativity*: the result of two `bind` calls does not depend of their order ; ex: (x + y) + z = x + (y + z)
   `(m flatMap f) flatMap g == m flatMap ((x => f(x) flatMap g))`
 - *left unit*: `unit(x) flatMap f == f(x)`
 - *right unit*: `m flatMap unit == m`

*Monoid* is a simple form of monad that does not return anything

Examples:
`Option` is a monad
`Try` is not a monad (left unit law fails)

Additional law: "monads with zero" also define `withFilter`


# Week 2

## Structural Induction on Trees
Proving session on trees:

To prove a property P(t) for all trees t of a certain type, we'll need to:
- show that P(l) holds for all leaves l
- for each type of internal nodes t with subtrees s1, ..., sn, show that:
P(s1) ^ ... ^ P(sn) implies P(t)

Example: `IntSets`

## Stream
*Streams* are like lists with tail evaluated on demand (lazily)
=> short and elegant notation (/ recursive)

Example: find the second prime number between 1000 and 10000
```scala
((1000 to 10000) filter isPrime)(1)
```

see `#::` that applies to streams (because `::` produces a list, not a stream)

Implem:
```scala

trait Stream[+A] extends Seq[A] {
  def isEmpty: Boolean
  def head: A
  def tail: Stream[A]
}

object Stream {

 // note: the only difference with list is the type of the 2nd parameter:
 def cons[T] (hd: T, tl: => Stream[T]) = new Stream[T] {
  def isEmpty = false
  def head = hd
  def tail = tl
 }

 val empty = new Stream[Nothing] {
  def isEmpty = true
  def head = throw new NoSuchElementException("empty head")
  def tail = throw new NoSuchElementException("empty tail")
 }

}

class Stream[T+] {

 def filter(p: T => Boolean): Stream[T] {
  if (isEmpty) this
  elseif (p(head)) cons(head, tail.filter(p))
  else tail.filter(p)
 }

}
```

## lecture "Lazy evaluation"

Previous implem has an issue: if tail is called several times, stream will be recomputed.
Solution: store th 1st tail evaluation

Haskell uses lazy evaluation, by default.

Scala:
- uses strict evaluation, by default.
- allows lazy with `lazy val"

```
lazy val x = expr
```

Fix in our Stream implem:
```
 def cons[T] (hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  lazy val tail = tl
 }
```

## lecture "Case study: infinite streams"

ex:
```scala

// all integers:
def from(n: Int): Stream[Int] = n #:: from(n+1)

val naturalNumbers = from()
val multiplesOf4 = nats maps (_ * 4)
// etc.
```

### Usage #1 : Prime numbers via the *Sieve of Eratosthenes*
```scala
 def sieve(: Stream[Int]): Stream[Int}
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

 val primes = sieves(from(2))
```

### Usage #2 : square roots
```scala

 def srtStream(x: Double): Stream[Double] = {

  def improve(guess: Double) = (guess + x  / guess) / 2
  lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
  guesses
 }

 def isGoodEnough(guess: Double, x: Double) =
   math.abs((guess * guess - x) / x) < 0.0001

 sqrtStream(4) filter (isGoodEnough(_, 4))
```

## lecture "Case study: Water pouring problem"

cf. "Design of computer programs" (more imperative solution in Python)

How to use:
- a glass of 4 cl.
- a glass of 9 cl.
- a big jar
to fill to mesure 6 cl ?

Our model:
  Glass: Int
  State: Vector[Int]
  Moves:
    Empty(glass)
    Fill(glass)
    Pour(from, to)

```scala
class Pouring(capacity: Vector[Int]) {

 type State = Vector[Int]
 val initialState = capacity map (x => 0)

 trait  {
  def change(state: State): State
 }
 case class Empty(glass: Int) extends Move {
  def change(state: State) = state updated (glass, 0)
 }
 case class Fill(glass: Int) extends Move {
  def change(state: State) = state updated (glass, capacity(glass))
 }
 case class Pour(from: Int, to: Int) extends Move {
  def change(state: State) = {
   val amount = state(from) min (capacityt(to) - state(to))
   state updated (from, state(from) - amount) updated (to, state(to) + amount)
  }
 }

 val glasses = 0 until capacity.length

 val moves =
  (for (g <- glasses) yield Empty(g)) ++
  (for (g <- glasses) yield Fill(g)) ++
  (for (from <- glasses; to <- glasses if from != to) yield Pour(from, to)

}

class Path(history: List[Move], val endState: State) {
 def extend(move: Move) = new Path(move :: history, move change endState)
 override def toString = (history.reverse mkString " ") + "--> " + endState
}

val initialPath = new Path(Nil, initialState)

def from(path: Set[Path], explored: Set[Path]): Stream[Set[Path]] =
 if (paths.isEmpty) Stream.empty
 else {
  val more = for {
   path <- paths
   next <- moves map path.extend
  } yield next
  if (!explored contains next.endState)
  paths #:: from(more)
 }

val pathSets = from(Set(initialPath), explored ++ (more map (_.endState)), Set(inialState)
def solution(target: Int) Stream[Path] =
 for {
  pathSet <- pathSets
  path <- pathSet
  if (path.endState contains targer)
 } yield path


object Test {}
 val problem = new Pouring(Vector(4, 7))
 problem.moves

 problem.solutions(6)
}
```

Guidelines:
- name everything you can (do not use "single-letter variables like mathematicians")
- put operations into natural scopes i.e. change method inside Move class)
- keep degrees of freedom for future refinements


# Week 3: Functions and State

## lecture Functions and State
Until now, we wrote pure functions with immutable data.
=> `side-effet free`
But how to work with *mutable state*? When *time is important*?

Substitution model:
programs can be evaluated by *rewriting* (function applications).
All rewritings that terminate *lead to the same result* (cf. Church-Rosser theorem of lambda-calculus).

Stateful Objects:
Changes over time => state
An object has state if its behavior is influenced by its history.
Ex : a bank transaction depends on the state of bank accounts.

State implementation:
Via variables and assignments
```
class BankAccount {

 private var balance = 0

 def deposit(amount: Int): Unit =
  if (amount > 0) balance = balance + amount

 def withdraw(amount: Int): Int =
   if (0 < amount && amount <= balance) {
    balance = balance - amount
    balance
   } else throw new Error("insufficient funds")

  val account = new BankAccount
  account deposit 50
  account withdraw 20 # OK
  account deposit 40 # Error, different result
```

## lecture "Identity and change"
When are objects the same?

On values, yes (cf. referential transparency:
```
 val a = E
 val b = E
 ```

But with variables and mutable state, no:
```
 val account1 = new BankAccount
 val account2 = new BankAccount
```

Being the same = `operational equivalence`.
i.e. no possible (black box) test can distinguish between them.
```
test(account1, account2)
```

The substitution model cannot be used with assignments (or it becomes very complicated).

## lecture "loops"

Loops: main feature in imperative programming.
In FP:
- `while` loops are modeled with recursive functions. (tail recursive)
- classical `for` loops cannot be modeled via higher-order function (because of nested variable)
Scala has for-expressions like `for (i <- 1 until 3) ...` (cf. Collections#foreach)

## lecture "Extended Example: Discrete Event Simulation"
Use mutable variables to simulate changing quantities in real world.
Also structure a system with layers, in particular with a Domain Specific Language.

Example: digital circuit simulator
Use wires to combine base components that a have a reaction time (delay):
- inverter
- AND gate
- OR gate

half-adder (HA)

```

 // components with side effects
 def inverter(input: Wire, output: Wire): Unit
 def andGate(a1: Wire, a2: Wire, output: Wire): Unit
 def orGate(a1: Wire, a2: Wire, output: Wire): Unit


def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire): Unit = {
 val d, e = new Wire // internal wires
 orGate(a, b, d)
 andGate(a, b, c)
 inverter(c, e)
 andGate(d, e, s)
}

def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire):, cout: Wire): Unit = {
 val s, c1, c2 = new Wire // internal wires
 halfAdder(b, cin, s, c1)
 halfAdder(a, s, sum, c2)
 orGate(c1, c2, cout)
}
```

## lecture "Discrete Event Simulation: API and Usage"
Implementation of class Wire and its functions.

A discrete event simulator performs *actions* at a given *moment*.

An action is a function:
```
 type Action = () => Unit
```

Time is simulated.

Layers: user -> circuits (higher-level components) -> gates (wires & base components)-> (abstract) simulation

```
trait Simulation {
 def currentTime: Int = ???
 def afterDelay(delay: Int)(block: => Unit): Unit ???
 def run(): Unit = ???

class Wire {

 private var sigVal = false; // current value
 private var actions: List[Action] = List()

 def getSignal: Boolean = sigVal

 def setSignal(s: Boolean): Unit =
  if (s != sigVal) {
   sigVal = s
   actions foreach (_())
  }

 def addAction(a: Action): Unit = {
  actions = a :: actions
  a()
 }
}

def inverter(input: Wire, output: Wire) : Unit = {
 def invertAction(): Unit = {
  val inputSig = input.getSignal
  afterDelay(InverterDelay) { output setSignal !inputSig }
 }
 input addAction invertAction
}

def andGate(in1: Wire, in2: Wire, output: Wire) : Unit = {
 def andAction(): Unit = {
  val in1Sig = in1.getSignal
  val in2Sig = in2.getSignal
  afterDelay(AndGateDelay) { output setSignal (in1Sig && in2Sig) }
 }
 in1 addAction andAction
 in2 addAction andAction
}

def orGate(in1: Wire, in2: Wire, output: Wire) : Unit = {
 def orAction(): Unit = {
  afterDelay(OrGateDelay) { output setSignal (in1.getSignal | in2.getSignal) }
 }
 in1 addAction orAction
 in2 addAction orAction
}
```


## lecture "Discrete Event Simulation: implement and test"

Simulation trait has an *agenda* of actions to perform.

```
trait Simulation {
 type Action = () => Unit

 case class Event(time: Int, action: Action) # case class => easy to pattern-match on

 private type Agenda = List[Event]
 private var agenda: Agenda = List()

 private var curtime = 0
 def currentTime: Int = curtime

 def afterDelay(delay: Int)(block => Unit) {
  val item = Event(curentTime + delay, () => block)
  agenda = inster(agenda, item)
 }
}
```

## Summary:

State & assignments => more complicated (we lose referential transparency and substituion model)
but programs are simpler and concise.
=> trade-off