Jay Taylor's notes

back to listing index

generics - Scala covariance / contravariance question - Stack Overflow

[web search]
Original source (stackoverflow.com)
Tags: scala programming type-theory covariance contravariance variance stackoverflow.com
Clipped on: 2012-08-20

Following on from this question, can someone explain the following in Scala:

class Slot[+T] (var some: T) { 
//  "COVARIANT parameter in CONTRAVARIANT position"


I understand the distinction between T+ and T in the type declaration (it compiles if I use T). But then how does one actually write a class which is covariant in its type parameter without resorting to creating the thing unparametrized? How can I ensure that the following can only be created with an instance of T?

class Slot[+T] (var some: Object){    
def get() = { some.asInstanceOf[T] }

EDIT - now got this down to the following:

abstract class _Slot[+T, V <: T] (var some: V) {
def getT() = { some }

this is all good, but I now have two type parameters, where I only want one. I'll re-ask the question thus:

How can I write an immutable Slot class which is covariant in its type?

EDIT 2: Duh! I used var and not val. The following is what I wanted:

class Slot[+T] (val some: T) { 
asked Mar 19 '09 at 17:46
Image (Asset 1/4) alt=49k11123284

93% accept rate
would you mind explaining why val works while var doesn't? – IttayD Oct 30 '09 at 6:34
2 upvote
Because var is settable whilst val is not. It's the same reason why scala's immutable collections are covariant but the mutable ones are not. – oxbow_lakes Oct 30 '09 at 8:21
add comment

3 Answers

up vote 85 down vote accepted

Generically, a covariant type parameter is one which is allowed to vary down as the class is subtyped (alternatively, vary with subtyping, hence the "co-" prefix). More concretely:

trait List[+A]

List[Int] is a subtype of List[AnyVal] because Int is a subtype of AnyVal. This means that you may provide an instance of List[Int] when a value of type List[AnyVal] is expected. This is really a very intuitive way for generics to work, but it turns out that it is unsound (breaks the type system) when used in the presence of mutable data. This is why generics are invariant in Java. Brief example of unsoundness using Java arrays (which are erroneously covariant):

Object[] arr = new int[1];
[0] = "Hello, there!";

We just assigned a value of type String to an array of type int[]. For reasons which should be obvious, this is bad news. Java's type system actually allows this at compile time. The JVM will "helpfully" throw an ArrayStoreException at runtime. Scala's type system prevents this problem because the type parameter on the Array class is invariant (declaration is [A] rather than [+A]).

Note that there is another type of variance known as contravariance. This is very important as it explains why covariance can cause some issues. Contravariance is literally the opposite of covariance: parameters vary upward with subtyping. It is a lot less common partially because it is so counter-intuitive, though it does have one very important application: functions.

trait Function1[-P, +R] {
def apply(p: P): R

Notice the "-" variance annotation on the P type parameter. This declaration as a whole means that Function1 is contravariant in P and covariant in R. Thus, we can derive the following axioms:

T1' <: T1
<: T2'
---------------------------------------- S-Fun
Function1[T1, T2] <: Function1[T1', T2']

Notice that T1' must be a subtype (or the same type) of T1, whereas it is the opposite for T2 and T2'. In English, this can be read as the following:


A function A is a subtype of another function B if the parameter type of A is a supertype of the parameter type of B while the return type of A is a subtype of the return type of B.


The reason for this rule is left as an exercise to the reader (hint: think about different cases as functions are subtyped, like my array example from above).

With your new-found knowledge of co- and contravariance, you should be able to see why the following example will not compile:

trait List[+A] {
def cons(hd: A): List[A]

The problem is that A is covariant, while the cons function expects its type parameter to be contravariant. Thus, A is varying the wrong direction. Interestingly enough, we could solve this problem by making List contravariant in A, but then the return type List[A] would be invalid as the cons function expects its return type to be covariant.

Our only two options here are to a) make A invariant, losing the nice, intuitive sub-typing properties of covariance, or b) add a local type parameter to the cons method which defines A as a lower bound:

def cons[B >: A](v: B): List[B]

This is now valid. You can imagine that A is varying downward, but B is able to vary upward with respect to A since A is its lower-bound. With this method declaration, we can have A be covariant and everything works out.

Notice that this trick only works if we return an instance of List which is specialized on the less-specific type B. If you try to make List mutable, things break down since you end up trying to assign values of type B to a variable of type A, which is disallowed by the compiler. Whenever you have mutability, you need to have a mutator of some sort, which requires a method parameter of a certain type, which (together with the accessor) implies invariance. Covariance works with immutable data since the only possible operation is an accessor, which may be given a covariant return type.

answered Mar 23 '09 at 16:27
Image (Asset 2/4) alt=21.7k15684
I don't know anything about Scala, but I had been trying to understand covariance and contravariance. This made perfect sense! – Matthew Willis Mar 11 '11 at 23:57
Great summary ! – fotNelton Mar 22 '11 at 5:57
The last paragraph about why List[+T] can still have methods taking arguments of T is exactly what I was looking for. – Martin Konicek May 12 '11 at 18:28
Very helpful post, thanks! – jlezard Sep 10 '11 at 13:06
Excellent post, re-reading it (multiple times) to understand it properly! – Alex Dean Oct 6 '11 at 19:25
add comment

See Scala by example, page 57+ for a full discussion of this.

If I'm understanding your comment correctly, you need to reread the passage starting at the bottom of page 56 (basically, what I think you are asking for isn't type-safe without run time checks, which scala doesn't do, so you're out of luck). Translating their example to use your construct:

val x = new Slot[String]("test") // Make a slot
val y: Slot[Any] = x             // Ok, 'cause String is a subtype of Any
.set(new Rational(1, 2))        // Works, but now x.get() will blow up

If you feel I'm not understanding your question (a distinct possibility), try adding more explanation / context to the problem description and I'll try again.

In response to your edit: Immutable slots are a whole different situation...* smile * I hope the example above helped.

answered Mar 19 '09 at 18:00
Image (Asset 3/4) alt=12.6k2150
I have read that; unfortunately I (still) don't understand how I can do what I ask above (i.e. actually write a parametrized class covariant in T) – oxbow_lakes Mar 19 '09 at 18:13
I removed my downmark as I realized this was a bit harsh. I should have made clear in the question(s) that I had read the bits from Scala by example; I just wanted it explained in a "less-formal" manner – oxbow_lakes Mar 19 '09 at 18:24
@oxbow_lakes smile I fear Scala By Example is the less formal explanation. At best, we can try to use concrete examples to work though it here... – MarkusQ Mar 19 '09 at 18:44
Sorry - I don't want my slot to be mutable. I've just realized that the problem is I declared var and not val – oxbow_lakes Mar 19 '09 at 19:24
add comment

You need to apply a lower bound on the parameter. I'm having a hard time remembering the syntax, but I think it would look something like this:

class Slot[+T, V <: T](var some: V) {

The Scala-by-example is a bit hard to understand, a few concrete examples would have helped.

Image (Asset 4/4) alt=49k11123284
answered Mar 19 '09 at 18:33
Corrected :> to be <: – oxbow_lakes Mar 19 '09 at 18:52
Thanks. I swapped the V and the T, but didn't change the bounding operator. – Saem Mar 19 '09 at 23:49
add comment

Your Answer

community wiki

Not the answer you're looking for? Browse other questions tagged or ask your own question.