A guest post by Vlad Patryshev, who was born in Russia, has an education in Math (including now popular category theory), and works at HealthExpense.com. A functional programmer and a Scala fan since 2008, he is now an organizer of Scala BASE and Bay Area Categories and Types meetups.

In this post, I explore the problem of mixing variance in Scala collections and I propose a solution derived from category theory, thus making Scala collections more type-safe.

## The Problem

If you have written code in Java, you know that although you have a `List<String>`

list, to which you can’t legally add anything but a String, you are allowed to check `list.contains(123)`

, since the method `contains()`

takes an Object as a parameter type.

The explanation lies in the collections covariance in Java: having class A, and class B extends A, you get `List<B>`

as a subtype of `List<A>`

. So, you can pass a `List<B>`

, where a `List<A>`

is required. This is convenient, and this is logical. Yet, if `List<B>`

has a method `contains(B b)`

, how can we possibly use it as a `List<A>`

, which is supposed to have a method `contains(A a)`

? This method, `contains(A x)`

, accepts any value of type `A`

. Our `List<B>`

has a method `contains(B x)`

– it only accepts values of type `B`

. We cannot magically extend a function’s domain from `B`

to `A`

.

The problem with `contains()`

is that it makes the class *contravariant*. You see, `contains(A a)`

should also be able to take any `B b`

as a parameter, as soon as `B`

is a subtype of A. From here it follows that any class `Coll<B>`

that has this method, should have this method applicable to any supertype of `B`

. That’s what contravariance is – the opposite of covariance. And this is why, in Java collections, `contains()`

is applicable to any Object.

We know that variance in particular, and generics in general are implemented wrongly in Java. This was the reason for creating Scala, according to Martin Odersky – to have a language with the right variance implementation. Unfortunately, in Scala too we can have `List(“a”, “b”, “c”).contains(42)`

compile without error messages.

This is weird. In Scala, you would expect better type safety, but this is easy to explain. While we can declare variance in Scala, and `List`

is covariant (defined as trait `List[+A]`

), `contains()`

requires contravariance (as in classes like `Map[-X,+Y]`

, and there is no reasonable way to combine variance in one parameterized type. This is why Scala `Set`

has eventually become an invariant: `Set[Dog]`

is not a subtype of `Set[Animal].`

, which is bad, but as a result, `Set("a", "b", "c").contains(42)`

will not compile, and this is good.

In an ideal world, `Set`

could be contravariant, which, in the real world, would leave us wondering why `Set[Animal]`

is a subtype of `Set[Dog]`

?

Having method `contains() take Any`

is even more confusing in Scala, since we can pass a closure. The statement `listOfInts.contains(_.isPrime)`

looks innocent, but what does it do? It checks if the function `(n:Int)=>n.isPrime()`

is a member of the list. It can’t be, if `listOfInts`

is declared as `List[Int]`

; so we have a cognitive dissonance here. If we were in the typeless world, we could not care, and we would agree with Senior Engineers telling us that we should be more careful. In Scala, we expect the compiler to be careful for us.

Can we fix this? I think we can. But first let’s take a look at it from the point of view of category theory. You can skip this part and go directly to the code solution below if you prefer.

## The Solution, Theory

Say we have a (covariant) functor `F: A → B`

and a contravariant functor `G:Aop → B`

. We can have a natural transformation from `F`

to `G`

, defined as a collection `tX:F(X) → G(X)`

, such that the following square commutes for each `f`

: `X → Y`

:

If you aren’t familiar with the idea, you can find the definition on Stackexchange.

So, how does this help us? First, let’s specify the category. Since we are talking about subtyping, in our category types will be objects, and the relationship of being a subtype will be arrows – so we actually have a poset. Now, in this category, we separate the covariant aspects into one, covariant, functor, and contravariant aspects in a contravariant functor, and have a natural transformation from one to another. In our case, we define List, or Tree, or any similar collection kind (or, one could say, algebraic functor), and have a natural transformation from this algebraic functor to the exponent functor, `F(X) → 2X`

. This is all that you need to do. See below, where I do this in plain Scala.

## The Solution, Practice

Instead of going ahead with the heavy generic case, we will see how we can solve the problem of `_.contains(Any)`

. We have a covariant collection, let’s call it `MyList[+A]`

, and let’s define it, as a demonstration, like as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
trait MyList[+T] { def head:T def tail:MyList[T] def ::[U>:T](x:U) = new HeadWithTail(x, this) def size: Int } case object EmptyList extends MyList[Nothing] { def head = error("This list is empty") def tail = error("this list is empty") def size = 0 } case class HeadWithTail[T](head:T, tail: MyList[T]) extends MyList[T] { def size = 1 + tail.size } |

Now we separate the method `contains()`

, defining it in a contravariant trait, like this:

1 2 3 |
trait Container[-T] { def contains(t:T): Boolean } |

To call this method on instances of `MyList[T]`

, we need an implicit natural transformation from `MyList[T]`

to `Container[T]`

, like this:

1 2 3 4 |
implicit def asContainer[T](list:MyList[T]): Container[T] = new Container[T] { def contains(t:T) = list.size > 0 && (list.head == t || asContainer(list.tail).contains(t)) } |

Now we can write `“Hello”::”World”::EmptyList contains “42”`

, but we can’t write `“Hello”::”World”::EmptyList contains 42`

.

Here are the tests:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
case class A(name: String) {override def toString = "A(" + name + ")"} case class B(override val name: String) extends A(name) {override def toString = "B(" + name + ")"} val listB = B("1") :: B("2") :: EmptyList listB.size must_== 2 val listA = A("3") :: listB listA.size must_== 3 listA contains A("3") must beTrue listA contains B("1") must beTrue // listB contains A(3) is a compilation error // listA contains "nothingness" is a compilation error val listC: MyList[Any] = listA listC contains "abracadabra" must beFalse listC contains B("2") must beTrue |

## Conclusion

I hope in time what I’ve covered in this post will be adopted in Scala, although probably not right away, but perhaps some time in the future. At least now we know the solution exists. Since new languages pop up all the time, if you have variance (and implicits), here’s what you can do to deal with them.

See below for some Scala resources from Safari Books Online.

## Read these titles on Safari Books Online

Not a subscriber? Sign up for a free trial.

Scala in Action is a comprehensive tutorial that introduces Scala through clear explanations and numerous hands-on examples. Because Scala is a rich and deep language, it can be daunting to absorb all the new concepts at once. This book takes a “how-to” approach, explaining language concepts as you explore familiar programming challenges that you face in your day-to-day work. | |

This book takes a step-by-step tutorial approach to teaching you Scala. Starting with the fundamental elements of the language, Programming in Scala introduces functional programming from the practitioner’s perspective, and describes advanced language features that can make you a better, more productive developer. | |

Scala in Depth is a unique new book designed to help you integrate Scala effectively into your development process. By presenting the emerging best practices and designs from the Scala community, it guides you though dozens of powerful techniques example by example. |

### About the author

Vlad Patryshev was born in Russia, and has an education in Math (including now popular category theory). Since 1998 in the US, he worked at Borland (JBuilder team), then at Google in various teams, and had a 20% project, an onscreen keyboard, now available on various Google pages. He then changed several Bay Area startups, and now is working at HealthExpense.com. A functional programmer and a Scala fan since 2008, he is now an organizer of Scala BASE and Bay Area Categories and Types meetups. As a hobby, he rides his road bike, builds decks, and drives around the US (Key West to the Polar Circle in Alaska). He can be reached at @vpatryshev. |