101.04 - Types and pattern matching

Types and Pattern matching

Pure OO Language - every value is an object. The type of each value is a class (assuming the language is based on classes).

Boolean simulation

abstract class Boolean {
  def ifThenElse[T](t: => T, e: => T): T

  def && (x: => Boolean): Boolean = ifThenElse(x, false)
  def || (x: => Boolean): Boolean = ifThenElse(true, x)
  def unary_!: Boolean = ifThenElse(false, true)

  def == (x: Boolean): Boolean = ifThenElse(x, x.unary_!)
  def == (x: Boolean): Boolean = ifThenElse(x.unary_!, x)
}

Int simulation

// partial implementation
class Int {
  def + (that: Double): Double
  def + (that: Float): Float
  def + (that: Long): Long
  def + (that: Int): Int

  def & (that: Long): Long
  def & (that: Int): Int
}

Natural number simulation

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat = new Succ(this)
  def + (that: Nat): Nat
  def - (that:Nat): Nat

object Zero extends Nat {
  def isZero = true
  def predecessor = throw new Error("0.predecessor")
  def + (that: Nat) = that
  def - (that:Nat) = if (that.isZero) this else throw new Error("negative number")
}

object Succ(n: Nat) extends Nat {
  def isZero = false
  def predecessor = n
  def + (that: Nat) = new Succ (n + that) 
  def - (that:Nat) = if (that.isZero) return this else n - that.predecessor
}

Functions as objects

The function type:

A => B

is an abbreviation for:

package scala
trait Function1[A, B] {
  def apply(x: A): B
}

There are traits Function2, Function3, ... , Function22 for functions with 2 .. 22 parameters

A function such as:

(x: Int) => x * x

expands to:

{ 
    class AnonFun extends Function1[Int, Int] {
      def apply(x: Int) = x * x
    }
    new AnonFun
}

or shorter:

{ 
    new Function1[Int, Int] {
      def apply(x: Int) = x * x
    }
}

The method:

def f(x: Int): Boolean = ...

is not itself a function value, but if used in a place where a Function type is expected, it will be converted to a function value. This is called an eta-expansion:

(x:Int) => f(x)

List simulation

object List {
  def apply[T]() = new Nil
  def apply[T](x1: T): List[T] = new Cons(x1, new Nil)
  def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, new Nil))
}

List()
List(1)
List(2,3)

Subtypes and generics

There are two forms of polymorphism:

• Subtyping
• Generics

Type bounds

Consider a method assertAllPos which:

• takes an IntSet as parameter;
• returns the IntSet if all members are positive;
• throws an exception otherwise;

We can define the method signature as follows:

def assertAllPos(s: IntSet): IntSet

We can also define as follows:

assertAllPos(Empty) = Empty
assertAllPos(NonEmpty(...)) = either NonEmpty(...) or throws an exception

Notice that if the initial set is Empty, the method cannot return NonEmpty and vice-versa. We can then define the method signature more precisely as follows:

def assertAllPos[S <: IntSet](r: S): S

This:

<: IntSet 

is an upper bound of the type parameter S, which means any subclass of type IntSet.

S <: T 

means S is a subtype of T, while:

S >: T 

means S is a supertype of T (or T is a subtype of S).

One can use lower bounds too, such as:

S >: IntSet

meaning S is a supertype of IntSet, meaning it can be IntSet, NonRef, AnyRef or Any. Sometimes both the upper bounds and the lower bounds can be specified, such as:

S >: NonEmpty <: IntSet

S is any type in the interval between NonEmpty and IntSet.

Covariance

Assuming:

Ford <: Car

should the following be true?

List[Ford] <: List[Car]

Intuitively, it makes sense. A list of Fords is a specialised case of a List of Cars.

This kind of generic types is called covariant. Their subtyping relationship varies with the type parameter.

• Java arrays are covariant;
• Scala arrays are NOT covariant

The co-variance brings forward the following issue in Java:

Ford [] fords = new Ford[] {new Ford("Focus")};
Car [] cars = fords;
car[0] = new Honda("Civic");   // ArrayStoreException thrown here at runtime
Ford f = a[0];

Java tags the array at creation with the type of objects that it can contain and will throw an ArrayStoreException at runtime, when trying to store an "incompatible" type into the array. This is a hole in the Java type system that exists for historical reasons. Originally, the language designers wanted to be able to write a method like:

