CS-210 Functional Programming Principles in Scala
- Books
- Call-by-name (CBN), call-by-value (CBV)
- Blocks and lexical scope
- Tail recursion
- Higher-Order Functions
- Currying
- Classes: functions and data
- Class Hierarchies
- Lists
- Implicit parameters
- Proof techniques
- Other collections
- For-Expressions
- Monads
- Streams
- Functions and State
- Lisp
Books
- Structure and Interpretation of Computer Programs, Harold Abelson and Gerald Jay Sussman, MIT Press
- Programming in Scala, Martin Odersky, Lex Spoon and Bill Venners, 2nd edition, Artima 2010
Call-by-name (CBN), call-by-value (CBV)
Let’s say we have the following function, and that we call it in the following way:
1
2
3
def test(x: Int, y: int) = x * x
test(3+4, 2)
There are 2 strategies to solving this: send the function the uncalculated arguments (CBN) or calculate the arguments and then send them to the function (CBV).
- CBN and CBV reduce an expression to the same value as long as both evaluations terminate.
- If CBV evaluation of an expression e terminates, then CBN evaluation of e terminates too
- The other direction is not true.
Here’s an example:
1
2
3
4
5
def first(x: Int, y: Int) = x
def loop: Int = loop
first(1, loop) // reduces to 1 under CBN since loop isn't run
first(1, loop) // does not terminate under CBV
Scala normally uses CBV, but you can force CBN with the =>
.
1
2
3
def contOne(x: Int, y: => Int) = 1
def or(x: Boolean, y: => Boolean) = if (x) y else false // we need to return y as a value, not a function.
Value definitions
Using def
is CBN, but val
is CBV.
1
2
3
4
5
val x = 2 // x refers to 2
val y = square(x) // y refers to 4, and not the function square(x)
def x = loop // OK
val x = loop // does not terminate since loop is evaluated
Blocks and lexical scope
To avoid namespace pollution, we can use nested functions:
1
2
3
4
5
6
7
8
9
10
11
12
13
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess)) guess
else sqrtIter(improve(guess))
def isGoodEnough(guess: Double) =
abs(guess * guess - x) / x < 0.001
def improve(guess: Double) =
(guess + x / guess) / 2
sqrtIter(1.0)
}
This is done using a block, delimited by { ... }
braces. The last element of a block is an expression that defines its return value.
The definitions inside a block are only visible from within the block. The block has access to what’s been defined outside of it, but if it redefines an external definition, the new one will shadow the old one, meaning it will be redefined inside the block.
Tail recursion
If a function calls itself as its last action, then the function’s stack frame can be reused. This is called tail recursion. In practice, this means that recursion is iterative in Scala, and is just as efficient as a loop.
One can require that a function is tail-recursive using a @tailrec
annotation:
1
2
@tailrec
def gcd(a: Int, b:Int): Int = ...
An error is issued if gcd
isn’t tail recursive.
Higher-Order Functions
Functions that take other functions as parameters or that return functions as results are called higher order functions, as opposed to a first order function that acts on simple data types.
1
2
3
4
5
6
7
8
9
10
11
12
13
// Higher order function
// Corresponds to the sum of f(n) from a to b
def sum(f: Int => Int, a: Int, b: Int): =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
// Different functions f
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
// Calling our higher order function
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumCubes(a: Int, b: Int): Int = sum(cube, a, b)
Anonymous functions
Instead of having to define a cube
and id
function in the example above, we can just write an anonymous function as such:
1
2
def sumInts(a: Int, b:Int): Int = sum(x => x, a, b)
def sumCubes(a: Int, b: Int): Int = sum(x => x*x*x, a, b)
Currying
From Wikipedia:
Currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument.
Essentially, with currying we do the following transition:
1
2
3
4
5
6
7
def f(x: Int): Int = x + y
f(1, 2) // evaluates to 3
def curry(f: (Int, Int) => Int): Int => (Int => Int) = x => y => f(x, y)
curry(f) // evaluates to x => (y => x + y)
curry(f)(1) // evaluates to y => y + 1
curry(f)(1)(2) // evaluates to 3
Using currying, we can once more improve our sum
function:
1
2
3
4
5
6
7
8
9
10
11
12
def sum(f: Int => Int): (Int, Int) => Int = { // Higher order function
def sumF(a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sumF(a + 1, b)
sumF // Returns another function
}
sum(cube)(1, 10) // equivalent to sumCubes
// Syntactic sugar:
def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a+1, b)
Function application associates to the left so sum(cube)(1, 10)
is equivalent to (sum(cube))(1, 10)
.
The type of sum
is (Int => Int) => (Int, Int) => Int
. This should be read and understood as (Int => Int) => ((Int, Int) => Int)
as functional types associate to the right.
Classes: functions and data
In Scala, we use classes to define and create data structures:
1
2
3
4
5
6
class Rational(x: Int, y: Int) {
def numer = x
def denom = y
}
val x = new Rational(1, 2)
This introduces two entities:
- A new type named
Rational
- A constructor
Rational
to create elements of this type
Methods
One can go further and also package functions operating on a data abstraction into the data abstraction itself. Such functions are called methods.
1
2
3
4
5
6
7
8
9
10
11
class Rational(x: Int, y: Int) {
def numer = x
def denom = y
def add(that: Rational) =
new Rational(
numer * that.denom + that.numer * denom,
denom * that.denom)
override def toString = numer + "/" + denom
}
Identifier
The identifier is alphanumeric (starting with a letter, followed by letters or numbers) xor symbolic (starting with a symbol, followed by other symbols). We can mix them by using an alphanumeric name, an underscore _
and then a symbol.
Small practical trick: to define a neg
function that returns the negation of a Rational
, we can write:
1
2
3
4
5
class Rational(x: Int, y: Int) {
...
def unary_- : Rational = new Rational(-numer, denom) // space between - and : because : shouldn't be a part of the identifier.
}
The precedence of an operator is determined by its first character, in the following priority (from lowest to highest):
- All letters
|
^
&
< >
= !
:
+ -
* / %
- All other symbolic characters
Infix notation
Any method with a parameter can be used like an infix operator:
1
2
3
r add s r.add(s)
r less s /* in place of */ r.less(s)
r max s r.max(s)
Constructors
Scala naturally executes the code in the class body as an implicit constructor, but there is a way to explicitly define more constructors if necessary:
1
2
3
4
5
6
class Rational(x: Int, y: Int) {
def this(x: Int) = this(x, 1)
def numer = x
def denom = y
}
Data abstraction
We can improve Rational
by making it an irreducible fraction using the GCD:
1
2
3
4
5
6
7
class Rational(x: Int, y: Int) {
private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
val numer = x / gcd(x, y) // Computed only once with a val
val denom = y / gcd(x, y)
...
}
There are obviously multiple ways of achieving this; the above code just shows one. The ability to choose different implementations of the data without affecting clients is called data abstraction.
Assert and require
When calling the constructor, using a denominator of 0 will eventually lead to errors. There are two ways of imposing restrictions on the given constructor arguments:
require
, which throws anIllegalArgumentException
if it failsassert
, which throws anAssertionError
if it fails
This reflects a difference in intent:
require
is used to enforce a precondition on the caller of a functionassert
is used to check the code of the function itself
1
2
3
4
5
6
class Rational(x: Int, y: Int) {
require(y != 0, "denominator must be non-zero")
val root = sqrt(this)
assert(root >= 0)
}
Class Hierarchies
Abstract classes
Just like in Java, we can have absctract classes and their implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
class Empty extends IntSet { // Empty binary tree
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
}
class NonEmpty(elem: Int, left: IntSet, right: Intset) extends IntSet { // left and right subtree
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)
if (x > elem) new NonEmpty(elem, left, right incl x)
else this // already in the tree, nothing to add
}
Terminology
Empty
andNonEmpty
both extend the classIntSet
- The definitions of
incl
andcontains
implement the abstract functions ofIntSet
- This implies that the types
Empty
andNonEmpty
conform to the typeIntSet
, and can be used wherever anIntSet
is required IntSet
is the superclass ofEmpty
andNonEmpty
Empty
andNonEmpty
are subclasses ofIntSet
- In Scala, any user-defined class extends another class. By default, if no superclass is given, the superclass is
Object
- The direct or indirect superclasses are called base classes
Override
It is possible to redefine an existing, non-abstract definition in a subclass by using override
.
1
2
3
4
5
6
7
8
9
abstract class Base {
def foo = 1
def bar: Int
}
class Sub extends Base {
override def foo = 2 // You need to use override
def bar = 3
}
Overriding something that isn’t overrideable yields an error.
Traits
In Scala, a class can only have one superclass. But sometimes we want several supertypes. To do this we can use traits. It’s declared just like an abstract class, but using the keyword trait
:
1
2
3
4
5
trait Planar {
def height: Int // Abstract method as it lacks an implementation
def width: Int
def surface = height * width // Concrete method defining a default implementation
}
Classes, objects and traits can inherit from at most one class but as arbitrarily many traits.
1
class Square extends Shape with Planar with Movable ...
Traits cannot have value parameters, only classes can.
Singleton objects
In the IntSet
example, one could argue that there really only is a single empty IntSet
, and that it’s overkill to have the user create many instances of Empty
. Instead we can define a singleton object:
1
2
3
4
object Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
}
Singleton objects are values, so Empty
evaluates to itself.
Packages and imports
Classes and objects are organized in packages, just like in Java.
1
2
3
4
5
package funprog.example
object Rational {
...
}
One can now call the object using its full qualified name, or with an import:
1
2
3
4
5
6
7
8
9
10
11
12
object test {
new funprog.example.Rational(1, 2)
}
// or
import funprog.example.Rational // Import Rational
import funprog.example.{Rational, Hello} // Import both Rational and Hello
import funprog.example._ // Or import everything in funprog.example
object test2 {
new Rational(1, 2)
}
Polymorphism
Just like in Java, we may wish to have polymorphic types.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
// val head: T is a legal implementation of head
// and so is val tail: List[T]
// (they're in the argument list of Cons[T])
}
class Nil[T] extends List[T] {
def isEmpty = true
def head = throw new NoSuchElementException("Nil.head")
def tail = throw new NoSuchElementException("Nil.tail") // returns type Nothing
}
Type parameters can be used in classes, but also in functions.
Type inference
The Scala compiler can usually deduce the correct type parameters.
1
2
3
4
def singleton[T](elem: T) = new Cons[T](elem, new Nil[T])
singleton[Int](1) // Explicit type definition
singleton(1) // Type inference
Type bounds
We can set the types of parameters as either subtypes or supertypes of something. For instance, a method that takes an IntSet
and returns it if all elements are positive, or throws an error if not, could be implemented as such:
1
2
// Can either return an Empty or a NonEmpty, depending on what it's given:
def assertAllPos[S <: IntSet](r: S): S = ...
Here, <: IntSet
is an upper bound of the type parameter S
. Generally:
S <: T
meansS
is a subtype ofT
S >: T
meansS
is a supertype ofT
It’s also possible to mix a lower bound with an upper bound:
1
[S >: NonEmpty <: IntSet]
This would restrict S
to any type on the interval between NonEmpty
and IntSet
.
Variance
Given NonEmpty <: IntSet
, is List[NonEmpty] <: List[IntSet]
? Yes!
Types for which this relationship holds are called covariant because their subtyping relationship varies with the type parameter. This makes sense in situations fitting the Liskov Substitution Principle (loosely paraphrased):
If
A <: B
, then everything one can do with a value of typeB
one should also be able to do with a value of typeA
.
In Scala, for instance, Array
s are not covariant.
There are in fact 3 types of variance (given A <: B
):
C[A] <: C[B]
meansC
is covariantC[A] >: C[B]
meansC
is contravariant- Neither
C[A]
norC[B]
is a subtype of the other meansC
is nonvariant
Scala lets you declare the variance of a type by annotating the type parameter:
1
2
3
class C[+A] { ... } // C is covariant
class C[-A] { ... } // C is contravariant
class C[A] { ... } // C is invariant
Functions are contravariant in their argument types, and covariant in their result type. This allows us to state a very useful and important subtyping relation for functions: A1 => B2 <: A2 => B1
if and only if A1 >: A2
and B1 >: B2
.
Note that, in this case, A2 => B2
is unrelated to A1 => B1
.
The Scala compiler checks that there are no problematic combinations when compiling a class with variance annotations. Roughly:
- Covariant type parameters can only appear in method results
- However, covariant type parameters may appear in lower bounds of method type parameters
- Contravariant type parameters can only appear in method parameters
- However, contravariant type parameters may appear in upper bounds of method type parameters
- Invariant type parameters can appear anywhere
The following code, for instance, is correct as the covariant type parameter is a method result, and the contravariant is a parameter:
1
2
3
4
package scala
trait Function1[-T, +U] {
def apply(x: T): U
}
Object oriented decomposition
Instead of writing external methods that apply to different types of subclasses, we can write the functionality inside the respective classes.
1
2
3
4
5
6
7
8
9
trait Expr {
def eval: Int
}
class Number(n: Int) extends Expr {
def eval: Int = n
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval + e2.eval
}
But this is problematic if we need to add lots of methods but not add many classes, as we’ll need to define new methods in all the subclasses. Another limitation of OO decomposition is that some non-local operations cannot be encapsulated in the method of a single object.
In these cases, pattern matching may be a better solution.
Pattern matching
Pattern matching is a generalization of switch
from C or Java, to class hierarchies. It’s expressed in Scala using the keyword match
:
1
2
3
4
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
If none of the cases match, a match error exception is thrown.
Patterns are constructed from:
- Constructors, e.g.
Number
,Sum
- Variables, e.g.
n
,e1
,e2
- Wildcard patterns
_
(if we don’t care about the argument, we can useNumber(_)
) - Constants, e.g.
1
,true
(by convention, startconst
with a capital letter).
These patterns can be stacked, so we may try to match a Sum(Number(1), Var(x))
for instance. The same variable name can only appear once in a pattern, so Sum(x, x)
is not a legal pattern.
It’s possible to define the evaluation function as a method of the base trait:
1
2
3
4
5
6
trait Expr {
def eval: Int = this match {
case Number(n) => n
case Sum(e1, e2) => e1.eval + e2.eval
}
}
Pattern matching is especially useful when what we do is mainly to add methods (not really changing the class hierarchy). Otherwise, if we mainly create sub-classes, then object-oriented decomposition works best.
Case classes
A case class definition is similar to a normal class definition, except that it is preceded by the modifier case
. For example:
1
2
3
trait Epxr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
Doing this implicitly defines companion object with apply
methods.
1
2
3
4
5
6
object Number {
def apply(n: Int) = new Number(n)
}
object Sum {
def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}
This way we can just do Number(1)
instead of new Number(1)
.
Lists
There are two important differences between lists and arrays:
- Lists are immutable — the elements of a list cannot be changed.
- Lists are recursive (linked lists), while arrays are flat.
Like arrays, lists are homogeneous: the elements of a list must all have the same type.
List constructors
A bit of syntactic sugar: you can construct new lists using the construction operation ::
(pronounced cons).
1
2
3
fruit = "apples" :: "oranges" :: "pears" :: Nil
List("apples", "oranges", "pears") // Equivalent
Nil.::("pears").::("oranges").::("apples") // Also equivalent
As a convention, operators ending in :
associate to the right, and are calls on the right-hand operand.
List patterns
It is also possible to decompose lists with pattern matching. Examples:
1
2
3
4
5
6
7
8
9
10
Nil // Nil constant
p :: ps // A pattern that matches a list with a head matching p and a tail matching ps
List(p1, ..., pn) // Same as p1 :: ... :: pn :: Nil
1 :: 2 :: xs // Lists that start with 1 then 2
x :: Nil // Lists of length 1
List(x) // Same as x :: Nil
List() // Empty list, same as Nil
List(2 :: xs) // A list that contains as only element another list that starts with 2
x :: y :: List(xs, ys) :: zs // Lists of length >= 3 with a list of 2 elements in 3rd pos
We can do a really short insertion sort this way (but one that runs in O(n2))
1
2
3
4
5
6
7
8
9
def isort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case y :: ys => insert(y, isort(ys)) // y is head, ys is tail
}
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 :: insert(x, ys)
}
List methods
Sublists and element access
xs.length
: The number of elements ofxs
xs.last
: The list’s last elemeent, exception ifxs
is emptyxs.init
: A list consisting of all elements ofxs
except the last one, except ifxs
is empty.xs take n
: A list consisting of the firstn
elements ofxs
orxs
itself if it’s shorter thann
xs drop n
: The rest of the collection after takingn
elements.xs(n)
: The element ofxs
at indexn
Creating new lists
xs ++ ys
orxs ::: ys
: Concatenation ofxs
andys
xs.reverse
: The list containing the elements ofxs
in reversed orderxs updated (n, x)
: The list containing the same elements asxs
, except at indexn
where it containsx
.
Finding elements
xs indexOf x
: The index of the first elemen inxs
matchingx
, or-1
ifx
does not appear inxs
xs contains x
: same asxs indexOf x >= 0
Higher-order list functions
These are functions that work on lists and take another function as argument. The above examples often have similar structures, and we can identify patterns:
- transforming each element in a list in a certain way
- retrieving a list of all elements satisfying a criterion
- combining the elements of a list using an operator
Since Scala is a functional language, we can write generic function that implement these patterns using higher-order functions.
Map
The actual implementation of map
is a bit more complicated for performance reasons, but follows something allong the lines of:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
abstract class List[T] {
...
def map[U](f: T => U): List[U] = this match {
case Nil => this
case x :: xs => f(x) :: xs.map(f)
}
}
// Multiplies all elements of the list by a factor
def scaleList(xs: List[Double], factor: Double): List[Double] =
xs map (x => x * factor)
// Squares all elements of the list
def squareList(xs: List[Int]): List[Int] =
xs map (x => x * x)
Filter
1
2
3
4
5
6
7
8
9
10
11
abstract class List[T] {
...
def filter(p: T => Boolean): List[T] = this match {
case Nil => this
case x :: xs =>
if (p(x)) x :: xs.filter(p)
else xs.filter(p)
}
}
def positiveElems(xs: List[Int]): List[Int] = xs filter (x => x > 0)
There are a few other methods that extract sublists based on a predicate:
xs filterNot p
: Same asxs filter (x >= !p(x))
xs partition p
: Same as(xs filter p, xs filterNot p)
xs takeWhile p
: The longest prefix of listxs
consisting of elements that all satisfy the predicatep
xs dropWhile p
: The remainder of the listxs
after any leading elements satisfyingp
have been removedxs span p
: Same as(xs takeWhile p, xs dropWhile p)
Reduce
A reduction of a list consist of a combination of the elements using a given operator (i.e. summing or multiplying all the elements).
For certain operations, the order matters, and there are therefore different orders in which the reduction can be made.
One such function is foldLeft
. It goes from left to right and takes an accumulator z
as an additional parameter, which is returned when foldLeft
is called on an empty list. For instance
1
2
3
4
5
6
7
// The general notation is:
// (List(x1, ..., xn) foldLeft z)(op)
// Which returns:
// ((z op x1) op ...) op xn
def sum(xs: List[Int]) = (xs foldLeft 0)(_ + _)
def product(xs: List[Int]) = (xs foldLeft 1)(_ * _)
Note: The (_ + _)
notation is equivalent to ((x, y) => x + y)
.
foldLeft
and reduceLeft
(same as foldLeft
but without the z
argument) could be implemented as follows:
1
2
3
4
5
6
7
8
9
10
11
12
abstract class List[T] {
...
def reduceLeft(op: (T, T) => T): T = this match {
case Nil => throw new Error("Nil.reduceLeft")
case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[U](z: U)(op: (U, T) => U): U = this match {
case Nil => z
case x :: xs => (xs foldLeft op(z, x))(op)
}
}
foldRight
and reduceRight
follow similar implementations but put the parentheses to the right.
Implicit parameters
If we wanted to generalize an implementation of merge sort to work on more types than just Int
s, we could rewrite it as such:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (lt(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val (fst, snd) = xs splitAt n
merge(msort(fst)(lt), msort(snd)(lt))
}
}
val nums = List(2, -4, 5, 6, 1)
msort(nums)((x, y) => x < y)
// Generalisation:
val fruits = List("apple", "pineapple", "orange", "banana")
msort(fruits)((x, y) => x.compareTo(y) < 0) # lexicographical order
As a tiny note, it’s usually best to put the function value as the last parameter of a function, because that makes it more likely that the compiler can infer the types of the arguments of the function. E.g. we have written (x, y) => x < y)
instead of (x: Int, y: Int) => x < y
.
How can we make this code nicer? We can use the Ordering
type to represent the function, and make it an implicit parameter:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def msort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (ord.lt(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val (fst, snd) = xs splitAt n
merge(msort(fst), msort(snd)) // ord is visible at this scope
}
}
val nums = List(2, -4, 5, 6, 1)
msort(nums)
// Generalisation:
val fruits = List("apple", "pineapple", "orange", "banana")
msort(fruits)
Using the Ordering[T]
type means using the predefined default ordering, which we don’t even need to supply to msort
, namely Ordering.String
and Ordering.Int
. See notes on ordering in Java.
When you write an implicit parameter, and you don’t write an actual argument that matches that parameter, the compiler will figure out the right implicit to pass, based on the demanded type.
Rules for implicit parameters
Say that a function takes an implicit parameter of type T
. The compiler will search for an implicit definition that:
- is marked
implicit
- has a type compatible with
T
- is visible at the scope of the function call (see line 13 above), or is defined in a companion object associated with
T
If there’s a single (most specific) definition, it will be taken as actual argument for the implicit parameter. Otherwise, it’s an error.
For instance, at line 13, the compiler inserts the ord
parameter of msort
Proof techniques
Before we can prove anything, we’ll just assert that pure functional languages have a property called referential transparency, since they don’t have side effects. This means that we can use reduction steps as equalities to some part of a term.
Structural induction
The principle of structural induction is analogous to natural induction.
To prove a property P(xs)
for all lists xs
:
- Base case: Show that
P(Nil)
holds - Induction step: for a list
xs
and some elementx
, show that ifP(xs)
holds thenP(x :: xs)
also holds.
Instead of constructing numbers and adding 1, we construct lists from Nil
and add one element.
Example
Let’s show that, for lists xs
, ys
and zs
, (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
.
We’ll use the two following axioms of ++
to prove this:
Nil ++ ys = ys
(x :: xs1) ++ ys = x :: (xs1 ++ ys)
Let’s solve it. First, the base case:
1
2
3
4
5
// Left-hand side:
(Nil ++ ys) ++ zs = ys ++ zs // by the 1st clause of ++
// Right-hand side:
Nil ++ (ys ++ zs) = ys ++ zs // by the 1st clause of ++
Now, onto the induction step:
1
2
3
4
5
6
7
// Left-hand side:
((x :: xs) ++ ys) ++ zs = (x :: (xs ++ ys)) ++ zs // by 2nd clause of ++
= x :: ((xs ++ ys) ++ zs) // by 2nd clause of ++
= x :: (xs ++ (ys ++ zs)) // by induction hypothesis
// Right-hand side:
(x :: xs) ++ (ys ++ zs) = x :: (xs ++ (ys ++ zs)) // by 2nd clause of ++
So this property is established.
Other collections
All the collections we’ll study are immutable. The collection hierarchy is as follows:
Iterable
Seq
List
Vector
Range
Set
Map
Sequences
Vectors
A Vector
of up to 32 elements is just an array, but once it grows past that bound, its representation changes; it becomes a Vector
of 32 pointers to Vector
s (that follow the same rule once they outgrow 32).
Unlike lists, which are linear (access to the end of the list is slower than the start), random access to a certain element in a vector can be done in time log32(n).
Vectors are fairly good for bulk operations that traverse a sequence, such as a map, fold or filter. Also, 32 is a good number since it corresponds to a cache line.
Vectors are created analogously to lists:
1
2
3
4
5
6
val nums = Vector(1, 2, 3, -88)
val people = Vector("Bob", "James", "Peter")
// Instead of x :: xs we have:
x +: xs // create a new vector with leading element x, followed by xs
xs :+ x // create a new vector with trailing element x, preceded by xs
Creating new vectors with these :+
and +:
operators works by adding a vector, and recreating parent vectors with pointers to the existing ones. Doing this preserves immutability while still being fairly efficient (log32(n)).
Arrays and Strings
They come from Java, so they can’t be subclasses of Iterable
, but they still work just as if they were subclasses of Seq
, and we can apply all the same operations.
Range
Represents a sequence of evenly spaced integers.
1
2
3
4
val r: Range = 1 until 5 // 1, 2, 3, 4
val s: Range = 1 to 5 // 1, 2, 3, 4, 5
1 to 10 by 3 // 1, 4, 7, 10
6 to 1 by -2 // 6, 4, 2
Ranges are represented as three fields: lower bounds, upper bounds and step value.
Sets
Sets are another basic abstraction in the Scala collections. It is written analogously to a sequence:
1
2
3
4
5
6
7
val fruit = Set("apple", "banana", "pear")
val s = (1 to 6).toSet
// Most operations on sequences are also available on sets:
s map (_ + 2) // Set(3, 4, 5, 6, 7, 8)
fruit filter (_.startsWith == "app") // Set("apple")
s.nonEmpty // true
The principal differences between sets and sequences are:
- Sets are unordered: the elements of a set do not have a predefined order in which they appear in the set.
- Sets do not have duplicate elements.
- The fundamental operation on sets is
contains
.
Maps
Another fundamental collection type is the map
. A map of type Map[Key, Value]
is a data structure associating keys with values.
1
2
val romanNumerals = Map("I" -> 1, "V" -> 5, "X" -> 10)
val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern")
They’re both an Iterable
and a function, as Map[Key, Value]
also extends the function type Key => Value
.
1
2
3
4
5
capitalOfCountry("US") // "Washington"
capitalOfCountry("Andorra") // NoSuchElementException: key not found: Andorra
capitalOfCountry get "Andorra" // None
capitalOfCountry get "US" // Some("Washington")
Both the None
and the Some
are subclasses of the Option
type.
1
2
3
trait Option[+A]
case class Some[+A](value: A) extends Option[A]
object None extends Option[Nothing]
This means that we can do pattern matching, or use the withDefaultValue
:
1
2
3
4
5
6
7
8
9
10
def showCapital(country: String) = capitalOfCountry.get(country) match {
case Some(capital) => capital
case None => "missing data"
}
capitalOfCountry get "US" // "Washington"
capitalOfCountry get "Andorra" // "missing data"
val cap1 = capitalOfCountry withDefaultValue "Unknown"
cap1("Andorra") // "Unknown"
Operations on iterables
Operations on Sequences
xs exists p
:true
if there is an elementx
ofxs
such thatp(x)
holds,false
otherwise.xs forall p
:true
ifp(x)
holds for all elementsx
ofxs
,false
otherwisexs zip ys
: A sequence of pairs drawn from corresponding elements of sequencesxs
andys
xs.unzip
: Splits a sequences of pairsxs
into two sequences consisting of the first and second halves of all pairsxs.flatMap f
: Applies collection-valued functionf
to all elements ofxs
to all elements the results.xs.sum
: The sum of all elements of this numeric collectionxs.product
: The product of all elements of this numeric collectionxs.max
: The maximum of all elements of this numeric collection (anOrdering
must exist)xs.min
: The minimum of all elements of this numeric collection (anOrdering
must exist)
A few examples below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// List all combinations of numbers x and y
// where x is drawn from 1..M
// and y is drawn from 1..N
(1 to M) flatMap (x => (1 to N) map (y => (x, y)))
// > Vector((1, 1), (1, 2), ..., (2, 1), (2, 2), ...)
// Scalar product of two vectors
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(xs zip ys).map(xy = xy._1 * xy._2).sum
// Or using pattern matching function value
// Note: Generally, {case p1 => e1 ...} is
// equivalent to x => x match {case p => e1 ...}
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(xs zip ys).map{ case (x, y) => x * y}.sum
def isPrime(n: Int): Boolean =
(2 until n) forall (d => n % d != 0)
Sorted and groupBy
To sort elements, we can use either sortWith
or sorted
as below.
groupBy
is available on Scala collections. It partitions a collection into a map of collections according to a discriminator function f
.
1
2
3
4
5
6
7
val fruit = List("apple", "pear", "orange", "pineapple")
fruit sortWith (_.length < _.length) // List("pear", "apple", "orange", "pineapple")
fruit.sorted // List("apple", "orange", "pear", "pineapple")
fruit groupBy (_.head) // > Map(p -> List(pear, pineapple),
// | a -> List(apple),
// | o -> List(orange))
For-Expressions
Higher order functions and collections in functional languages often replace loops in imperative languages. Programs using many nested loops can therefore often be replaced by a combination of higher order functions.
For example, let’s say we want to find all 1 < i < j < n for which i + j is prime. This would take two loops in an imperative language, but in Scala we can “just” write:
1
2
(1 until n).flatMap(i => (1 until i) map (j => (i, j)))
.filter(pair => isPrime(pair._1 + pair._2))
This is hard to read, so we can use a for expression, of the form
1
for (s) yield e
Where s
is a sequence of generators and filters, and e
is an expression whose value is returned by an iteration.
Instead of ( s )
, braces { s }
can also be used, and then the sequence of generators and filters can be written on multiple lines without requiring semicolons.
Using a for expression, we can rewrite our previous example:
1
2
3
4
5
6
7
8
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)
// Scalar product
(for ((x, y) <- xs zip ys) yield x*y).sum
The rest of these notes correspond to the Functional Pogram Design in Scala course
Querying
Let’s say we want to query the number of authors who have written two or more books.
1
2
3
4
5
6
7
8
9
10
11
{ for {
b1 <- books
b2 <- books
if b1.title < b2.title // Prevent duplicates by using lexicographical order
// We could also use if b1 != b2, but this would
// match for the same pair of books twice.
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1
}.distinct // another way to prevent duplicates
The first mechanism to prevent duplicates is to compare titles using lexicographical order instead of a simple !=
. Another trick is to use .distinct
, which is like a .toSet
.
Translation to higher-order functions
The syntax of for is closely related to the higher-order functions map
, flatMap
, and filter
. These functions could be implemented as such:
1
2
3
4
5
6
7
8
def map[T, U](xs: List[T], f: T => U): List[U] =
for (x <- xs) yield f(x)
def flatMap[T, U](xs: List[T], f: T => Iterable[U]): List[U] =
for (x <- xs; y <- f(x)) yield y
def filter[T](xs: List[T], p: T => Boolean): List[T] =
for (x <- xs if p(x)) yield x
In reality, the translation is done the other way by the compiler. How do we translate for-expressions to these higher-order functions?
Below is the for expression and its translation at the next line.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// For-expression
for (x <- e1) yield e2
// Desugared
e1.map(x => e2)
// Let s be a (potentially empty) sequence of generators and filters
// For-expression
for (x <- e1 if f; s) yield e2
// Desugared
for (x <- e1.withFilter(x => f); s) yield e2
// For-expression
for (x <- e1; y <- e2; s) yield e3
// Desugared
e1.flatMap(x => for (y <- e2; s) yield e3)
// For-expression
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)
// Desugared
(1 until n) flatMap(i =>
(1 until i).withFilter(j => isPrime(i + j))
.map(j => (i, j)))
See more examples of desugared for-expressions in this gist.
Interestingly, the translation of for
is not limited to lists, sequences, or collections. Since it’s based solely on the presence of the methods map
, flatMap
and withFilter
, we can simply redefine these methods for our own types.
If, for instance, we were to write a database supporting these methods, then as long as these methods are defined, we can use the for
syntax for querying the database.
Functional Random Generators
Definition
We could also define these three methods (map
, flatMap
, withFilter
) for a random value generator. Let’s define it as such:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)
}
But we can streamline this:
1
2
3
4
5
6
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)
Which expands to:
1
2
3
4
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)))
We therefore need to define map
and flatMap
on the Generator
class.
1
2
3
4
5
6
7
8
9
10
11
12
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) // we use self instead of this to reference the trait and not the method
}
def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
def generate = f(self.generate).generate
}
}
Our example now expands to:
1
2
3
4
5
6
7
8
val booleans = for (x <- integers) yield x > 0
val booleans = integers map { x => x > 0}
val booleans = new Generator[Boolean] {
def generate = (x: Int => x > 0)(integers.generate)
}
val booleans = new Generator[Boolean] {
def generate = integers.generate > 0
}
We can also define other types of generators:
1
2
3
4
5
6
7
8
9
def single[T](x: T): Generator[T] = new Generator[T] {
def generate = x // identity
}
def choose(lo: Int, hi: Int): Generator[Int] =
for (x <- integers) yield lo + x % (hi - lo)
def oneOf[T](xs: T*): Generator[T] = // T* means you can give it as many arguments as you want
for (idx <- choose(0, xs.length)) yield xs(idx)
Usage
Having created a generator, we can use this as a building block for more complex expressions:
1
2
3
4
5
6
7
8
9
10
def lists: Generator[List[Int]] = for {
isEmpty <- booleans
list <- if (isEmpty) emptyLists else nonEmptyLists
} yield list
def emptyListst = single(Nil)
def nonEmptyLists = for {
head <- integers
tail <- lists
} yield head :: tail
Application: Random Testing
Generators are especially useful for random testing. Obviously it’s hard to predict the result of any random input without running the program, but what we can do is test postconditions, which are properties of the expected result.
1
2
3
4
5
6
7
def test[T](g: Generator[T], numTimes: Int = 100)(test T => Boolean): Unit = {
for (i <- 0 until numTimes) {
val value = g.generate
assert(test(value), "test failed for "+value)
}
println("Passed " + numTimes + " tests")
}
We can use a tool called ScalaCheck to do this in a more automated way. Instead of writing tests, with ScalaCheck we write properties that are assumed to hold. ScalaCheck will then try to find good counter-examples if the assertion fails.
1
2
3
forall { (l1: List[Int], l2: List[Int]) =>
l1.size + l2.size == (l1 ++ l2).size
}
Monads
Definition
A monad M
is a parametric type M[T]
with two operations, unit
and flatMap
(more commonly called bind
in the literature):
1
2
3
4
trait M[T] {
def flatMap[U](f: T => M[U]): M[U]
def unit[T](x: T): M[T]
}
The unit method return a monad with the given type:
List
is a monad withunit(x) = List(x)
Set
is a monad withunit(x) = Set(x)
Option
is a monad withunit(x) = Some(x)
Generator
is a monad withunit(x) = single(x)
For every monad, map
can be be defined as a combination of flatMap
and unit
. All of the following are equivalent.
1
2
3
m map f
m flatMap (x => unit(f(x)))
m flatMap (f andThen unit)
These methods have to satisfy some laws:
- Associativity: we can put the parentheses either to the left or the right, so
(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
Significance of the laws
Associativity says that one can “inline” nested for-expressions; the following are equivalent:
1
2
3
4
5
6
7
8
9
10
for {
y <- for(x <- m; y <- f(x)) yield y
z <- g(y)
} yield z
for {
x <- m
y <- f(x)
z <- g(y)
} yield z
Right unit says for (x <- m) yield x
is equivalent to just m
, and left unit isn’t very useful for for-expressions.
If monads are still mysterious, this is a good read.
Streams
Sometimes, for performance reasons, we want avoid computing the tail of a sequence until it is needed for the evalutation result (which might be never). Streams implement this idea while keeping the notation concise. They’re similar to lists, but their tail is evaluated only on demand.
Definition
Streams can be constructed like most other collections:
1
2
3
Stream.cons(1, Stream.cons(2, Stream.empty))
Stream(1, 2, 3)
(1 to 1000).toStream
.toStream
can be applied to any collection.
Streams can be described as partially constructed lists, and they support almost all of the List
methods. For instance, to find the second prime number between 1000 and 10000, we can do:
1
((1000 to 10000).toStream filter isPrime)(1)
The only exception is the cons operator, which is #::
instead of ::
. This can be used in operation but also in patterns.
Implementation
Again, this is pretty close to lists:
1
2
3
4
5
6
trait Stream[+A] extends Seq[A] {
def isEmpty: Boolean
def head: A
def tail: Stream[A]
...
}
All other methods can be defined in terms of these three. The actual implementation of streams is in the Stream
companion object, so if we want to define a new type of Stream
, we just need to redefine these three methods.
1
2
3
4
5
6
7
8
9
10
11
12
13
object Stream {
def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] { // Use CBN!
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")
}
}
Notice how the cons
method uses CBN. This is what makes the whole drastic difference between List
and Stream
!
The other stream methods are implemented analogously to their list counterparts:
1
2
3
4
5
6
7
class Stream[+T] {
...
def filter(p: T => Boolean): Stream[T] =
if (isEmpty) this
else if (p(head)) cons(head, tail.filter(p))
else tail.filter(p)
}
Lazy Evaluation
The proposed implementation suffers from a serious potential performance problem: if tail
is called several times, the corresponding stream will be recomputed each time. To avoid this, we can store the result of the first evalutation of tail
and re-use the stored result next time.
This is called lazy evaluation (as opposed to by-name evaluation where everything is recomputed, and strict evaluation for normal parameters and val
definitions). Scala uses strict evaluation by default, but allows lazy evaluation:
1
lazy val x = expr
x
is computed only once, when it is needed the first time; since functional programming expressions yield the same result on each call, the result is saved and reused next time.
This means that using a lazy value for tail
, Stream.cons
can be implemented more efficiently:
1
2
3
4
5
def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
def head = hd
lazy val tail = tl
...
}
Infinite Streams
Infinite streams benefit from laziness. All elements of a stream except the first one are computed only when needed. This opens up the possibility to define infinite streams.
1
2
3
def from(n: Int): Stream[Int] = n #:: from(n+1)
val nats = from(1) // stream of all natural numbers
nats map(_ * 4) // all natural multiples of 4
We also don’t need to worry too much about infinite recursions with infinite streams since the tail isn’t evaluated:
1
2
3
4
5
6
7
8
9
10
11
def 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))
Functions and State
So far we’ve seen that rewriting can be done anywhere in a term, and all rewritings which terminate lead to the same solution. For instance:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def iterate(n: Int, f: Int => Int, x: Int) =
if (n == 0) x
else iterate(n-1, f, f(x))
def square = x * x
iterate(1, square, 3)
// Can be rewritten as follows:
if (1 == 0) 3 else iterate(1-1, square, square(3))
iterate(0, square, square(3))
iterate(0, square, 3*3)
iterate(0, square, 9)
if (0 == 0) 9 else iterate(0-1, square, 9)
9
// But also:
if (1 == 0) 3 else iterate(1-1, square, square(3))
iterate(0, square, square(3))
if (0 == 0) square(3) else iterate(0-1, square, square(square(3)))
square(3)
9
There are multiple ways to rewrite our way to the solution; this is known as the Church-Rosser Theorem of lambda-calculus.
In this chapter, we’ll look at code that doesn’t satisfy that property. We will say goodbye to the substitution model for code that isn’t purely functional.
Stateful Objects
An object has a state if its behavior is influenced by its history. It is mutable (while everything so far has been immutable).
Mutable states are defined using the var
keyword (instead of val
), and assigned with =
:
1
2
3
4
var x: String = "abc"
var count = 111
x = "hi"
count = count + 1
If we define an object with stateful variables, then it is a stateful object if the result of calling a method depends on the history of the called methods, that the result may change over time.
Identity
Mutable state introduces questions about equality, identity between two objects.
With immutable values (val
), we had referential transparency; val x = E; val y = E
was equivalent to val x = E; val y = x
. This is no longer the case.
If BankAccount
is a stateful object (its balance may change), then val x = new BankAccount
and val y = new BankAccount
aren’t equal. This makes sense, because modifying x
doesn’t mean modifying y
, and we therefore have to different accounts.
In general, to determine equality, we must first specify what is meant by “being the same”. The precise meaning is defined by the property of operational equivalence: informally, x
and y
are operationally equivalent if no possible test can distinguish between them. For any arbitrary function f
, f(x, y)
and f(x, x)
must return the same value.
Loops
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// While:
while (i > 0) {
...
}
// Do-while:
do {
...
} while (i <= 25)
// For:
for (i <- 1 until 3) { // i takes values 1, 2 but not 3
...
}
For-loops look similar to for-expressions, but are translated to foreach
instead of map
and flatMap
:
1
2
3
for (i <- 1 until 3; j <- "abc") print(i + "" + j + " ")
// translates to:
(1 until 3) foreach (i => "abc" foreach (j => print(i + "" + j + " ")))
This should print “1a 1b 1c 2a 2b 2c”
Lisp
I don’t have a whole lot of notes on this, since most of Lisp was seen during lab sessions, and my notes on lambda-calculus are on paper (it wouldn’t have been easy typing it in real time). But for future reference, I’m adding a syntax list of the Lisp dialect seen in class:
(if c a b)
: special form which evaluatesc
, and thena
ifc != 0
andb
ifc = 0
.(cond (c1 r1) ... (cn rn) (else relse))
: special form which evaluatesc1
, thenr1
ifc1
is true, or else continues with the other clauses.(cons first rest)
: constructs a list equivalent to Scala’sx :: xs
. In our interpreter,xs
must be a list.(car lst)
: returns the head of a given list.(cdr lst)
: returns the tail of a given list(quote x)
: returns x as a quoted expression, i.e.(quote foo)
returns the quoted symbolfoo
, and(quote (a b c))
returns the list equivalent to(cons (quote a) (cons (quote b) (cons (quote c) nil)))
(= a b)
: returns whethera
andb
are equal. In our interpreter, a and b may be numbers, symbols or even lists.(lambda (p1 ... pn) body)
: creates an anonymous function.def f x
: creates a definition.def (f p1 ... pn) body
: syntactic sugar for defining a named function.