2010-01-24

Scala and Covariance

I was recently programming a very simple Scala program that would process clouds, and by clouds I mean objects containing an item (e.g. a link) and a value.

package me.m1key.clouds

class Cloud[T](val cloudItem: T, val value: Int) {

}

As you can see, it's very simple. The cloud item will hold a URL or any other kind of object (so not just text links) and the value is an integer. I used the val keyword to make properties immutable and accessible from the outside, the Scala way that is. As you can see, this class is parametrized so that when you have a cloud with a known parametrized type you do not have to do casting (whether it would be useful in a non-academic environment is probably arguable).

I also wrote a simple collection alike class. Please see:

package me.m1key.clouds

import _root_.scala.collection.mutable.ListBuffer

class CloudCollection() {
 
  val clouds = new ListBuffer[Cloud[Any]]
 
  def add(clouds: Cloud[Any]*) = {
    for (cloud <- clouds) {
      this.clouds += cloud
    }
  }

  // Some code omitted for brevity.
 
  def getClouds(f: (Cloud[Any]) => Boolean) : Seq[Cloud[Any]] = {
    for {
      cloud <- clouds
      if f(cloud)
    } yield cloud
  }

}

Now, let's test this with the Specs library. (I will write a separate article on simple unit testing in Eclipse.)

package me.m1key.clouds

import org.specs.runner.JUnit4
import org.specs.runner._
import org.specs._

class JCloudCollectionSpecTest extends JUnit4(CloudCollectionSpec)


object CloudCollectionSpec extends Specification {
 
  "A cloud collection" should {
    "allow for adding a value and contain it" in {
      val cloud = new Cloud("Michal", 30)
      val collection = new CloudCollection
      collection.add(cloud)
      collection.contains(cloud) mustEqual true
    }
  }
  // More tests.
}

Uh-oh. That actually causes a compile-time error! What does it say?

type mismatch;
found : me.m1key.clouds.Cloud[java.lang.String]
required: me.m1key.clouds.Cloud[Any] CloudCollectionSpec.scala


Hmmm. I cannot apply Cloud[java.lang.String] to Cloud[Any] - why? Isn't every String an Any (which is roughly an equivalent of Object in Java) in Scala? Enter covariance.

Let's generalize. Imagine we have a parametrized class C (just like the Cloud class).
Now, imagine we have two instances of it, declared as C[A] (just like Cloud[String] in our example), and C[B] (Cloud[Any]).
Imagine also that A is a subclass of B (just like String is a subclass of Any). But that doesn't mean that C[A] is a subclass of C[B]! It is called invariance. Although A and B are related, C[A] and C[B] are not. That is why in our example I cannot assign Cloud[String] to Cloud[Any] - my parametrized Cloud class is invariant, i.e. it does not support covariance (nor does it support contravariance). What exactly is covariance and contravariance?

If you want the ordering to be preserved, that is, for parametrized class C:
if A is a subtype of B and you want C[A] to be a subtype of C[B], then you need covariance.
Contravariance reverses the ordering.

Scala defines so called variance annotations: plus (+) and minus (-). The plus is Scala's covariance operator. The minus - contravariance. No operator (like in the Cloud example above) means invariance.

So, when I declare my Cloud class with the covariance operator, my code compiles.

package me.m1key.clouds

class Cloud[+T](val cloudItem: T, val value: Int) {

}

Why? Because thanks to the plus operator, Cloud[java.util.String] is a subclass of Cloud[Any]. I can provide a Cloud[String] when a Cloud[Any] is expected. Or Cloud[Int]. Or Cloud[Long] etc.

One more example to clarify?

If my class is defined as C[T] then when a method expects a C[T] parameter, it can only get C[T] kind of objects. That's invariance.

If my class is defined as C[+T] then when a method expects a C[T] parameter, it can get any C[A] object provided that A is T or A is a subclass of T.

If my class is defined as C[-T] then when a method expects a C[T] parameter, it can get any C[B] object provided that B is T or B is a superclass of T.

Why is invariance the default behavior (both in Scala and in Java)? - you might ask. That is because it might cause problems when using mutable data.

One last note is: if you need more accuracy when defining e.g. method parameters, type bounds are what you are probably looking for.

Download the tiny code sample for this article.

1 comment: