Functional Programming with Scala - Course notes

progfun1-week3.md

Week 3: Object-Oriented Sets

Note about union performance/complexity

(Taken from the discussion forums)

def union1(that: TweetSet): TweetSet = right.union(left.union(that)).incl(elem)
def union2(that: TweetSet): TweetSet = right.union(that).union(left).incl(elem)
def union3(that: TweetSet): TweetSet = right.union(left.union(that.incl(elem)))

Let's define the size of this and that as n. As usual with big-O notation, we assume approximately the same size here; we're only interested how the order of magnitude changes with increasing set sizes.

union1 recurses into right and left, each containing about n/2 elements. For each element we call incl, which effectively does an insert sort in a binary tree (this is O(log(n))). Combined, the complexity is O(n * log(n)).

union2 recurses into right and right.union(that), thus the complexity for the recursion is O(n/2) + O(n/2 * n) = O(n) + O(n^2) = O(n^2). As all implementations call incl, the combined complexity is O(n^2 * log(n)^2).

union3 recurses identically to union1, for complexity O(n * log(n)). However, we get some improvement due to tail recursion. This is due to mechanical sympathy (we use less stack space, causing less CPU cache invalidation) but does not reduce the big-O complexity.

progfun1-week4.md

Week 4

Variance

Notation:

• A <: B -- A is a subtype of B. That means that “everything that can be done with an object of type B can also be done with an object of type A” (Liskov substitution principle).
• A >: B -- A is a supertype of B (means that B <: A).

Function types:

If A2 <: A1 and B1 <: B2, then (A1 => B1) <: (A2 => B2).

Why is that?

• Functions of type A2 => B2 take a parameter of type A2; hence all parameters that can be fed into it can also be fed to a function of type A1 => B1, because A2 is a subtype of A1.
• Functions of type A1 => B1 return a value of type B1; because of the type relationships, all B1s are also B2s. So every A2 value passed to a function of type A1 => B1 is also a B2, making that function also of type A2 => B2.

Notation change:

• If Ac <: Ap and Bc <: Bp, then (Ap => Bc) <: (Ac => Bp)
• If mammal <: animal and banana <: food, then (animal => fruit) <: (mammal => food)

Conclusions:

• Every function that takes an A can also be said to take any subtype of A.
• Every function that returns a B can also be said to return any supertype of B.

Reasoning:

• In set notation, the phrase "every X is also a Y" means that all X's are contained in the set of all Y's. So, X < Y.

• In type notation, if every value of type X is also a value of type Y, then X is a subtype of Y. So, X <: Y.

• "animal-taking function" is a subtype of "mammal-taking function". This means that every animal-taking function can also be seen as a mammal-taking function.

• "fruit-returning function" is a special case of "food-returning function". Every fruit-returning function is also a food-returning function.

So (A => _) is a subtype of (T => _)[T <: A], and (_ => B) is a subtype of (_ => T)[B <: T].

Functions are covariant on their return types and contravariant on their parameter types.

In Scala, +T denotes a covariant type parameter, and -T denotes a contravariant type parameter. Just T denotes a nonvariant type parameter, that is, parameterized types with related type parameters are not related.

Function types

A function type is represented in Scala via a trait. A function which takes one argument maps to the Function1 trait:

trait Function1[-T, +U] {
    def apply(x: T): U
}

What if a method were a function? Well, to apply a method to a set of parameters, we would first have to resolve it as the apply method of a Function trait; then, to apply the apply method, we would need to translate it into the application of another apply method. This would not end.

So maybe a method is simply a “signature” of a function.

When to use (co|contra|non)variance

• Contravariant type parameters can only appear in method parameters.
• Covariant type parameters can only appear in method results.
• Nonvariant type parameters can appear anywhere.

By making our List class covariant (List[+T]), we may express Nil as a singleton object, instead of a generic class! We define Nil as an instance of List[Nothing], because Nothing <: T for any T, hence List[Nothing] <: List[T]. So Nil is an instance of any List[T] type.

That fits well into our previous definition of Nil#head and Nil#tail as having Nothing return type.

However, we cannot do something like this:

abstract class List[+T] {
    def prepend(elem: T): List[T] = new Cons(elem, this)
}

because that violates variance checking. Furthermore, this kind of method would violate the Liskov substitution principle. Suppose a Set type with two subtypes, object Empty and class NonEmpty; and a list xs of type List[Set]:

xs.prepend(Empty)

The same operation on a list ys of type List[NonEmpty] would lead to a type error:

