Mike Slinn
ScalaCourses.com

Parametric Variance and Bounds

— Draft —

Published 2014-11-04. Last modified 2019-07-11.
Time to read: 9 minutes.

Invariance, covariance and contravariance are demonstrated and explained. Lower bounds and upper bounds are introduced, and a thought-provoking example is shown.

The sample code for this lecture can be found in courseNotes/src/main/scala/ParametricBounds.scala.

Variance

As you know from the Parametric Types lecture, classes and traits can have parametric types, and methods can use these parametric types, or they can define additional parametric types. Up to now we have only discussed invariant parametric types (T). Immutable Scala objects can also be designated as covariant (+T) and contravariant (-T).

I will begin the explanation of variance by introducing some classes, then discuss an example of how variance works, then I will review the general rules with a diagram. The remainder of this lecture will provide further details. The cartoon midway through the lecture does a good job of explaining the difference between covariance and contravariance. You might want to read and/or watch this section twice before moving on.

First, let's define a base class called BaseClass, a subclass called SubClass, and three containers: InvariantContainer, CovariantContainer and ContravariantContainer. We will learn about variance by testing to see which types can be put in each of the three Container subtypes. Don’t get the wrong idea – containers can have multiple parametric types consisting of one or more of each type of variance: invariant, covariant and contravariant. We are just starting off with only one parameter. Later in this lecture we will explore the rules for how multiple types of variance coexist for any given class.

Scala code
class BaseClass
class SubClass extends BaseClass

trait Container
class InvariantContainer[T](t: T) extends Container      // this class has an invariant parameter
class CovariantContainer[+T](t: T) extends Container     // this class has a covariant parameter
class ContravariantContainer[-T](t: T) extends Container // this class has a contravariant parameter

Let’s create some instances of these classes:

Scala code
val baseClass = new BaseClass
val subClass  = new SubClass

val invariantContainingBase     = new InvariantContainer(baseClass)
val invariantContainingSub      = new InvariantContainer(subClass)

val covariantContainingBase     = new CovariantContainer(baseClass)
val covariantContainingSub      = new CovariantContainer(subClass)

val contravariantContainingBase = new ContravariantContainer(baseClass)
val contravariantContainingSub  = new ContravariantContainer(subClass)

Type Inference

Just a reminder: as we learned in the Parametric Types lecture earlier in this course, when creating instances of a container, Scala can often infer the parametric type, for example:

Scala REPL
scala> val icb1 = new InvariantContainer(baseClass)
icb1: InvariantContainer[BaseClass] = InvariantContainer@25c97c75

...has the same type as:

Scala REPL
scala> val idb2 = new InvariantContainer[BaseClass](baseClass)
idb2: InvariantContainer[BaseClass] = InvariantContainer@12e0f043

You can put the type hint on the left side of the equal sign to achieve the same result:

Scala REPL
scala> val idb3: InvariantContainer[BaseClass] = new InvariantContainer(baseClass)
idb3: InvariantContainer[BaseClass] = InvariantContainer@5425fca3

Normally, the only time you need to specify the type is when you want a non-default type parameter, like the following. If the type parameter [BaseClass] was not present, the Scala compiler would have looked at the argument (subClass), and inferred the parametric type to be SubClass.

Scala REPL
scala> val idb4 = new InvariantContainer[BaseClass](subClass)
idb4: InvariantContainer[BaseClass] = InvariantContainer@54e6204e

Non-Parametric Methods

Let’s define a method signature that accepts a container that does not accept a type parameter, called Container. As you would expect from standard object-oriented rules, this method accepts Container and all subclasses. We don’t need to define a method body in order to learn how variance works, but this body is handy because it shows the class name of the passed in container.

Scala code
def base(container: Container) = container.getClass.getName

base(invariantContainingBase)
base(invariantContainingSub)
base(covariantContainingBase)
base(covariantContainingSub)
base(contravariantContainingBase)
base(contravariantContainingSub)

Invariant Parameters

Now let’s define all valid methods which accept the invariant subclass of Container, InvariantContainer, parameterized first with BaseClass and then with SubClass. Each of these methods can only accept one type of argument, which must be exactly the specified type. You can think of invariant as meaning inflexible. Invariant types cannot be cast to subtypes or supertypes.

Scala code
def invariantWithBase(container: InvariantContainer[BaseClass]) = container.getClass.getName
invariantWithBase(invariantContainingBase)

def invariantWithSub(container: InvariantContainer[SubClass]) = container.getClass.getName
invariantWithSub(invariantContainingSub)
Method Argument Type Allowable Argument Type
InvariantContainer parameterized by BaseClass SubClass
BaseClass ✔  
SubClass   ✔

Covariant Parameters

Like non-parametric containers, and unlike invariant containers, covariant containers allow subclasses to be passed as arguments. This works because covariant containers of subclasses are subclasses of covariant containers of base classes. If you found that sentence confusing, wait a minute and I will show you a diagram that should help make this clear.

Scala code
def covariantWithBase(container: CovariantContainer[BaseClass]) = container.getClass.getName
covariantWithBase(covariantContainingBase)
covariantWithBase(covariantContainingSub)

def covariantWithSub(container: CovariantContainer[SubClass]) = container.getClass.getName
covariantWithSub(covariantContainingSub)
Method Argument Type Allowable Argument Type
CovariantContainer parameterized by BaseClass SubClass
BaseClass ✔ ✔
SubClass   ✔

Contravariant Parameters

Now for the unexpected: contravariant containers allow superclasses to be passed as arguments. This works because contravariant containers of subclasses are superclasses of contravariant containers of base classes. Again, the diagram I am about to show you should help make this clear.

Scala code
def contravariantWithBase(container: ContravariantContainer[BaseClass]) = container.getClass.getName
contravariantWithBase(contravariantContainingBase)

def contravariantWithSub(container: ContravariantContainer[SubClass]) = container.getClass.getName
contravariantWithSub(contravariantContainingBase)
contravariantWithSub(contravariantContainingSub)
Method Argument Type Allowable Argument Type
ContravariantContainer parameterized by BaseClass SubClass
BaseClass ✔  
SubClass ✔ ✔

Summary

This diagram summarizes how covariance and contravariance work.

Within the Scala type system a typing rule or a type constructor is:

  • covariant if a container of a subclass is a subtype of a container of the base type. We use a plus sign to indicate covariance.
  • contravariant if it reverses this ordering (a container of a superclass is a subtype of a container of the base type). We use a minus sign to indicate contravariance.
  • invariant if neither of these applies. No sign is required to indicate invariance – it is the default.

Read-only data types like return values (sources) can be covariant; write-only data types like parameters (sinks) can be contravariant. Mutable data types which act as both sources and sinks should be invariant.

Cartoon

Here is a cartoon that explains the difference between covariance and contravariance. The author is unknown, or I would give them credit. A short explanation is: consumers are contravariant, producers are covariant.

Variant Positions

Parametric containers can have methods which accept arguments which are of a parametric type. Those parameters must be contravariant. If the return type is parametric, it must be covariant. Thus we say that the contravariant positions are those corresponding to input type parameters, and the covariant position corresponds to the output type parameter. As an example, Functions have contravariant input parameters (-T1, -T2, etc) and a covariant return type (+R). Here are the method signatures for Function1.apply and Function2.apply.

Scala code
trait Function1[-T1, +R] extends AnyRef {
  def apply(v1: T1): R
}

trait Function2[-T1, -T2, +R] extends AnyRef {
  def apply(v1: T1, v2: T2): R
}

In summary, methods operating on immutable data can return covariant types, and contravariant types are used for parametric arguments. Covariant and contravariant types are immutable; a mutable type may not be designated as being covariant or contravariant – except for Array, as we shall see in a moment. Here is a good writeup on the distinction between the two.

Exercise - Create a Failure-Proof init Method

Enrich the IterableOps trait and add a failure-proof version of its init method, which accepts a Seq or subclass and returns all but the first element. Call this new method init2. Notice that IterableOps is parametric in A, CC and C.

trait IterableOps[+A, +CC[_], +C]
with IterableOnce[A]
with IterableOnceOps[A, CC, C]

Remember, init throws an exception under some circumstances.

Scala REPL
scala> val seq: Seq[Int] = List.empty[Int]
seq: Seq[Int] = List()

scala> seq.init
java.lang.UnsupportedOperationException: empty.init

We saw the necessary code to do this in the Immutable Collections lecture. Once again, here is the body of the method that you need to write.

Scala REPL
scala> seq.take(seq.size-1)
res2: Seq[Int] = List()

Review the Implicit Classes lecture if you need to refresh your memory of how to enrich a class.

Solution

Here is the enriched class:

Scala class
implicit class RichIterableOps[+A, +CC[_], +C](iterableOps: collection.IterableOps[A, CC, C]) {
  def init2: C = iterableOPs.take(iterableOPs.size-1)
}

You can see it in action here:

Scala REPL
scala> import scala.language.higherKinds
import scala.language.higherKinds

scala> implicit class RichIterableOps[+A, +CC[_], +C](iterableOps: collection.IterableOps[A, CC, C]) {
     |   def init2: C = iterableOps.take(iterableOps.size-1)
     | }
defined class RichIterableOps

scala> List(1,2,3).init2
res0: List[Int] = List(1, 2)

scala> List().init2
res1: List[Nothing] = List()

scala> Vector().init2
res2: scala.collection.immutable.Vector[Nothing] = Vector()

scala> Seq().init2
res3: Seq[Nothing] = List()

This solution is provided in courseNotes/src/main/scala/solutions/NoFailInit.scala.

Bounds

The following classes are referenced for the remainder of this lecture.

Scala code
abstract class Clothing(val size: Int, val manufacturer: String) extends Ordering[Clothing] {
  def compare(a: Clothing, b: Clothing) =  {
    val primaryKey = a.size - b.size
    if (primaryKey!=0) primaryKey else a.manufacturer compare b.manufacturer
  }

  override def equals(other: Any) = {
    try {
      val that = other.asInstanceOf[Clothing]
      this.size == that.size && this.manufacturer==that.manufacturer
    } catch {
      case e: Exception => false
    }
  }

  override def hashCode = super.hashCode

  override def toString = s"$productPrefix by $manufacturer of size $size"
}

object Clothing {
  implicit val ClothingOrdering = Ordering.by { clothing: Clothing =>
    (clothing.size, clothing.manufacturer)
  }
}

class Dress(override val size: Int, override val manufacturer: String) extends Clothing(size, manufacturer)

class Pants(override val size: Int, override val manufacturer: String) extends Clothing(size, manufacturer)

class Hat(override val size: Int, override val manufacturer: String) extends Clothing(size, manufacturer)

Upper Bounds

You might want to guarantee that a parametric type is a particular type, or a subtype. You can do that using upper bounds; the notation is <:. Upper bounds are often used with collections, especially sequences. As an example, let’s define a class that performs operations on Clothing and its subclasses.

Scala code
class ShoppingCart[A <: Clothing] {
  val items = ListBuffer.empty[A]

  def pick(item: A, count: Int): ShoppingCart[A] = {
    1 to count foreach { i =>
      items.+=:(item)
      s"Adding size ${item.size} by ${item.manufacturer} to shopping cart"
    }
    this
  }

  override def toString = {
    val strings = items.map(item => s"${item.productPrefix} size ${item.size} by ${item.manufacturer}").mkString("\n  ", "\n  ", "\n")
    s"ShoppingCart has ${items.size} items in it:$strings"
  }
}

Note that the type parameter A is constrained to be a Clothing or a subclass of Clothing, like Hat, Pants and Dress.

Scala code
val hat   = new Hat(5, "Gucci")
val pants = new Pants(5, "Ralph Lauren")
val dress = new Dress(4, "Donna Karan")

val shoppingCart = new ShoppingCart[Clothing].pick(hat, 2).pick(dress, 3).pick(pants, 5)

Lower Bounds

You can also specify lower bounds, which means that a parametric type must be a particular type or a supertype. The notation is B >: A if A is a lower bound for B (B is a supertype of A).

You can specify both lower and upper bounds, like this:

Scala code
def put[U >: T <: Clothing](item: U): Unit = ml += item

The above method is parametric in T, where T must be a Clothing or a subtype of Clothing, and a local type definition U is created which must be a T or a supertype of T. In other words, you can invoke the put method and pass in an instance of a Skirt or any other Clothing subclass. We will see an example of this in a moment.

Keeping Upper and Lower Bounds Straight

Here is a tip to help you remember what a higher or lower bound is. Below is the Scala inheritance tree we saw in the Type Hierarchy and Equality lecture of the Introduction to Scala course. The diagram starts at the top with Any, and goes down to the most specific type under consideration, and then to the bottom type, Nothing.

  • If A is a lower bound for B (written B >: A), then it means that B is the same or higher than A in the inheritance tree, i.e. B is closer to Any, so B is either A or a supertype of A.
  • If C is an upper bound for D (written D <: C), then it means that D is the same or lower than C in the inheritance tree, i.e. D is closer to Nothing, so D is either C or a subtype of C.
Scala Inheritance Diagram

Digging Deeper

Covariance

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, like this.

Scala REPL
scala> val xs: List[AnyVal] = List(1, 2, 3)
x: List[AnyVal] = List(1, 2, 3)

This is an intuitive way for generics to work, but the relationships do not hold when used with mutable data. One exception, because of how Java was implemented, is Array; Array[Hat] is a subtype of Array[Clothing], even though Array is mutable.

Scala REPL
scala> val clothing: Array[Clothing] = Array(new Hat(5, "Gucci"), new Hat(4, "Ralph Lauren"))
ys: Array[ParametricBounds.Clothing] = Array(Hat by Gucci of size 5, Hat by Ralph Lauren of size 4)

Covariant parameters are denoted by preceding them with a plus sign, like this: [+T]. If a type is covariant, instances can be converted from a wider type (Clothing) to a subtype (Hat). A covariant collection of subtypes is a subtype of the collection type.

Parametric containers can contain covariant types as well as covariant types that also have upper or lower bounds. For example:

Scala code
class Bag[+T <: Clothing] {
  val items = collection.mutable.MutableList.empty[Clothing]

  def putNG(item: T, quantity: Int): Bag[T] = {
    1 to quantity foreach { x => items += item }
    this
  }
}

The above is an example of combining covariance with upper bounds: [+T <: Clothing]. This means that T must be Clothing or a subtype (like Dress), and collections of T subtypes are also subtypes of collections of Clothing.

Since T is covariant, and Hat is a subtype of Clothing, then Bag[Hat] is a subtype of Bag[Clothing].

MutableList is defined to be invariant and so we cannot specify that it contains items of the covariant type parameter T. This only means that a MutableList[Dress] is not a subtype of MutableList[Clothing]. However, items can accept objects that are subclasses of Clothing, such as Dress.

Scala code
val clothingHamper: [Clothing] = collection.mutable.MutableList.empty[Dress]

The above compiles, but if you try to invoke putNG you will get this error message from the Scala compiler.

Scala code
covariant type T occurs in contravariant position in type T of value item

The explanation for the error message is quite theoretical – suffice it to say that when you put an item into a covariant collection you will need to specify a local supertype of the parametric type, such as U here.

Scala code
class Bag[+T <: Clothing] {
  val items = collection.mutable.MutableList.empty[Clothing]

  def put[U >: T <: Clothing](item: U, quantity: Int): Bag[T] = {
    1 to quantity foreach { x => items += item }
    this
  }
}

Contravariance

Contravariance, denoted with a negative sign [-T], means that an assigned type must be a supertype of the original collection, or the same type as the original collection. As with covariant types, contravariant types may only be immutable. Contravariant types can be converted from a subtype (like Dress) to its supertype (like Clothing). If the type Container has a contravariant type parameter.

Scala code
class Container[-T]

... then Container[Dress] is a supertype of Container[Clothing].

Type A<:B vs. Type +B

This section is inspired by Rex Kerr’s posting on Stack Overflow.

The upper bound type Q[A <: B] means that type Q can take any type A that is a subtype of B, or B itself. This is useful when you want to do something generic, but you need to rely upon a certain set of methods in B. For example, if you have an Output type with a maybeFile method, you could use that method in any type that could be passed into Q. This also works for a non-parametric class or object, like UpperBound shown here, that has a parametric method called read which is parameterized by the upper bound Output (scroll the code to view the read method).

Scala code
object UpperBound extends App {
  import java.io.File

  trait Output {
    def maybeFile: Option[File]
  }

  case class Storage(key: String, value: String) extends Output {
    val maybeFile: Option[File] = try {
      import java.nio.file._
      val file = new File(key).toPath
      val path: Path = Files.write(file, value.getBytes, StandardOpenOption.TRUNCATE_EXISTING, StandardOpenOption.WRITE, StandardOpenOption.CREATE)
      Some(path.toFile)
    } catch {
      case e: Exception =>
        println(e)
        None
    }
  }

  def read[A <: Output](a: A): String = {
    val maybeFile: Option[File] = a.maybeFile
    maybeFile.map(io.Source.fromFile(_).getLines().mkString).getOrElse("")
  }

  val readBackContents: String = read(Storage("storage.txt", "Blah blah blah"))
  println(s"Contents are ’$readBackContents’")
}

