Functional Programming in Scala: Week 4
Contents
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:
|
|
Here is how it will work for an anonymous function:
|
|
There’s also an anonymous class syntax:
|
|
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 thatS
can be the type, the topmost type of which isIntSet
. This leaves us with the option of eitherEmpty
orNonEmpty
. - S >: T means S is the supertype of T.
[S >: NonEmpty]
would mean thatNonEmpty
defines the “lower bound” on the type parameter and thereforeS
can be any type aboveNonEmpty
in the type heirarchy. So siblings likeEmpty
would not be available, onlyNonEmpty
,IntSet
,AnyRef
, orAny
.
- 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
, andC[S] >: C[T]
. - Invariant: If
S <: T
, butC[S]
andC[T]
have no sub/super relationship. This is the default variance type for the user defined types.
Variances can be setup like this:
|
|
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:
|
|
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.
|
|
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.
|
|
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.
Author Tushar Tyagi
LastMod Aug 29, 2016