Why is GenSet declared to have invariant type parameter?

Question

I have a type Foo, with subtypes.

I have another class that contains, among other things, a Foo:

class FooResult(val foo: Foo ...

I have a Set of FooResult, and I wish to pull the Foos out of it with a map(), and then calc the diff between that Set (of Foos) and another Set of Foos. 'results' below is a Set[FooResult] and - this is the critical part - bundle is a Set[_ <: Foo]

val completedFoos = results.map(result => result.calc)
val unfinishedFoos = bundle.foos.diff(completedCalcs)

The second line will not compile. It worked fine when bundle was a Set[Foo] instead of Set[_ <: Foo] - introducing the covariance screws things up. This is the error:

type mismatch;
found   : Set[Foo]
required: scala.collection.GenSet[_$1]
Note: Foo >: _$1, but trait GenSet is invariant in type A.
You may wish to investigate a wildcard type such as `_ >: _$1`. (SLS 3.2.10)

I have not been able to find any simple way around this. Forgive my ignorance, but why would these 'helper' types like GenSet be declared invariant?

Am I missing something (very likely) or is this somehow a weakness of Scala's marvelous collections framework (very unlikely, I think)?

Answer 1

This was a conscious design decision to make Set.contains/apply typesafe. You should not be able to have a s:Set[Int] and accidentally do something like s.contains("x") which would always be false so probably not what you intended. Also, Set[T] implements Function[T,Boolean], which is only possible if the apply method does not take an Any.

There were endless discussions about this topic on the scala-user mailing list. See for example this or this.

Here is a quote from Paul Phillips from the second discussion that summarizes the rationale very well:

"Yes, apply (aliased to contains) is the central operation of Set, whereas contains is indeed "just some method" on Seq.

Nobody's saying you don't sometimes want a covariant Set, but on balance, it is more useful invariant."

Note that you can always add covariance to sets with an implicit conversion. This means that if you have e.g. a Set[Int] and a method that takes a Set[Any], it will work. But it also means that you can now accidentally call Set[Int].contains("x"), and the compiler will not catch the error (you will always get false).

scala> implicit def setIsCovariant[T,U <: T](s:Set[U]):Set[T] = s.asInstanceOf[Set[T]]
setIsCovariant: [T, U <: T](s: Set[U])Set[T]

scala> val s : Set[Int] = Set(1,2,3,4)
s: Set[Int] = Set(1, 2, 3, 4)

scala> s.contains("x")
res0: Boolean = false

scala> val a: Set[Any] = s
a: Set[Any] = Set(1, 2, 3, 4)