Covariance and Contravariance in Scala

One great feature brought by Scala is that you can do generics in very succinct ways, also convenient is making covariances and contravariances on generic classes, like writing something like class A[+T] or class A[-T]. The former is termed “covariance” meaning that if U is a subclass of V then A[U] is a subclass of A[V], while the latter is termed “contravariance” and has the opposite meaning of if V is a subclass U then A[U] is a subclass of A[V].

The wording of the above principles is easy to memorize, seemingly straightforward to comprehend, until you come across this example listed on https://docs.scala-lang.org/tutorials/tour/variances.html

class Stack[+T]{
  def push[S >: T](elem: S): Stack[S] = new Stack[S]{
    override def top: S = elem
    override def pop: Stack[S] = Stack.this
    override def toString: String =
      elem.toString + " " + Stack.this.toString
    }
  def top: T = sys.error("no element on stack")
  def pop: Stack[T] = sys.error("no element on stack")
  override def toString: String = ""
}

object VariancesTest extends App {
  var s: Stack[Any] = new Stack().push("hello")
  s = s.push(new Object())
  s = s.push(7)
  println(s)
}

This is an immutable stack implementation where every time you push to or pop away from the stack, you get a new Stack instance. Obviously, this example is about covariance, but it appears quite insane to me as I saw the line def push[S >: T](elem: S) harshly contradicts the line var s: Stack[Any] = newStack().push("hello"). Why? Because the method definition says that you must pass something that is a superclass of Tto method push, how dare you to push a string to a stack that is supposed to hold type Any? Apparently, I was not alone being dubious, as you can see in the comment area there are people raising this same question and even harvested a few upvotes.

This question perplexed me for quite a while and after figuring out the rationale behind the scene I couldn’t help laughing. In fact, there are two things tangled together here. First, every time you invoke push, you are essentially creating an anonymous subclass of Stack, and since Stack is covariant on T, you cannot let T appear in the argument list of Stack’s member methods, which is to ensure Liskov substitution principle. Here is an example to explain Liskov substitution principle. Suppose you have a class

abstract class Automaker[-T, +R] {
  // build a vehicle from the material provided
  def build(material: T): R
}

and you create a class like this

class GermanAutomaker[Steel, Volkswagon] extends Automaker[Steel, Volkswagon] {
  def build(material: Steel): Volkswagon = ???
}

That’s perfectly fine! Now you want to define a subclass of GermanAutomaker, say FancyGermanAutomaker. Before you do that, take a moment to think what would people expect from FancyGermanAutomaker? Yes, complete substitution. Whenever people need a GermanAutomaker, a FancyGermanAutomaker will work just as fine. So there are two meanings here – first, if people ask you to build something, they are at least expecting a Volkswagon as output, and you must be able to build a Volkswagon, e.g. Jetta, Passat, but never a BMW. Second, if people are feeding you steel as the building material, you must able to accept. Of course, if you are not picky you can accept a more general material such as metal, that’s fine, but never complain “I need stainless steel!” That being said, your FancyGermanAutomaker could look something like this

class FancyGermanAutomaker[Metal, Passat] extends GermanAutomaker[Steel, Volkswagon]{
  def build(material: Metal): Passat = ???
}

Translating Liskov substitution principle into plain English would be

In order to substitute another class, you must be able to consume a broader range of inputs and produce a stricter range of outputs.

Like back in those miserable slavery days a slave owner would only be interested in substituting his current slave for a new one if that new one is less picky about consuming food and more deft in making gadgets. Going back to the aforementioned example, it explains why we need to write def push[S >: T](elem: S): Stack[S], because you are defining a subsclass of Stack, and Stack is covariant on T, so you cannot use T in the method argument list. You can only use another class S and explicitly point out that S is a super type of T.

Finally, we can come to the question why we can do s = s.push(7)? Is Integer a super class of Any? Sure it is not, but Scala is smart enough to do an implicit conversion here. It will figure out on it own how many downward casts it is required to convert an Integer to be a super or equal class of Any. It will find out that the best it can do is to convert 7 into Any and complete this push.