ys.prepend(Empty)
           ^ type mismatch
           required: NonEmpty
           found: Empty

So, List[NonEmpty] cannot be a subtype of List[Set] when it contains such a prepend method.

Type bounds

To make the prepend method correct, we can use type bounds:

def prepend [U >: T] (elem: U): List[U] = new Cons(elem, this)

In this case we set T as a lower bound for type U.

• Covariant type parameters may appear in lower bounds of method type parameters
• Contravariant type parameters may appear in upper bounds of method type parameters

Decomposition

Decomposition: Access objects in an extensible class hierarchy.

Failed attempts:

• Classification and accessor methods: too much code
• Type tests and casts: unsafe and low-level
• Object-oriented decomposition:
  • Need to touch all classes to add a new operation
  • Does not always work. Example: simplifying arithmetical operations is a non-local operation and requires working with multiple objects.

Pattern matching

The sole purpose of test and accessor functions is to reverse the construction process:

• Which class was used?
• Which parameters were used in the constructor?

Case classes

trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

This also implicitly defines auxiliary objects:

object Number {
  def apply(n: Int) = new Number(n)
}

Number(1) // Now equivalent to `new Number(1)`

match

def eval(e: Expr): Int = e match {
  case Number(n) => n
  case Sum(e1, e2) => eval(e1) + eval(e2)
}

MatchError is thrown if no pattern matchces the value of the selector

Forms of patterns

• Constructors — e.g. Number(n), Number(_)
• Variables
• Wildcard patterns _
• Constants

Rules:

• The same variable name can only appear once in a pattern — Sum(x, x) is an illegal pattern
• Variable names begin with a lowercase letter
• Names of constants begin with a capital letter (except reserved keywords null true false)

Lists

Convention: Operators ending in : associate to the right. A :: B :: C is interpreted as A :: (B :: C). They are also seen as method calls of the right-hand operand. So these two are equivalent:

val nums = 1 :: 2 :: 3 :: 4 :: Nil
val nums = Nil.::(4).::(3).::(2).::(1)
// Also equivalent to:
val nums = List(1, 2, 3, 4)

So :: is a prepend operation.

Lists can be pattern-matched:

• Nil
• p :: ps
• x :: Nil
• List(p1, p2, p3)

Syntax tips

On constants and variables

You can't pattern-match against a variable in the following way:

def startsWith(list: List[Int], n: Int): Boolean = list match {
  case n :: ns => true
  case _ => false
}

startsWith(List(1, 2, 3), 1) // true
startsWith(List(1, 2, 3), 4) // true (???)

This is because n is interpreted as a match variable that shadows the parameter n; it is equivalent to any other variable name (e.g. the first case is equivalent to x :: xs). So every non-empty list will be matched. Actually, all names that begin with a lowercase letter are interpreted as match variables (as noted above). You could add an uppercase-beginning constant and match against it (or change the parameter name); but I think this would pollute the code.

The best solution, I think, is wrapping the variable name with backticks ` `. In Scala jargon, this will make it a stable identifier pattern; that is, it will actually match against the value of the variable n:

def startsWith(list: List[Int], n: Int): Boolean = list match {
  case `n` :: ns => true
  case _ => false
}

startsWith(List(1, 2, 3), 1) // true
startsWith(List(1, 2, 3), 4) // false

Capturing decomposed expressions

Suppose you pattern matched against an expression that decomposed a value, and you want to use the value as a whole in the pattern block:

def foo(list: List[(Char, Int)]): (Char, Int) = list match {
  case (c, 1) :: xs => (c, 1)
  case _ => ???
}

Here we have repeated the (c, 1) expression in the pattern-block. We can capture it with the @ operator, avoiding a repetition:

def foo(list: List[(Char, Int)]): (Char, Int) = list match {
  case (pair @ (c, 1)) :: xs => pair
  case _ => ???
}

In this case it is a little more typing, but our intention becomes more explicit and we avoid typing mistakes when copying the LHS expression.

progfun1-week5.md

Week 5

Operations on lists

Concatenation

def concat[T](xs: List[T], ys: List[T]) = xs match {
  case Nil => ys
  case z :: zs => z :: concat(zs, ys)
}

Complexity is proportional to |xs| (length of xs).

Pairs and tuples

val pair = ("answer", 42)   //> pair : (String, Int)

Pairs can be used as patterns — both in assignments and in match constructs:

val (label, value) = pair   //> label : String = "answer"
                            //| value : Int = 42

:

def merge(xs: List[T], ys: List[T]): List[T] =
  (xs, ys) match {
    ???
  }

Formally…

• Tuple types: (T1, …, TN) stands for scala.TupleN[T1, …, TN]
• Tuple constructors: (e1, …, eN) stands for scala.TupleN(e1, …, eN)

Implicit parameters

Tip: when a method has several parameter lists and one of them is a function value, it is usually advantageous to put the function value last, because then we have a better chance that the types will have been inferred due to the previous parameters.

Ordering

import scala.math.Ordering

def msort[T](xs: List[T])(ord: Ordering[T]) =

  def merge(xs: List[T], ys: List[T]): List[T] =
    ... if (ord.lt(x, y)) ...

  ... merge(msort(fst)(ord), msort(snd)(ord)) ...

...

msort(someIntList)(Ordering.Int)
msort(someStringList)(Ordering.String)

If we make ord an implicit parameter, we can leave it out in our calls. The compiler will figure it out, looking for a definition that

• is marked implicit
• has a type compatible with T
• either
  • is visible at the point of the call (this is the case in the calls to msort in the inner merge function); or
  • is defined in a companion object associated with T (this is the case of Ordering.Int and Ordering.String)

There must be one and only one matching definition. Otherwise it’s an error.

Higher-order operations on lists

map

A simplified implementation of map could be like this:

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)
  }

The actual implementation is a little more complicated, because it is tail-recursive and also works for arbitrary collections, not just lists.

(My tail-recursive try:

  def map[U](f: T => U): List[U] = {
    def mapAcc(xs: List[T], ys: List[U]): List[U] = xs match {
      case Nil => ys
      case z :: zs => mapAcc(zs, f(z) :: ys)
    }
    mapAcc(this, Nil)
  }

)

filter

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)
  }

filter also has some friends:

• filterNot
• partition (computes filter and filterNot in one go, returning a pair of Lists)
• takeWhile, dropWhile
• span (like partition for takeWhile and dropWhile

progfun2-week1.md

Week 1: for expressions and monads

for expressions

Translation rules

1. Single generator

    for (x <- e1) yield e2
     ↓ 
    e1.map (x => e2)
   

2. Multiple generators: reduction step

    for (x <- e1; y <- e2; s) yield e3
     ↓ 
    e1.flatMap(x => for (y <- e2; s) yield e3)
   

3. Filtering

    for (x <- e1 if f; s) yield e2
     ↓ 
    for (x <- e1.withFilter(x => f); s) yield e2
   

Monads

Definition

Two basic operations, flatMap and unit:

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

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

satisfying the laws:

1. Associativity

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

2. Left unit

   unit(x) flatMap f == f(x)
   

3. Right unit

   m flatMap unit == m
   

map

map can be defined as a composition of unit and flatMap:

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

We can also expand the for single-generator expression as follows:

for (x <- m) yield e1
m.map (x => e1)
m.flatMap (x => unit(e1))

Monad laws and for expressions

Right unit

m
// by right unit law
  == m flatMap unit
// `id` is the identity function
  == m flatMap (id andThen unit)
// by definition of `map`
  == m map id
// by definition of `for` with a single generator
  == for (x <- m) yield id(x)
// because `id(x) == x`
  == for (x <- m) yield x

or, more simply,

m
// by right unit law
  == m flatMap unit
  == m flatMap (x => unit(x))
// by our expansion of `for` with `map` defined from `flatMap`
  == for (x <- m) yield x

Associativity

LHS:

for (y <- for (x <- m; y <- f(x)) yield y
     z <- g(y)) yield z

for (y <- (m.flatMap (x => for (y <- f(x)) yield y))
     z <- g(y)) yield z

for (y <- (m.flatMap (x => f(x).map(y => y)))
     z <- g(y)) yield z

for (y <- (m.flatMap (x => f(x)))
     z <- g(y)) yield z

for (y <- (m flatMap f)
     z <- g(y)) yield z

(m flatMap f).flatMap(y => for (z <- g(y)) yield z)

(m flatMap f) flatMap g

RHS:

for (x <- m; y <- f(x); z <- g(y)) yield z

m flatMap (x => for (y <- f(x); z <- g(y)) yield z)

m flatMap (x => f(x).flatMap(y => for (z <- g(y)) yield z))

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

Try: not a monad!

Try(expr)
// => Success(value)
// => Failure(exception)

It breaks the left unit law:

Try(x) flatMap f != f(x)

LHS encapsulates non-fatal exceptions that might be thrown by expression x or by call f(x), whilst RHS throws them