sort(Object [] arr);

to sort any kind of array. That required co-variance.

The Liskov Substitution Principle

Let q(x) be a property provable about objects x of type B. Then q(y) should be provable for objects y of type A where A <: B

In plain words:

If Ford <: Car then everything one can do with a Car instance, one should be able to do with a Ford instance.

Variance

List should be co-variant while Array should be not. Why? Because List is immutable while Array is mutable.

Say: C[T] is a parameterized type and A, B are types, such as: A <: B. There are three possible relationships between C[A] and C[B]:

• C is covariant: C[A] <: C[B]

• C is contravariant: C[A] >: C[B]

• C is nonvariant: C[A] and C[B] are unrelated types (no subtypes)

  In Scala, you can "program" the variance:

class C[+A] { ... }     // covariant
class C[-A] { ... }     // contravariant
class C[A] { ... }      // nonvariant

Example:

type A = Car => Ford
type B = Ford => Car

The variance of the above function is:

A <: B

What can you do with type B? You can pass a Ford parameter to it and you will receive a Car in return. You can do the same with type A, You can pass a Ford parameter to it (which is a Car) and it will return a Ford (which is a Car). So type A satisfies the same contract as type B.

This can be generalised as follows:

If:

• A2 <: A1 and B1 <: B2

then:

• A1 => B1 <: A2 => B2

(note that the inheritance direction of the arguments and return types is opposite). Functions are contra-variant in their argument type and co-variant in their return type.

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

The Scala compiler performs variance checks:

• contra-variant types are only allowed as function parameters;
• co-variant parameters are only allowed as function results;
• non-variant parameters are allowed anywhere;

Decomposition

• Classification and access methods: quadratic explosion;
• Type tests: unsafe and low-level;
• OO decomposition: doesn't always work, have to touch all classes to add a new method;
• Pattern matching

Pattern Matching

Case classes are similar to normal classes, except that they are preceded by the modifier: case:

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

For case classes , the Scala compiler generates automatically companion objects with factory methods:

object Number {
  def apply(n: Int) = new Number(n)
}
object Sum {
  def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}

val x = Number(1)

Note: the last line, there's no new keyword when instantiating the object. We can then use pattern matching:

e match {
  case pattern1 => expression
  case pattern2 => expression
}

For instance:

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

Patterns are constructed from:

• constructors: Number, Sum, etc
• variables: n, e1, e2
• wildcards: _
• constants: 1, true, "abc"

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

Lists

• Lists are immutable and recursive
• Arrays are mutable and flat (non-recursive)

val fruit = List("apples", "oranges", "bananas")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()

Type is inferred here, but you could also write:

val fruit: List[String] = List("apples", "oranges", "bananas")
val empty: List[Nothing]: List()

You can also use the cons operator :: to construct lists:

fruit = "apples" :: ("oranges" :: ("bananas" :: Nil))
nums = 1 :: (2 :: (3 :: (4 :: Nil)))
empty = Nil

Note: in Scala all operators that end in : associate to the right by convention, so we don't even need the parenthesis:

fruit = "apples" :: "oranges" :: "bananas" :: Nil

Operators ending in : are also seen as method calls of the right-hand operand, so we could write as well:

Nil.::(4).::(3).::(2).::(1)

From that perspective, :: is really a prepend operation.

All List operations can be expressed in terms of the following operations:

• head
• tail
• isEmpty

Lists can also be decomposed with pattern matching:

Nil - The Nil constant p :: ps - A pattern that matches a list with head p and a tail matching ps List(p1, ..., pn) - Same as p1 :: ... :: pn :: Nil

For example:

1 :: 2 :: xs - A List that starts with 1 and 2 x :: Nil - List length is 1 List(x) - Same as above List() - Same as Nil, empty list List(2 :: xs) - A List of Lists, the first of which starts with 2

Sorting a List

Lists have methods for sorting, but assuming there is no such method, here is how a List could be sorted:

Given a List 7 :: 3 :: 9 :: 2 we could:

• sort the tail 3 :: 9 :: 2 to: 2 :: 3 :: 9
• insert the head 7 into the right position: 2 :: 3 :: 7 :: 9

This sorting algorithm is called Insertion Sort.

def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case y :: ys => insert(y, isort(ys)) 
}

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