# Variance, a Scala language concept

Covariance, Invariance and Contravariance (will refer to as CIC) in Scala determine the relationship between generic types and subtyping. We noticed that people find it tricky to get their head around CIC, but in our view it is mostly an issue in the terminology used, such as "covariant positions".

We've thought long about this, and found that examples of `Cat` and `Dog` being sub-types of `Animal` is too concrete, and make CIC more difficult to understand. Often, describing a generic thing in general terms, is just more straightforward.

## The subtyping assumption

When `A2` is a subtype of `A` (syntax: `A2 <: A`), the assignments between `A` and `A2` we can try are:

✅ compiles ❌ does not make sense
Conversion Convert an `A2` to an `A` Convert an `A` to an `A2`
Example `def convert[A2 <: A](a2: A2): A = a2` `def convert[A2 <: A](a: A): A2 = a`
Why? `A2` is an `A` An `A` is not an `A2`, so we cannot convert an `A` to an `A2` as it may be an `A3` or some other subtype that does not conform to `A2`.

## Subtyping generic types

Upon understanding the material out there, we concluded that the function `I => O`, or `Function1[I, O]` type, where `Function1` is a generic type, is the best example for demonstrating subtyping. First, we use functions all the time; second, it is already predefined for us.

### Subtyping over the return type

We first focus on the case of a return type:

#### Converting `I => O2` to `I => O`

Example `def convert[I, O, O2 <: O](f: I => O2): I => O = f`
Outcome ✅ compiles
Why? The `O2` that is returned from `f` is also an `O`.

#### Converting `I => O` to `I => O2`

Example `def convert[I, O, O2 <: O](f: I => O): I => O2 = f`
Outcome ❌ does not make sense
Why? An `O` is not necessarily an `O2` when returning.

Therefore, if `O2 <: O`, then `(I => O2) <: (I => O)` . A function with a more specific return type is a subtype of a less specific return type.

### Subtyping over the input type

Let's try to do the above but on the input type:

#### Converting `I2 => O` to `I => O`

Example `def convert[I, I2 <: I, O](f: I2 => O2): I => O = f`
Outcome ❌ does not make sense
Why? `f` only accepts `I2`, and does not support `I` values.

#### Converting `I => O` to `I2 => O`

Example `def convert[I, I2 <: I, O](f: I => O): I2 => O = f`
Outcome ✅ compiles
Why? `f` accepts all `I2` values, as it accepts all `I` values.

Then, `I2 <: I` means that `(I => O) <: (I2 => O)`, which is the other way round compared to the relationship we had for the output type.

### What we learned

We ended up with 2 cases:

When inner subtype Then generic/outer subtype
`O2 <: O` `(I => O2) <: (I => O)`
`I2 <: I` `(I => O) <: (I2 => O)`

Before we jump onto the next step, make sure you have really understood the above. In case you haven't, write it out on a piece of paper, spend a good 15 minutes going back and forth.

### What we learned, in terminology

Now that we've built an intuition around this, let's name what we have just done:

• Covariance is for getting subtyping of the generic thing based on its output types;
• Contravariance is for getting subtyping of the generic thing based on its input types.

### Terminology applied to Function1

Function1 is defined as:
``````trait Function1[-T1, +R] {
def apply(v1: T1): R
}``````

The `-` and the `+` modifiers on the type parameters of `Function1` signifies a demand to make `Function1` possible to subtype based on its input (`-`) and output (`+`) type parameters; and that is is all that is meant by "contravariant position" and "covariant position" respectively.

Enabling subtyping brings the user additional powers, but what if we don't add these modifiers?

## The most basic generic type

By default in Scala, a generic type such as `trait X[A]` does not possess subtyping. Let's define a simple subtype relationship and a generic type:

``````trait Z
// Z2 <: Z
trait Z2 extends Z
trait X[A]``````

Now try to convert `X[Z2]` to `X[Z]`, and we get:

``````def convert(x2: X[Z2]): X[Z] = x2
/**
-- [E007] Type Mismatch Error: -------------------------------------------------
1 |def x: X[Z] = x2
|              ^^
|              Found:    X[Z2]
|              Required: X[Z]
|
*/``````

The compiler sees no way to see `X[Z2]` as `X[Z]`. This is what is meant by Invariance: there is no relationship between `X[Z2]` and `X[Z]`.

Change `trait X[A]` to `trait X[+A]`, and now this function compiles!

``def convert(x2: X[Z2]): X[Z] = x2``

Change it to `trait X[-A]`, and this compiles:

``def convert(x: X[Z]): X[Z2] = x``

## Finalising CIC

Lastly, we ought to understand the relationship between Covariance, Invariance and Contravariance. The way I think about it is that "Invariance is the intersection of Contravariance and Covariance". `Function1` is a great example to use because saying `A => A` we say `Function1[-A, +A]`, combining both contravariance and covariance.

Then we try to convert `A => A` to `A2 => A2`:

Example `def convert[A, A2 <: A](f: A => A): A2 => A2 = f`
Outcome ❌ does not make sense
Why? `f` can return `A` which is more than `A2` that is expected in the conversion.

When we try to convert `A2 => A2` to `A => A`:

Example `def convert[A, A2 <: A](f: A2 => A2): A => A = f`
Outcome ❌ does not make sense
Why? `f` only takes `A2` as inputs, yet we require a function that will take any `A`.

The only case where these examples work is if `A2 = A`, taking us back to the idea of invariance: regardless of a subtyping relationship of the inner types, there is no subtyping relationship of the generic type if it is invariant. To complete your understanding, try the following in a Scala console:

``````type X[A] = A => A
type X[-A] = A => A
type X[+A] = A => A``````

As next steps, read through the code of `List` and `Function1` to learn about context bounds.

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

## How our 100 algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.

### Study our 100 Scala Algorithms: 6 fully free, 100 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 22 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Subscribe to Scala Algorithms

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.