Variance, Immutability, and Strictness in Kotlin

Variance is the way parameterized types relate regarding inheritance of their type parameter. This article will first offer a reminder of how variance works, and then elaborate how strictness and mutability interfere with variance — and how to deal with this problem. This is a preview of my upcoming book The Joy of Kotlin, published by Manning.

Let’s start with an example object hierarchy. As you can see in the following figure, Gala extends Apple, which in turn extends Fruit. In other words, a Gala is an Apple and an Apple is a Fruit.

A Producer<Gala> is a function (or an object containing a function) that produces a Gala. It seems then natural to consider that a Producer<Gala> is a Producer<Apple>, which is a Producer<Fruit>. Or in other words, that Producer<Gala> extends Producer<Apple>, which in turn extends Producer<Fruit>. Producer is then said to be covariant on its type parameter, because inheritance of the parameterized type applies in the same direction as inheritance of its type parameter.

Conversely, a Consumer<Fruit> can consume any fruit, among which apples, and a`Consumer<Apple>` can consume any apple, among which are Galas. So wherever a Consumer<Gala> is needed, you can use a Consumer<Apple> or a Consumer`Fruit. This is because a Consumer<Fruit> is a Consumer<Apple>, which in turn is a Consumer<Gala>. Or we can say that Consumer<Fruit> extends Consumer<Apple>, which in turns extends Consumer<Gala>. As inheritance of Consumer works here in an inverse way than how it works for the type parameter, Consumer is said to be contravariant on its parameter.

Now consider a Basket<Apple>: You can get an Apple, which is a Fruit, out of it, or you can put an Apple into it, but also a Gala. Basket both supplies and consumes objects of its parameter type, so it can neither be covariant nor contravariant. It is thus said to be invariant, which simply means that there is no inheritance relation among Basket<Fruit>, Basket<Apple>, and Basket<Gala>.

You might, however, disagree with this, arguing that after all, a basket of apples is a basket of fruit, which would make it a covariant basket. This is not exactly true. It is only true if you are very careful when putting fruit into it. If your basket of apples is a basket of fruit, nothing prevents you from putting a fruit into it that might not be an apple. So you would need to check the type of the fruit before trying to put it into the basket.

Let’s see how this translates into code using Kotlin. You can’t use Java for this example because Java does not handle variance. In Java, all parameterized types are invariant. Kotlin is very similar to Java, so even if you don’t know this language, you will easily understand the example.

Let’s first define our fruit:

open class Fruit
open class Apple: Fruit() // Apple extends Fruit
class Gala: Apple() // Gala extends Apple

In Kotlin, classes are final by default, so they must be declared open so they can be extended.

Here are now some examples of variance:

class Variance {
    val fruitProducer: () -> Fruit = ::Fruit
    val appleProducer: () -> Apple = ::Apple
    val galaProducer: () -> Gala = ::Gala
    val fruitConsumer: (Fruit) -> Unit = ::eatFruit
    val appleConsumer: (Apple) -> Unit = ::eatApple
    val galaConsumer: (Gala) -> Unit = ::eatGala
    val newFruitProducer1: () -> Fruit = appleProducer
    val newFruitProducer2: () -> Fruit = galaProducer
    val newAppleProducer: () -> Apple = galaProducer
    val newGalaConsumer1: (Gala) -> Unit = appleConsumer
    val newGalaConsumer2: (Gala) -> Unit = fruitConsumer
    val newAppleConsumer: (Fruit) -> Unit = fruitConsumer
}

fun eatFruit(fruit: Fruit) {}
fun eatApple(apple: Apple) {}
fun eatGala(fruit: Gala) {}

If you don’t know Kotlin, here is the equivalent Java code:

public class Variance {

    Supplier<Fruit> fruitSupplier = Apple::new;
    Supplier<Apple> appleSupplier = Apple::new;
    Supplier<Gala> galaSupplier = Gala::new;
    Consumer<Fruit> fruitConsumer = this::eatFruit;
    Consumer<Apple> appleConsumer = this::eatApple;
    Consumer<Gala> galaConsumer = this::eatGala;
    Supplier<Fruit> newFruitSupplier1 = appleSupplier; // Compile error
    Supplier<Fruit> newFruitSupplier2 = galaSupplier; // Compile error
    Supplier<Fruit> newAppleSupplier = galaSupplier; // Compile error
    Consumer<Gala> newGalaConsumer1 = appleConsumer; // Compile error
    Consumer<Gala> newGalaConsumer2 = fruitConsumer; // Compile error
    Consumer<Apple> newAppleConsumer= fruitConsumer; // Compile error

    void eatFruit(Fruit fruit) {}
    void eatApple(Apple apple) {}
    void eatGala(Gala fruit) {}
}

As you can see, Java doesn’t allow us to cast Supplier and Consumer according to their type parameter hierarchy like Kotlin does. So Kotlin brings us covariance and contravariance for types that are strictly compatible, meaning types using their parameter in either covariant or contravariant positions, but not both.

Now, let’s define our Basket<T>, starting with an invariant version:

sealed class Basket<T> {

    abstract fun getFirst(): T

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

    class EmptyBasket<T>: Basket<T>() {

        override fun getFirst(): T = throw NoSuchElementException()
    }

    class NonEmptyBasket<T>(private val t: T, private val rest: Basket<T>): Basket<T>() {

        override fun getFirst(): T = t
    }
}

(Beware that this is just an oversimplified example!)

This is equivalent to an abstract Basket<T> class in Java with two internal subclasses, the NonEmptyBasket class having two properties: first, being the first available T on top of the basket, and rest, being the rest of the `T`s in the basket. (In fact, this is a simplified immutable linked list.)

The problem with this implementation is that it is invariant. The Basket class acts both as a producer and a consumer, if you simply declare it covariant, which can be done by using the out keyword, as in:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    fun add(t: T): Basket<T> = NonEmptyBasket(t, this) // compile error

You get a compile error saying that in function add, type parameter T, which is declared as out (covariant), occurs in the in (contravariant) position. The out keyword allows you to use a Basket<Apple> where a Basket<Fruit> is needed, but it would also allow you to add a Fruit to a Basket<Apple>, which could be harmful if this Fruit were not an Apple.

But wait. This can’t happen because the add function takes a T as its parameter, so it will always reject a super type of T. What you need is to tell the compiler that you want to take responsibility for bypassing type checking — and this can be done using the @UnsafeVariance annotation:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

If you try adding a Fruit to a Basket<Apple>, you’ll get a compile error:

fun main(args: Array<String>) {
    val basket = Basket.EmptyBasket<Apple>()
    val newBasket = basket.add(Fruit()) // Compile error
}

However, if you treat your Basket<Apple> as a Basket<Fruit>, you suddenly are able to add a Fruit to it, which might not be an Apple:

fun main(args: Array<String>) {
    val basket = Basket.EmptyBasket<Apple>()
    val fruitBasket: Basket<Fruit> = basket
    val newFruitBasket = fruitBasket.add(Fruit())
}

The Relationship Between Variance and Immutability

As you can see, a Basket<Apple> can be treated as a Basket<Fruit>, allowing one to add a Fruit that might not be an Apple into it. But this is not a problem because Basket is immutable. When basket is affected by the fruitBasket: Basket<Fruit>, it is still a Basket<Apple> — and this will never change. Inserting a Fruit into it will simply produce a new Basket<Fruit>, which will never be a Basket<Apple>.

But this is safe only with immutable baskets. With a mutable Basket<Apple>, one would be able to insert a Fruit into a Basket<Apple> and the compiler would say nothing because you would have taken responsibility for this:

class MutableBasket<out T> {
    val content = mutableListOf<@UnsafeVariance T>()

    fun getFirst(): T = content.removeAt(0)

    fun add(t: @UnsafeVariance T) = content.add(t)
}

val mbasket = MutableBasket<Apple>()
mbasket.add(Apple())
//mbasket.add(Fruit()) // Compile error
val mfruitBasket: MutableBasket<Fruit> = mbasket
mfruitBasket.add(Fruit())
mfruitBasket.add(Fruit())
val mFruit1: Apple = mbasket.getFirst()
println(mFruit1)
val mFruit2: Fruit = mbasket.getFirst()
println(mFruit2)
val mFruit3: Fruit = mbasket.getFirst()
println(mFruit3)

As you can see, you can’t insert a Fruit into a MutableBasket<Apple>, but you can through the mfruitBasket: MutableBasket<Fruit> reference, although it is the same basket. Once you have done this, you can still get an element out of the basket and affect it via an Apple reference, and this will work if the returned object is an Apple, as is shown by the first output line of this program:

com.asn.dbreplicator.agent.client.business.test.Apple@6b884d57

However, getting the third element (a Fruit) and trying to affect it via an Apple reference causes a `ClassCastException':

