Covariant and Contravariant in Scala

Scala often uses type parameter and also, you can see [+A] or [-A] in many library codes. I also wonder what it is. So, I study this and discuss with my co-worker. And leave this post to understand me. (But also, any comments are always welcome!)

Special Thanks for Karellen in Kakao.

What is Covariant, Contravariant and Invariant?

In Scala School Co, Contra, In -variant is described like this.

Variance is  about “if A <: B ( A is a subtype of B), how is the relation between M[A] and M[B]?”

if A <: B… then,

Meaning Scala notation
covariant M[A] <: M[B] [+B]
contravariant M[B] <: M[A] [-B]
invariant M[B] and M[A] are not related [B]

This means for example, in Java

As you can see above,

List<Object> objects = listStr

cannot be compiled.

Because in Java List<Object> is not considered as a parent of List<String>.

But, in Scala,

It can be compiled. Because in Scala, List[Any] is considered as a parent of  List[String]. In Scala source code, List is set as covariant.

Liskov Substitution Principle

It is very natural and simple. If A <: B, we can assign Typ A variable to Type B variable.


val a: A = new A

val b: B = a

also, List[+A] can be adapted, becase List is covariant.


val a: List[A] = List[A].empty

val b: List[B] = a

Variance in class

Guess, that I want to make my own List, and class like this.


class MyList[+A] {
    def insert(element: A): A = ??? // compile error
}

compile error message is


Error: covariant type A occurs in contravariant position in type A of value element
def insert(element: A): A = ???

Why does that happen? Simply thinking, I make a List of type A and subtype of A can be considered as a subtype of MyList[A]. Below topic explain of this.

Rethinking of + and –

In Scala, ‘+’ means Covariant and ‘-‘ means Contravariant. Let`s forget about it. And redefine ‘+’ as ‘Can receive subtype’ and ‘-‘ as ‘Can receive Supertype’. And then, above error can be described.

As defined in Liskov principle, In element, we can assign super type of A. But, +A is covariant. So, element can be only assigned subtype. So, this is contradiction.

So, if we correct the code like this, It can be compiled.


class MyList[+A] {
    def insert[B >: A](element: B): A = ???
}

By the way, how about return type as A. Is this ok? Of course yes. Let`s say that C <: A

And after long, long operation, the return type is decided as C. And as Liskov law, type C can be assigned to type A.(val c: C = A)

Variance in Function

In conclusion(as you can see above), Parameter is Contravariant(-A) and return type is Covariant. Also, in Scala, Function signature is


trait Function1[-T1, +R]

Yes, it`s simplified.

The subtype of Functions

In Scala course in coursera, there is a interesting problem. (It`s motivation of this post)

There are types like this.


NoneEmpty <: IntSet

type A = IntSet => NoneEmpty

type B = NoneEmpty => IntSet

What is the relationship between A and B?

  • A <: B
  • A >: B

The answer is A <: B. Why? As Liskov Principle, A can be assigned as B. It does not feel the impact to me. So, Let`s say that

if A <: B, A can pretend as B

Yes, String can pretend as Object. And above, NoneEmpty can pretend as IntSet.

Ok, then type A (IntSet => NoneEmpty) can pretend as type B(NoneEmpty => IntSet)? Of course!

If User passes NoneEmpty to A, It can be assigned to IntSet. And after an operation, A return NoneEmpty. And NoneEmpty can be assigned to IntSet.

subtypeFunction.png

A can pretend as B and A <: B

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s