Why doesn't the example compile, aka how does (co-, contra-, and in-) variance work?

Question

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

class Slot[+T] (var some: T) { 
   //  DOES NOT COMPILE 
   //  "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) { 
}

Solution 1

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 Integer[1];
arr[0] = "Hello, there!";

We just assigned a value of type String to an array of type Integer[]. 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 <: 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 invariant. 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.

Solution 2

@Daniel has explained it very well. But to explain it in short, if it was allowed:

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

  val slot: Slot[Dog] = new Slot[Dog](new Dog)   
  val slot2: Slot[Animal] = slot  //because of co-variance 
  slot2.some = new Animal   //legal as some is a var
  slot.get ??

slot.get will then throw an error at runtime as it was unsuccessful in converting an Animal to Dog (duh!).

In general mutability doesn't go well with co-variance and contra-variance. That is the reason why all Java collections are invariant.

Solution 3

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
y.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.

Solution 4

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) {
  //blah
}

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

View more solutions

Comments

[oxbow_lakes]

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.

[user573215]

This might be interesting in this context: scala-lang.org/old/node/129

[oxbow_lakes]

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]

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

[MarkusQ]

@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...

[oxbow_lakes]

Sorry - I don't want my slot to be mutable. I've just realized that the problem is I declared var and not val

[Kristen]

Could this be stated in plain english as - you can take something more simple as a parameter and you can return something more complex?

[Emre Sevinç]

Java compiler (1.7.0) does not compile "Object[] arr = new int[1];" but rather gives the error message: "java: incompatible types required: java.lang.Object[] found: int[]". I think you meant "Object[] arr = new Integer[1];".

[perryzheng]

When you mentioned, "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)." Could you actually give a couple examples?

[Lasf]

@perryzheng per this, take trait Animal, trait Cow extends Animal, def iNeedACowHerder(herder: Cow => Unit, c: Cow) = herder(c) and def iNeedAnAnimalHerder(herder: Animal => Unit, a: Animal) = herder(a). Then, iNeedACowHerder({ a: Animal => println("I can herd any animal, including cows") }, new Cow {}) is okay, as our animal herder can herd cows, but iNeedAnAnimalHerder({ c: Cow => println("I can herd only cows, not any animal") }, new Animal {}) gives a compile error, as our cow herder can't herd all animals.

[Peter Schmitz]

This is related and helped me with variance: typelevel.org/blog/2016/02/04/variance-and-functors.html

[Vladimir Nabokov]

Input-output abstraction helps. you can only refine and refine an input, if you pass it from an external wrapper(sub-function) to an internal target(function), and you can only generalize and generalize an output that comes from the internal target (function) back to the wrapper(sub-function). Way in - refinement, way out - coarsening.

[Jordan Parmer]

A nice breakdown can be found here: atlassian.com/blog/software-teams/…