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
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
andfilter
. - can use pattern matching in the left-hand side. Example:
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"))
For expressions used as a DSL for database queries.
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"))
map
, flatMap
and filter
can be implemented with for expressions.
But the compiler implement for expresions with higher-order functions map
, flatMap
and filter
.
// 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
andfilter
in your own type, you can use for expressions.
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)
Monad is a design pattern A monad M is a parametric type M[T]:
- with 2 operations:
flatMap
(orbind
) andunit
having both of them givesmap
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
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
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
((1000 to 10000) filter isPrime)(1)
see #::
that applies to streams (because ::
produces a list, not a stream)
Implem:
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)
}
}
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
}
ex:
// all integers:
def from(n: Int): Stream[Int] = n #:: from(n+1)
val naturalNumbers = from()
val multiplesOf4 = nats maps (_ * 4)
// etc.
def sieve(: Stream[Int]): Stream[Int}
s.head #:: sieve(s.tail filter (_ % s.head != 0))
val primes = sieves(from(2))
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))
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)
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
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
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).
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 likefor (i <- 1 until 3) ...
(cf. Collections#foreach)
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)
}
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
}
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)
}
}
State & assignments => more complicated (we lose referential transparency and substituion model) but programs are simpler and concise. => trade-off