**Note:**

This blog is intended to record what I learned in *Functional Program Design in Scala*, rather than share the course materials. So there are two things that I won’t put up: my solution to assignments and topics which I’ve mastered already.

PLEASE NOTIFY ME if I broke Coursera Honor Code accidentally.

## Week 1

### Recap: Functions and Pattern Matching

### Recap: Collections

### Lecture 1.1 - Queries with For

- the for notation is essentially equivalent to the common operations of query languages for databases.

### Lecture 1.2 - Translation of For

the Scala compiler translates for-expressions in terms of map, flatMap and a lazy variant of filter.

1

2

3

4

5

6

7

8

9

10

11

12for (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

// withFilter is a variant of filter which does not produce an intermediate list

for (x <- e1; y <- e2; s) yield e3

// is translated to

x1.flatMap(x => for (y <- e2, s) yield e3)we can use

`for`

syntax for our own types as long as we define`map`

,`flatMap`

and`withFilter`

for these types.

### Lecture 1.3 - Functional Random Generators

we can use

`self =>`

at the begining of`class`

/`trait`

body to declare an alias for`this`

.1

2

3

4

5

6

7trait Generator[+T] {

self => // an alias for ”this”.

def map[S](f: T => S): Generator[S] = new Generator[S] {

// we cannot use this here (but Generator.this is ok)

def generate = f(self.generate)

}

}define a trait

`Generator[T]`

that generates random values of type`T`

:1

2

3

4

5

6

7

8

9

10

11

12

13

14

15trait Generator[+T] {

def generate: T

}

// some instances

val integers = new Generator[Int] {

val rand = new java.util.Random

def generate: Int = rand.nextInt()

}

val booleans = new Generator[Boolean] {

def generate: Boolean = integers.generate > 0

}

val pairs = new Generator[(Int, Int)] {

def generate = (integers.generate, integers.generate)

}how can we avoid the

`new Generator`

boilerplate since it’s not trivial? Use`for`

syntax:1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22// Ideally, we would like to write:

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

def pairs[T, U](t: Generator[T], u: Generator[U]) = for {

x <- t

y <- u

} yield (x, y)

// they would be expanded to:

val booleans = integers.map(x => x > 0)

def pairs[T, U](t: Generator[T], u: Generator[U]) = t.flatMap(x => u.map(y => (x, y)))

// so we have to define map and flatMap for trait Generator:

trait Generator[+T] {

self => // an alias for ”this”.

def generate: T

def map[S](f: T => S): Generator[S] = new Generator[S] {

def generate = f(self.generate)

}

def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {

def generate = f(self.generate).generate

}

}some helper functions:

1

2

3

4

5

6

7def single[T](x: T): Generator[T] = new Generator[T] {

def generate = x

}

def choose(lo: Int, hi: Int): Generator[Int] =

for (x <- integers) yield lo + x % (hi - lo)

def oneOf[T](xs: T*): Generator[T] =

for (idx <- choose(0, xs.length)) yield xs(idx)[Exercise] how to implement a generator that creates random

`Tree`

objects?1

2

3

4

5

6

7

8

9

10

11

12

13

14trait Tree

case class Inner(left: Tree, right: Tree) extends Tree

case class Leaf(x: Int) extends Tree

// my solution:

def trees: Generator[Tree] = for {

isLeaf <- booleans

tree <- if (isLeaf) leafs else inners

} yield tree

def leafs: Generator[Leaf] = for (x <- integers) yield Leaf(x)

def inners: Generator[Inner] = for {

left <- trees

right <- trees

} yield new Inner(left, right)random test: generate random test inputs.

1

2

3

4

5

6

7

8def test[T](g: Generator[T], runTimes: Int = 100)

(f: T => Boolean): Unit = {

for (i <- 0 until runTimes) {

val t = g.generate

assert(f(t), "assert failed for " + t)

}

println("passed %s tests".format(runTimes))

}

### Lecture 1.4 - Monads

a

`monad`

is a parametric type`M[T]`

with two operations:`flatMap`

(in the literature, flatMap is more commonly called`bind`

) and`unit`

, that have to satisfy some laws:1

2

3

4trait M[T] {

def flatMap[U](f: T => M[U]): M[U]

}

def unit[T](x: T): M[T]`List`

is a monad with`unit(x) = List(x)`

;`Set`

is monad with`unit(x) = Set(x)`

;`Generator`

is a monad with`unit(x) = single(x)`

`map`

can be defined for every monad as a combination of`flatMap`

and`unit`

:1

m map f = m flatMap (x => unit(f(x)))

to qualify as a monad, a type has to satisfy three laws:

associativity:

1

m flatMap f flatMap g == m flatMap (x => f(x) flatMap g)

left unit:

1

unix(x) flatMap f == f(x)

right unit:

1

m flatMap unit == m

[Note] you might find

`List`

doesn’t obey the`left unit`

rule since`List(1) flatMap (Set(_)) = List(1) != Set(1)`

, this is because the monad law assumes`f: A => M[A]`

(here`f: A => List[A]`

). Refer to link.1

List(1) flatMap (x => List(x, x)) = List(1, 1) == (x => List(x, x))(1)

what is the significance of the laws with respect to

`for`

syntax?associativity says essentially that one can “inline” nested for expressions:

1

2

3

4

5

6for (y <- for (x <- m; y <- f(x)) yield y

z <- g(y)) yield z

==

for (x <- m;

y <- f(x)

z <- g(y)) yield zright unit says:

1

for (x <- m) yield x == m

left unit does not have an analogue for for-expressions.

`Try`

is not a monad since it breaks the`left unit`

rule:`Try(expr) flatMap f != f(expr)`

: left-hand side will never raise a non-fatal exception whereas the right-hand side will raise any exception thrown by expr or`f`

.

`Try`

trades one monad law for another law which is more useful in this context:- an expression composed from
`Try`

,`map`

,`flatMap`

will never throw a non-fatal exception.

- an expression composed from

## Week 2

### Lecture 2.1 - Structural Induction on Trees

### Lecture 2.2 - Streams

streams is similar to lists, but their tail is evaluated only on demand.

1

2

3

4

5scala> Stream(1, 2, 3)

res0: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> res0.tail

res1: scala.collection.immutable.Stream[Int] = Stream(2, ?)we use

`#::`

instead of`::`

for stream prepending.- how to use stream to improve efficiency?
1

2

3

4

5

6// it is inefficient because it constructs all prime numbers between 1000

// and 10000 in a list, while what we need is only the second one.

((1000 to 10000) filter isPrime)(1)

// using stream only needs evaluate the first two prime numbers.

((1000 to 10000).toStream filter isPrime)(1)

### Lecture 2.3 - Lazy Evaluation

- in a purely functional language an expression produces the same result each time it is evaluated.
`lazy evaluation`

means evaluting on first demand, storing the result of the first evaluation and re-using the stored result instead of recomputing.- it’s not
`by-name evaluation`

where everything is recomputed. - it’s not
`restricted evaluation`

for normal parameters and`val`

definitions.

- it’s not
- Haskell use lazy evaluation by default, but Scala use stricted evaluation by default since it also supports mutable side effects (which might be inharmonious with lazy evaluation) in functions.

### Lecture 2.4 - Computing with Infinite Sequences

define an infinity stream:

1

2

3def from(n: Int): Stream[Int] = n #:: from(n+1)

// all natural numbers:

val nats = from(0)calculate all prime numbers:

1

2

3def sieve(s: Stream[Int]): Stream[Int] =

s.head #:: sieve(s.tail filter (_ % s.head != 0))

val primes = sieve(from(2))calculate the square root:

1

2

3

4

5

6

7

8def sqrtStream(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 2.5 - Case Study: the Water Pouring Problem

- a
**very decent solution**to`Water Pouring Problem`

, which is quite worthy of being reviewed. - some guiding principles for good design:
- name everything you can.
- put operations into natural scopes.
- keep degrees of freedom for future refinements.

## Week 3

### Lecture 3.1 - Functions and State

### Lecture 3.2 - Identity and Change

- the precise meaning of “being the same” is defined by the property of
`operational equivalence`

.`x`

and`y`

are operationally equivalent if`no possible test`

can distinguish between them.

### Lecture 3.3 - Loops

`for-loops`

is not`for-expression`

(end with`yield`

).- for-loops translate similarly to for-expression, but using
`foreach`

combinator instead of`map`

and`flatMap`

.1

2

3for (i <- 1 until 3; j <- "abc") println(i + " " + j)

// is translated to

(1 until 3) foreach (i => "abc" foreach (j => println(i + " " + j)))

### Lecture 3.4 - Extended Example: Discrete Event Simulation

### Lecture 3.5 - Discrete Event Simulation: API and Usage

### Lecture 3.6 - Discrete Event Simulation: Implementation and Test

## Week 4

### Lecture 4.1 - Imperative Event Handling: The Observer Pattern

- the
`Observer Pattern`

is widely used when views need to react to changes in a model. Variants of it are also called:- publish/subscribe.
- mode/view/controller (MVC).

### Lecture 4.2 - Functional Reactive Programming

- imperative reactive programming is about reacting to sequences of events that happen in time, while in functional view: aggregate an event sequence into a signal.
- generally, an indexted argument like
`f(E1,...,En) = E`

is translated to`f.update(E1,...,En, E)`

, which also works if`n = 0`

. `sig.update(5)`

can be abbreviated to`sig() = 5`

.- we cannot update signal value by
`s() = s() + 1`

, since this statement tries to define a signal to be at*all points in time*one larger than itself.

### Lecture 4.3 - A Simple FRP Implementation

### Lecture 4.4 - Latency as an Effect 1

### Lecture 4.5 - Latency as an Effect 2

### Lecture 4.6 - Combinators on Futures 1

### Lecture 4.7 - Combinators on Futures 2

- do not block when you have asynchronous computation.

### Lecture 4.8 - Composing Futures 1

### Lecture 4.9 - Implementation of flatMap on Future

### Lecture 4.10 - Composing Futures 2

## Conclusions

### How to Apply Functional Design Elements in Applications

- lazy evaluation and infinite data structures
- distinction between computations and values (e.g. a random value acctually is a computation).
- monads to abstract over properties of computation (randomness, delays, effects).
- running computations at some later time.