Functional Programming in Scala: Week 4

Everything is an Object

This week has been pretty dense as compared to the other weeks and Prof. Odersky started with showing how unlike Java, Scala treats every type as objects. Therefore, as compared to Java, every type a built-in wrapper which transforms to Java type pseudo-objects during compile time. And since the method names can be almost anything, the operations are usually method names: a + b is actually a.+(b). This also means that the function values themselves are treated as objects.

Scala has FunctionX traits defined, which each function is an instance of. Here X is anything between 0 and 22 (inclusive) and stands for the number of input parameter the given function takes. The trait has an apply method defined, which contains the code for the given function value:

1
2
3
4
5


// For function which will take a value and return another value:
// f: A => B
trait Function1[A, B] {
  def apply(x: A): B
}

Here is how it will work for an anonymous function:

1
2
3
4
5
6
7
8


val f = (x: Int) => x * x

// gets expanded to
val f = { class SomeRandomClassName extends Function1[Int, Int] {
    def apply(x: Int) = x * x
  }
  new SomeRandomClassName
}

There’s also an anonymous class syntax:

1
2
3
4


val f = new Function1[Int, Int] {
    def apply(x: Int) = x * x
  }
f.apply(3) // 9

Methods defined using def are also converted into function values using the expansions above and applied.

Polymorphism:

Scala supports 2 types of polymorphism:

Subtyping
Generics

Subtyping:

Subtyping allows a child type to be used in place of the parent type; this essentially means that if IntSet type has two subtypes Empty and NonEmpty then we can pass both of the subtypes in places where the parent type is expected.

But we cannot blindly pass the subtypes; this is restriced by Liskov’s Substitution Principle which states that a subtype B can only be used in place of a parent type A if it can do everything the parent type can do. Essentially, this means that the child needs to have all the methods and properties defined which are being used in the code.

Generics:

In generics, we make the types of a given class/trait/etc. abstract so that it can take up more than one type, e.g. instead of IntList, FloatList, StringList, we will have a List[T] where T can be substituted for Int, Float, String, etc.

Generics also have its own boundaries which should not be crossed:

A diversions into bonds and variance:

Bounds:

Bonds define how two classes are connected to each other. In scala, this is defined by the following notation:
- S <: T means S is the subtype of T, and T defines an “upper bound” on the class. Therefore, in the class hierarchy, T is the highest type S can have. Therefore, [S <: IntSet] means that S can be the type, the topmost type of which is IntSet. This leaves us with the option of either Empty or NonEmpty.
- S >: T means S is the supertype of T. [S >: NonEmpty] would mean that NonEmpty defines the “lower bound” on the type parameter and therefore S can be any type above NonEmpty in the type heirarchy. So siblings like Empty would not be available, only NonEmpty, IntSet, AnyRef, or Any.
Variance:

Since NonEmpty <: IntSet, is List[NonEmpty] <: List[IntSet]? Turns out it is. This property means that the type List is covariant.

There are 2 more types of variances:

Contravariant: If S <: T, and C[S] >: C[T].
Invariant: If S <: T, but C[S] and C[T] have no sub/super relationship. This is the default variance type for the user defined types.

Variances can be setup like this:

1
2
3


class C[+T] { ... } // C is covariant
class D[-T] { ... } // D is contravariant
class E[T]  { ... } // E is invariant

In order to our types to compile correctly and not mess up later, we define the function of the types to be contravariant in their argument type, and covariant in their result type. Or take the safe option and let them invariant.

For instance, this is how the FunctionX traits are defined:

1
2
3


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

Pattern matching:

Scala provides case classes which allow pattern matching based on the class type. This turns to be much flexible and elegant than using a lot of if/else statements.

1
2


trait Expr
case class Number(n: Int) extends Expr

Creating a case class also takes care of the boilerplate by creating a companion object which contains a predefined apply method. Using this we can create the classes without using new operator. scala object Number { def apply(n: Int) = new Number(n) }

Case classes can be used in pattern matching by using the match expression. The match works by recursively matching the patterns.

1
2
3
4
5
6


expr match {
    case C(p1,...pn) => // Matches the constructors
    case Z => // Matches a constant, which always start with an Uppercase
    case v => // Matches a variable, and stores its value in `v`
    case _ => // Matches everything
}

Exercises:

Here we are supposed to create Huffman Coding for texts. The methods are excellent and forced a lot of thinking in the combine and mergeCodeTables method. In the latter I missed out on the point that List() is a valid List[Bit] and kept thinking about other things.

The exercises took around 6-7 hours of good thinking, but at the end I was able to knock out the questions. Although I turned lazy and did not change the recursive calls to tail recursive for many questions. This turned out to be a no-issue since the submission worked fine.

Contents