Exception in thread "main" java.lang.ClassCastException: Fruit cannot be cast to Apple

So you see that covariance may safely be applied to collections only if they are immutable. Applying it to mutable collections would result in very unsafe programs.

The Relationship Between Variance and Strictness

A major benefit of making immutable collections covariant is that you can then treat empty collections for what they are. Think about an empty basket. Is it an empty basket of apples? Or an empty basket of fruit? Or an empty basket of anything else?

Of course, an empty basket has no specific type. In fact, it can have any type. Should you then parameterize the EmptyBasket type with Any (the Kotlin equivalent for a Java Object)? Of course not, since you would be unable to cast it into any specific type when adding an element of a given type.

Should you then parameterize it with a specific type? For this, Kotlin offers the special type Nothing, which is a subtype of all other types. You can then simply parametrize the empty basket with this type. And due to covariance, an EmptyBasket<Nothing> is a subtype of Basket<T>, whatever T actually is. So you need only one EmptyBasket<Nothing> and thus, you can make it a singleton object:

object EmptyBasket: Basket<Nothing>() {

    override fun getFirst(): Nothing = throw NoSuchElementException()
}

But you are still having a problem. Imagine you want to test whether a basket contains a given element. You could define a contains abstract function in the parent class and implement it in each subclass:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    abstract fun contains(t: @UnsafeVariance T): Boolean

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

    object EmptyBasket: Basket<Nothing>() {

        override fun contains(t: Nothing): Boolean = false

        override fun getFirst(): Nothing = throw NoSuchElementException()
    }

    class NonEmptyBasket<out T>(private val t: T, private val rest: Basket<T>): Basket<T>() {

        override fun contains(t: @UnsafeVariance T): Boolean = t == this.t || rest.contains(t)

        override fun getFirst(): T = t
    }
}

