How (and why) to make mutable collections invariant in Scala

This is an excerpt from the Scala Cookbook (partially modified for the internet). This is Recipe 19.4, “How to make mutable collections invariant in Scala.”

Problem

You want to create a collection whose elements can be mutated, and want to know how to specify the generic type parameter for its elements.

Solution

When creating a collection of elements that can be changed (mutated), its generic type parameter should be declared as [A], making it invariant.

For instance, elements in a Scala Array or ArrayBuffer can be mutated, and their signatures are declared like this:

class Array[A] ...
class ArrayBuffer[A] ...

Declaring a type as invariant has several effects. First, the container can hold both the specified types as well as its subtypes. For example, the following class hierarchy states that the Dog and SuperDog classes both extend the Animal trait:

trait Animal {
    def speak
}

class Dog(var name: String) extends Animal {
    def speak { println("woof") }
    override def toString = name
}

class SuperDog(name: String) extends Dog(name) {
    def useSuperPower { println("Using my superpower!") }
}

With these classes, you can create a Dog and a SuperDog:

val fido = new Dog("Fido")
val wonderDog = new SuperDog("Wonder Dog")
val shaggy = new SuperDog("Shaggy")

When you later declare an ArrayBuffer[Dog], you can add both Dog and SuperDog instances to it:

val dogs = ArrayBuffer[Dog]()
dogs += fido
dogs += wonderDog

So a collection with an invariant type parameter can contain elements of the base type, and subtypes of the base type.

The second effect of declaring an invariant type is the primary purpose of this recipe.

Given the same code, you can define a method as follows to accept an ArrayBuffer[Dog], and then have each Dog speak:

import collection.mutable.ArrayBuffer

def makeDogsSpeak(dogs: ArrayBuffer[Dog]) {
    dogs.foreach(_.speak)
}

Because of its definition, this works fine when you pass it an ArrayBuffer[Dog]:

val dogs = ArrayBuffer[Dog]()
dogs += fido
makeDogsSpeak(dogs)

However, the makeDogsSpeak call won’t compile if you attempt to pass it an ArrayBuffer[SuperDog]:

val superDogs = ArrayBuffer[SuperDog]()
superDogs += shaggy
superDogs += wonderDog
makeDogsSpeak(superDogs)  // ERROR: won't compile

This code won’t compile because of the conflict built up in this situation:

• Elements in an ArrayBuffer can be mutated.
• makeDogsSpeak is defined to accept a parameter of type ArrayBuffer[Dog].
• You’re attempting to pass in superDogs, whose type is ArrayBuffer[SuperDog].
• If the compiler allowed this, makeDogsSpeak could replace SuperDog elements in superDogs with plain old Dog elements. This can’t be allowed.

As stated, one of the reasons this problem occurs is that ArrayBuffer elements can be mutated. If you want to write a method to make all Dog types and subtypes speak, define it to accept a collection of immutable elements, such as a List, Seq, or Vector.

Discussion

The elements of the Array, ArrayBuffer, and ListBuffer classes can be mutated, and they’re all defined with invariant type parameters:

class Array[T]
class ArrayBuffer[A]
class ListBuffer[A]

Conversely, collections classes that are immutable identify their generic type parameters differently, with the + symbol, as shown here:

class List[+T]
class Vector[+A]
trait Seq[+A]

The + symbol used on the type parameters of the immutable collections defines their parameters to be covariant. Because their elements can’t be mutated, adding this symbol makes them more flexible, as discussed in the next recipe.

See Also

• You can find the source code for Scala classes by following the “Source code” links in their Scaladoc. The source code for the ArrayBuffer class isn’t too long, and it shows how the type parameter A ends up sprinkled throughout the class.