Tip:
Highlight text to annotate it
X
The first three weeks courses have focused on functions, classes, data items, and a
model how they are evaluated. In this week, we are going to concentrate
more on types. That is the way the compiler sees these
classes and functions. In particular, we're going to learn about
fundamental ways to abstract and compose types.
The principal concept here is type parameterization.
Type parameterization means that classes as well as methods can now have types as
parameters. The running example for this week is a
data structure which is fundamental for many functional languages.
That's the immutable list that's built from individual consoles.
Over the last sessions we have seen quite a few different forms of types.
From simple types such as int or double, to class types such as rational and inset.
What we're going to see this week is more flexible ways to express and parameterize
types. This is called polymorphism.
So as a motivating example lets looks at the data structure that's been fundamental
in many functional languages from the beginnings of list, its called the cons
list. So cons list is an immutable link list
constructed from two building blocks. The empty list which we call mill and the cell
that contains first element of the list and a pointer reference to the rest of the
list, that is called cons. Let's look at some examples.
The list one, two, three could be drawn as follows.
You would have a first Cons cell that contains the one.
And a reference to the next Cons cell that contains the two.
And a reference to a Cons cell that contains the three.
And finally, this right field is nil. Here's a somewhat more complicated
example. A list containing two nested lists.
So that could be visualized as follows. We would have here, let's start with the
list that contains true. And false,
That would be the first element of the outer list.
Then there would be another list which is three and nil.
That will be the second element and then we would connect those two lists like
that. And,
We would finally, get a little here. So that would be, the list, list of true,
false, and the list of three here. So you see the general principle.
The question now is, how do we write that as a class heirarchy in Scala?
Okay, so here's an outline of a class heirarchy that would represent list of
integers in this fashion. We would start with a base trait, call it
IntList and two subclasses, Cons and Nil Cons subclass takes a head which is an
integer, the first element of the list, and a tail which is the remainder of the
list of Type intList and extends IntList The Nil class,
Representing the empty list, simply extends inclist.
And, we will have to fill in the dots here, to show what methods are in this
class hierarchy and how we would implement them.
Now, there is one piece of new syntax here, I have written directly val head int
and val tail inclist. What that does is, it defines at the same
time a parameter of the class and a field value definition in the class itself.
So the parameters that you see here are in fact equivalent to two fields, head and
tail, that I initialized by parameters that have some other name that's not
otherwise used in the program. So you can always express the val
parameters in, in this way but of course val parameters are much more concise so
they're preferred as a syntax form. But there's actually one other problem
with our type hierarchy, and that's that it's way too narrow to define on the list
with int elements. If we do it that way we'ld need another
class hierarchy for double lists, and one for list of booleans and so on.
One for each possible element type so lets clear an unscalable.
What we need to do is generalize the definition and we can do that using a type
parameter. So as an outline, what we're going to do
is, we're going to define now a base trait list, which takes a type parameter t.
So type parameters are written, in square brackets.
And that base trait list of T would have two subclasses, cons and middle.
Both of them are again parametrized. Also we call their type parameters T.
And in the case of cons we would now have a head element that is of type T, no
longer imp, but the parameter T. And a tail element that is of type list of
T. And cons of T itself extends list of T.
The middle class is analogous, so middle of T would simply extend list of T.
What we're going to do now is flesh out this hierarchy, adding the necessary
methods and the implementations. And we're going to do that using Eclipse
again. So what I'm going to do is create a Scala
trait, call it list. And the first thing I will do is add, the
type parameter, to, list, t. We could have any name, but, if this is
just a single type parameter at play, t is quite common.
So what methods should, we put into that trait?
Well, there seem to be three fundamental ones.
The first method is, we need to distinguish between whether the list is a
Cons cell the empty list. So let's call this method is empty.
Of type Boolean. So that tells us what kind of list we
have. Second method would be if we have a non
empty list, then we would be interested what is the first element of that list, so
that would be head as a method name, and what should it's type be?
Well, it would be element type of the list, so that would be T.
And finally, the last method would be tail, which gives us the remaining list
and its type would be list of T. Good, now that we have fleshed out the
base trait, let's go the implementations. First implementation would be the class
cons, which takes the type parameter t and head and tail as you've seen.
And it's an extension of list of T and what do we need to implement, well let's
start is MT. If a console is empty is always false
because consoles are never empty. What about the other two?
Definitions head and tail. Well actually, we have already implemented
them using the parameter names here. So the vowel had T.
T is actually a legal implementation for the method head t in the base class.
And the same holds for the tail value that we have here.
Oh, I just forgot, we have to put the tail value here in front because otherwise, it
wouldn't count as a field, and it wouldn't implement.
So what that shows is that in, Scala val definitions.
So field definitions in classes are really special cases of methods.
And they can override methods, and they can implement abstract methods and traits.
The difference between eval and the def concerns only the initialization.
Eval is evaluated when the object is first initialized.
Where, whereas a def is evaluated each time it is referenced.
So now we have cons. Let's look at the final one, Nil.
Nil of T also extends list of T and we have to implement the three methods.
What should this empty be? Well for Nil that would always be true.
What should head be? Well the problem with head is that we
cannot take the head of an empty list. So we should do is draw an exception, is
actually a handy exception in java code. No such element exception which we could
throw here and we can give it a message which says well you just hit nil.head.
So new no such element exception and finally tail.
Would be the same thing. We cannot also, cannot take the remainder
of an empty list. So, it would also throw a no such element
exception. What is the type of head and tails?
Well, you've learned that throw exception has type nothing and that then is also the
inferred type of head and tails so to be explicit, we could try that like this.
And then, we also see why that works, because head is, now is type nothing.
Nothing is a subtype of any other type, including T, so it's perfectly okay to
have a head definition here that returns nothing and that can implement a head,
abstract method in the trait list that returns a T, simply because a nothing is a
T, a nothing is a subtype of any other type.
Good. So, that was our implementation of lists,
which relied on the fact that we could parameter as classes with type parameters.
Type parameters are there not only for classes, but we can apply them also to
functions. So, functions can have type parameters.
For instance, here's a function that creates a list consisting of a single
element. So we would write def singleton and it
takes a element of the type of the list. And again that could be any type, so we
parametrize here singleton with a type parameter T.
And the body of the singleton is that simply creates a new Cons cell. it passes
on the type parameter T to say well, it needs to be a, a Cons cell of type T.
Its first element is elem and its tail is an empty list and it's an empty list of
element type T. The same T as the Cons cell. And if we do
that, we can then write singleton, and we can pass the type along.
So we want a singleton of type int now and the actual value should be one.
And that would give us, of course, the singleton list.
One and nil. Or the other one would be, that Singerton
lists ture and Nil. So we can create lists like that by passing in first the type
parameter and then the value parameter. In fact, the type parameters are often
redundant, because the Scala compiler can usually deduce the correct type parameter
from the value arguments of a function call here.
So, for instance, for the singleton, examples you could also write simply
singleton of one. And, the compiler would infer that this is
a singleton of type Int. Simply because, it knows that the constant one is of type
Int so Int is the best fitting parameter type.
And, the same way, it could infer that singleton of True has type parameter
boolean because, True is a value of type Boolean.
So that gives us a quite significant simplification of notation.
Where, then, the types really get out of the way.
They're not in your face anymore but they do in the background what needs to happen.
So when I drew data structures like this, Then in fact the actual type Int and
boolean doesn't form part of the data structure,
It's not stored anywhere. And that's a principle that affects all of
evaluation. So it turns out that type parameters do
not affect evaluation in Scala at all. So, to use our substitution model, we can
simply assume that all type parameters and type arguments are removed before
evaluating the program. Otherwise said, pipes are only important
for the compiler to verify that the program satisfies certain correctness
properties, but they're not relevant for the actual execution.
That's a property which is called type erasure so types erased at run-time.
And it's a property that some languages have and others don't.
So, if we look at the camp of languages that use type erasure, then we'll see Java
and also Scala. And functional languages such as Haskell,
ML or OCaml. But other languages actually keep the type
parameters around at run time. So for those languages, type parameters.
Would affect run time behavior, so those languages include c++ and languages in
the.NET family, such as C# or F#. So what we've seen here is a form of
polymorphism. Polymorphism is a Greek word and its
original meaning was having many forms. So applied to a function, it means that
the function can be applied to arguments of many different types.
Applied to a class or a type, it means that the type can have instances of many
different types. In fact, what we have seen are two
principle forms of polymorphism, namely sub typing and generics.
So sub-typing means that instances of a sub-class can be base, passed to a base
class. So, for instance, in the case of list.
I would have two subtypes. One was the class new, and the other was
the class cons. And wherever I would have a parameter that
accepts a list that could pass either a nil or a cons.
That which would be. Just as just as good as, as a channelist.
So that means that it is a form of polymorphism that it could have one of
those two forms. The other form of polymorphism we've seen
was generics where we can create many instances of a function or a class by type
parameterization. So using generics we could create a list
of int's or a list of doubles or a list of list of booleans.
The two forms of polymorphism complement each other well and Scala has both of
them. Typically you would say that subtyping was
traditionally a form that object-oriented languages had first whereas generics was a
form that functional languages had first. So let's do an exercise.
Given our definition of lists, write a function nth that takes an integer n and
the list and selects the nth element of the list.
So we assume that elements in the list are numbered from zero.
So the first element in the list has index zero, the second has index one, and so on.
The other specification is that if an index is outside the range from zero up to
the length of the list minus one, so it's outside range, then you should throw an
index out of bounds exception. So let's see how we would solve the
exercise. I have here our implementation of lists.
What I want to do is create a worksheet in which I could.
Implement this method. Call it Nth.
So I want to import in the worksheet what we have defined in the list class.
And I want to define a method. .
Call it nth that takes an index of type int.
And a list of type, list of. Well, we want to be flexible in the
element type. So that should be a type parameter of our
nth method. Have to return an element of type t.
So how do we implement that method? Well one good way to do it would be to ask
whether the. Index n equals zero and if it is then we
would have the answer immediately we could just return xs.head first element of x.
On the other hand if xn is not zero then what do we do.
Well the idea then is would be to say well to take say the third element end of a
list. That would be the same as taking the
second element of the remainder of the list.
So we would do an nth of n minus one as the index.
And x as [inaudible] as the list argument. Okay, so now we have to find M.
Let's test it. Let's do a list ,, .
So we have to find the list one two three And lets do n of two in the list.
What could we expect Well, It's three because we have arranged the elements in a
list, starting from zero. So, the one element will be at index zero,
two at index one, three at index two. So far so good, but, there was another
part of it, and that says well, what do we do if the index is not in the range of the
list. So, that would be something like that.
. And here we see a.
Java you till no such element exception nil.tail.
That's an exception alright, but it's not the one we wanted.
The exercise said we should return an index out of bound exception.
So what do we do here? Well, we have to change our definition of
Nth to guard against index out of bound exceptions.
So what we need to do is change the definition of Nth to take account of this
behavior with exceptions. So the idea here is to say well, if our
list is empty then we can essentially, not select any element no matter what the
index. So we have to catch this case beforehand.
So what I would do here is I would say, if X is empty then we throw a new index out
of bounds. The exception.
And now we see the, worksheet behaves as we want.
Nth minus one of list will throw an index out of bound exception, and I would hope
that nth and four of list would do the same thing.
Yes, it does. Index out of bound exception in both