However, this won’t work. Let’s try running the following program:

fun main(args: Array<String>) {
    val basket: Basket<Apple> = Basket.EmptyBasket
    val apple1 = Apple()
    val apple2 = Apple()
    val appleBasket = basket.add(apple1)
    println(appleBasket.contains(apple1))
    println(appleBasket.contains(apple2))
}

Here is what you get:

true
Exception in thread "main" java.lang.ClassCastException: Apple cannot be cast to java.lang.Void

What’s happening? Although the error message is rather weird, you can assume that it is due to casting Applei\ into Nothing, which is, of course, illegal since Nothing is a subclass of Apple and not the other way round. As the contains function is recursive, and the error happens when using contains with an object that is not in the basket, you also can assume that it happens when testing the empty basket. But for this test, you should not need any casting, since the contains function simply returnsfalse.

Here, you are bitten by strictness. Kotlin, like Java, is a strict language. This means that function arguments are evaluated as soon as they are received, even if they are eventually not used, which is precisely the case with EmptyBasket.contains.

What can you do to work around this problem? You have a choice. You can make the contains function lazy, or you can bypass this function call. To bypass the function call, you can simply test the class of the Basket and simply return false if it is the EmptyBasket:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    fun contains(t: @UnsafeVariance T): Boolean = when (this) {
        is EmptyBasket -> false
        is NonEmptyBasket -> this.t == t || this.rest.contains(t)
    }

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

    object EmptyBasket: Basket<Nothing>() {

        override fun getFirst(): Nothing = throw NoSuchElementException()
    }

    class NonEmptyBasket<out T>(internal val t: T, internal val rest: Basket<T>): Basket<T>() {

        override fun getFirst(): T = t
    }
}

Note that you had to make the NonEmptyBasket constructor parameters internal instead of private since unlike in Java, Kotlin classes cannot access private members of inner classes (but like Java, inner classes may access private members of the enclosing class.)

Another solution is to make the contains parameter lazy, which can be done as follows:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    abstract fun contains(st: () -> @UnsafeVariance T): Boolean

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

    object EmptyBasket: Basket<Nothing>() {

        override fun contains(st: () -> Nothing): Boolean = false

        override fun getFirst(): Nothing = throw NoSuchElementException()
    }

    class NonEmptyBasket<out T>(private val t: T, private val rest: Basket<T>): Basket<T>() {

        override fun contains(st: () -> @UnsafeVariance T): Boolean = st() == this.t || rest.contains(st)

        override fun getFirst(): T = t
    }
}

This is less practical because you have to change the user program:

fun main(args: Array<String>) {
    val basket: Basket<Apple> = Basket.EmptyBasket
    val apple1 = Apple()
    val apple2 = Apple()
    val appleBasket = basket.add(apple1)
    println(appleBasket.contains { apple1 })
    println(appleBasket.contains { apple2 })
}

This programs prints:

true
false

A third (and probably best) solution is to declare EmptyBasket abstract and parameterize it with T, and then implement it as a singleton object. This way, the contains function may be defined in the abstract EmptyBasket class, where the T parameter type is accessible:

sealed class Basket<out T> {

    abstract fun getFirst(): T

    abstract fun contains(t: @UnsafeVariance T): Boolean

    fun add(t: @UnsafeVariance T): Basket<T> = NonEmptyBasket(t, this)

    abstract class Empty<out T>: Basket<T>() {

        override fun getFirst(): T = throw NoSuchElementException()

        override fun contains(t: @UnsafeVariance T): Boolean = false
    }

    object EmptyBasket: Empty<Nothing>()

    class NonEmptyBasket<out T>(internal val t: T, internal val rest: Basket<T>): Basket<T>() {

        override fun getFirst(): T = t

        override fun contains(t: @UnsafeVariance T): Boolean = this.t == t || this.rest.contains(t)
    }
}

Conclusion

The fact that Kotlin handles variance is a great plus compared to Java — but it comes with limitations. Greater freedom implies greater responsibility. Compiletime problems are not a big deal, they will simply make your job a bit more difficult. But runtime problems may make your programs much less reliable. This is an area where immutability helps make programs safer. A good understanding of laziness also helps. Kotlin does not handle true laziness out of the box, but you can easily implement it. You can implement much more powerful laziness than what was shown in this example, but that would be the subject of another article.