Remember the definition of `IntSet`

(in section Object Oriented Programming):

```
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
```

It seems too narrow to define only sets with `Int`

elements.

We'd need another class hierarchy for `Double`

lists, and so on,
one for each possible element type.

We can generalize the definition using a *type parameter*:

```
abstract class Set[A] {
def incl(a: A): Set[A]
def contains(a: A): Boolean
}
class Empty[A] extends Set[A] {
…
}
class NonEmpty[A](elem: A, left: Set[A], right: Set[A]) extends Set[A] {
…
}
```

Type parameters are written in square brackets, e.g. `[A]`

.

Like classes, functions can have type parameters.

For instance, here is a function that creates a set consisting of a single element.

`def singleton[A](elem: A) = new NonEmpty[A](elem, new Empty[A], new Empty[A])`

We can then write:

```
singleton[Int](1)
singleton[Boolean](true)
```

In fact, the Scala compiler can usually deduce the correct type parameters from the value arguments of a function call.

So, in most cases, type parameters can be left out. You could also write:

```
singleton(1)
singleton(true)
```

Type parameters do not affect evaluation in Scala.

We can assume that all type parameters and type arguments are removed before evaluating the program.

This is also called *type erasure*.

Languages that use type erasure include Java, Scala, Haskell, ML, OCaml.

Some other languages keep the type parameters around at run time, these include C++, C#, F#.

Polymorphism means that a function type comes "in many forms".

In programming it means that

- the function can be applied to arguments of many types, or
- the type can have instances of many types.

We have seen two principal forms of polymorphism:

- subtyping: instances of a subclass can be passed to a base class
- generics: instances of a function or class are created by type parameterization.

The remaining subsections compare their interaction.

Consider the following class hierarchy:

```
trait Animal {
def fitness: Int
}
trait Reptile extends Animal
trait Mammal extends Animal
trait Zebra extends Mammal {
def zebraCount: Int
}
trait Giraffe extends Mammal
```

Consider the method `selection`

that takes two animals as parameters
and returns the one with the highest `fitness`

value:

What would be the best type you can give to `selection`

? Maybe:

`def selection(a1: Animal, a2: Animal): Animal`

In most situations this is fine, but can one be more precise?

One might want to express that `selection`

takes `Zebra`

s to `Zebra`

s and `Reptile`

s to `Reptile`

s.

A way to express this is:

```
def selection[A <: Animal](a1: A, a2: A): A =
if (a1.fitness > a2.fitness) a1 else a2
```

Here, “`<: Animal`

” is an *upper bound* of the type parameter `A`

.

It means that `A`

can be instantiated only to types that conform to `Animal`

.

Generally, the notation

`A <: B`

means:, and`A`

is a subtype of`B`

`A >: B`

means:, or`A`

is a supertype of`B`

.`B`

is a subtype of`A`

You can also use a lower bound for a type variable.

`A >: Reptile`

The type parameter `A`

that can range only over *supertypes* of `Reptile`

.

So `A`

could be one of `Reptile`

, `Animal`

, `AnyRef`

, or `Any`

.

(We will see later on in this section where lower bounds are useful).

Finally, it is also possible to mix a lower bound with an upper bound.

For instance,

`A >: Zebra <: Animal`

would restrict `A`

any type on the interval between `Zebra`

and `Animal`

.

There's another interaction between subtyping and type parameters we need to consider.

Consider the following type modeling a field containing an animal:

```
trait Field[A] {
def get: A // returns the animal that lives in this field
}
```

Given

`Zebra <: Mammal`

is

`Field[Zebra] <: Field[Mammal]`

?

Intuitively, this makes sense: a field containing a zebra is a special case of a field containing an arbitrary mammal.

We call types for which this relationship holds *covariant*
because their subtyping relationship varies with the type parameter.

Does covariance make sense for all types, not just for `Field`

?

For perspective, let's look at arrays in Java (and C#).

Reminder:

- An array of
`T`

elements is written`T[]`

in Java. - In Scala we use parameterized type syntax
`Array[T]`

to refer to the same type.

Arrays in Java are covariant, so one would have:

`Zebra[] <: Mammal[]`

But covariant array typing causes problems.

To see why, consider the Java code below:

```
Zebra[] zebras = new Zebra[]{ new Zebra() } // Array containing 1 `Zebra`
Mammal[] mammals = zebras // Allowed because arrays are covariant in Java
mammals[0] = new Giraffe() // Allowed because a `Giraffe` is a subtype of `Mammal`
Zebra zebra = zebras[0] // Get the first `Zebra` … which is actually a `Giraffe`!
```

It looks like we assigned in the last line a `Giraffe`

to a
variable of type `Zebra`

!

What went wrong?

The following principle, stated by Barbara Liskov, tells us when a type can be a subtype of another.

If `A <: B`

, then everything one can to do with a value of type `B`

one should also
be able to do with a value of type `A`

.

The problematic array example would be written as follows in Scala:

```
val zebras: Array[Zebra] = Array(new Zebra)
val mammals: Array[Mammal] = zebras
mammals(0) = new Giraffe
val zebra: Zebra = zebras(0)
```

If you try to compile this example you will get a compile error at line 2:

```
type mismatch;
found: Array[Zebra]
required: Array[Mammal]
```

We have seen that some types should be covariant whereas others should not.

Roughly speaking, a type that accepts mutations of its elements should not be covariant.

But immutable types can be covariant, if some conditions on methods are met.

Say `C[T]`

is a parameterized type and `A`

, `B`

are types such that `A <: B`

.

In general, there are *three* possible relationships between `C[A]`

and `C[B]`

:

`C[A] <: C[B]`

,`C`

is*covariant*,`C[A] >: C[B]`

,`C`

is*contravariant*,- neither
`C[A]`

nor`C[B]`

is a subtype of the other,`C`

is*nonvariant*.

Scala lets you declare the variance of a type by annotating the type parameter:

`class C[+A] { … }`

,`C`

is*covariant*,`class C[-A] { … }`

,`C`

is*contravariant*,`class C[A] { … }`

,`C`

is*nonvariant*.

Generally, we have the following rule for subtyping between function types:

If `A2 <: A1`

and `B1 <: B2`

, then

`A1 => B1 <: A2 => B2`

So functions are *contravariant* in their argument type(s) and
*covariant* in their result type.

This leads to the following revised definition of the `Function1`

trait:

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

Consider the following type modeling a veterinary:

```
trait Vet[A] {
def treat(a: A): Unit // Treats an animal of type `A`
}
```

In such a case, intuitively, it makes sense to have `Vet[Mammal] <: Vet[Zebra]`

because
a vet that can treat any mammal is able to treat a zebra in particular. This is
an example of a contravariant type.

We have seen in the array example that the combination of covariance with certain operations is unsound.

In the case of `Array`

, the problematic combination is:

- the covariant type parameter
`T`

- which appears in parameter position of the method
`update`

.

The Scala compiler will check that there are no problematic combinations when compiling a class with variance annotations.

Roughly,

*covariant*type parameters can only appear in method results.*contravariant*type parameters can only appear in method parameters.*invariant*type parameters can appear anywhere.

The precise rules are a bit more involved, fortunately the Scala compiler performs them for us.

Let's have a look again at Function1:

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

Here,

`T`

is contravariant and appears only as a method parameter type`U`

is covariant and appears only as a method result type

So the method is checks out OK.

Sometimes, we have to put in a bit of work to make a class covariant.

Consider adding a `prepend`

method to `Stream`

which prepends a given
element, yielding a new stream.

A first implementation of `prepend`

could look like this:

```
trait Stream[+T] {
def prepend(elem: T): Stream[T] = Stream.cons(elem, this)
}
```

But that does not work!

Why does the above code not type-check?

`prepend`

fails variance checking.

Indeed, the compiler is right to throw out `Stream`

with `prepend`

,
because it violates the Liskov Substitution Principle:

Here's something one can do with a stream `mammals`

of type `Stream[Mammal]`

:

`mammals.prepend(new Giraffe)`

But the same operation on a list `zebras`

of type
`Stream[Zebra]`

would lead to a type error:

```
zebras.prepend(new Giraffe)
^ type mismatch
required: Zebra
found: Giraffe
```

So, `Stream[Zebra]`

cannot be a subtype of `Stream[Mammal]`

.

But `prepend`

is a natural method to have on immutable lists!

How can we make it variance-correct?

We can use a *lower bound*:

`def prepend[U >: T](elem: U): Stream[U] = Stream.cons(elem, this)`

This passes variance checks, because:

- covariant type parameters may appear in lower bounds of method type parameters
- contravariant type parameters may appear in upper bounds of method

Complete the following implementation of the `size`

function that returns
the size of a given list.

```
def size[A](xs: List[A]): Int =
xs match {
case Nil => res0
case y :: ys => res1 + size(ys)
}
size(Nil) shouldBe 0
size(List(1, 2)) shouldBe 2
size(List("a", "b", "c")) shouldBe 3
```