You can run this example by typing:

Shell
$ sbt "runMain UpperBound"
...Usual sbt output not shown...
Contents are ’Blah blah blah’

The covariant type Q[+B] means that Q can take any type, but if A is a subtype of B, then Q[A] is considered to be a subtype of Q[B]. This is useful when you want to make collections that behave the same way as the original types. If you take B and you make a subtype A, then you can pass A in anywhere where B is expected. If you have a method that accepts a collection of B, Q[B], you cannot pass in Q[A] unless it is designated as being covariant (+B). In other words Q covaries (follows along with) B’s subtypes’ inheritance relationship.

The covariant upper bound type Q[+A <: B] means that type Q can only take subtypes of B (including B), and the subtype relationship between A and B is propagated to Q[A] and Q[B].

Understanding How to Combine Variance and Bounds

Let’s look at some concrete examples of combining variance and bounds. Take the case of Container2 covariant in A, and try to add a method to this type that accepts (consumes) A as an argument.

Scala code, does not compile
case class Container2[+A] {
  def consume(a: A): Unit = println(a)
}

The above will not compile. If you try this code in the REPL, Scala will complain as follows:

Scala REPL error message
error: covariant type A occurs in contravariant position in type A of value a
def consume(a: A): Unit = println(a)

The reason this doesn’t work is that type safety is violated. If you have a Container covariant in A and you could accept any subtype of A, you could potentially create an object that’s parameterized by the subtype, assign it to a supertype, and then try inserting another subtype, which would fail at runtime. The classic case that illustrates this is the covariant array in Java.

Scala code
public class TypeSafety {
  public static void main(String[] args) {
    String[] covariantArrayOfString = new String[] {"a", "b", "c"};
    Object[] covariantArrayOfObject = covariantArrayOfString;
    covariantArrayOfObject[0] = 1;
  }
}

This code compiles but fails at runtime.

Shell
$ sbt "runMain TypeSafety"
...usual SBT output not shown ...
Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer
  at TypeSafety.main(TypeSafety.java:5)

What happened? A String is an Object, and arrays are covariant in Java, so an array of Strings (String[]) is an array of Object (Object[]). So, we instantiate an array of Strings, then assign a reference of type of an Object array to point to the array of Strings. This means that we can add any Object to any element of the array. If we try storing an Integer in the array, we’ll get an ArrayStoreException because the array was allocated for Strings. The Java compiler allows covariance but because of its type system flaw, Java needs to check the type at runtime and prevent the wrong type from being stored. This means that the compiler fails to prevent a type error. Scala’s type system does not allow this problem.

Scala REPL
scala> val ss: Array[String] = Array("a", "b", "c")

scala> %}val os: Array[Object] = ss
error: type mismatch;
 found   : Array[String]
 required: Array[Object]
Note: String <: Object, but class Array is invariant in type T.
You may wish to investigate a wildcard such as `_><: Object`.
(SLS 3.2.10)
       val os: Array[Object] = ss
                              ^>

Going back toContainer2[+A], this is exactly why we can’t have a consume method accepting A while the Container2 is covariant in A. So what do we do if the object has to accept A or the subtypes of A? We can add a lower bound of A for B in the method signature. Since B is a supertype of A, hence "higher" in the hierarchy (where Any is at the top of the hierarchy), so A is a lower bound for B because it’s its subtype of A or A itself.

Scala code
case class Container3[+A](a: A) {
  def consume[B >: A](b: B): Unit = println(s"$a $b")
}

Container3("Hello to all my").consume("fans")

Now the consume method will accept types that are either A or supertypes of A. But since the Container2 is covariant in A, what we care about is that the method will now accept A. While variance and bounds are important by themselves, they are even more powerful and useful when combined because they provide type safety and flexibility.

We can run this as TypeSafety2:

Shell
$ sbt "runMain TypeSafety2"
...Usual sbt output not shown...
Hello to all my fans

Scala 2 Breaks the Rules

Scala’s variance mechansim breaks the Liskov Substitution Principle. Hopefully Scala 3 will fix this.

Previous lecture:

Next lecture:
* indicates a required field.

Please select the following to receive Mike Slinn’s newsletter:

You can unsubscribe at any time by clicking the link in the footer of emails.

Mike Slinn uses Mailchimp as his marketing platform. By clicking below to subscribe, you acknowledge that your information will be transferred to Mailchimp for processing. Learn more about Mailchimp’s privacy practices.