Search code examples
scalasetcovariancescala-collections

Why is Scala's immutable Set not covariant in its type?

EDIT: Re-written this question based on original answer

The scala.collection.immutable.Set class is not covariant in its type parameter. Why is this? 

import scala.collection.immutable._

def foo(s: Set[CharSequence]): Unit = {
    println(s)
}

def bar(): Unit = {
   val s: Set[String] = Set("Hello", "World");
   foo(s); //DOES NOT COMPILE, regardless of whether type is declared 
           //explicitly in the val s declaration
}
Solution

  • Set is invariant in its type parameter because of the concept behind sets as functions. The following signatures should clarify things slightly:

    trait Set[A] extends (A=>Boolean) {
  def apply(e: A): Boolean
}

    If Set were covariant in A, the apply method would be unable to take a parameter of type A due to the contravariance of functions. Set could potentially be contravariant in A, but this too causes issues when you want to do things like this:

    def elements: Iterable[A]

    In short, the best solution is to keep things invariant, even for the immutable data structure. You'll notice that immutable.Map is also invariant in one of its type parameters.