# 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:

```
// 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:

```
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*:

```
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`

.

- 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,
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:

```
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:

```
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.

```
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.

```
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.