Intersect Scala set with set of subtype

Question

Why doesn't this function compile?

case class MyType(n: Int)
def intersection(s1: Set[MyType], s2: Set[_ <: MyType]) =
  (s1 & s2)

I get the following error:

error: type mismatch; found : Set[_$1] where type _$1 <: MyType required: scala.collection.GenSet[MyType] Note: _$1 <: MyType, but trait GenSet is invariant in type A. You may wish to investigate a wildcard type such as _ <: MyType. (SLS 3.2.10) (w & r)

Is there a simple way to "promote" the second argument to type Set[MyType] without using asInstanceOf?

Answer 1

This is because Set is defined as Set[A]. It is in-variant and not co-variant.

& is defined as

def &(that: GenSet[A]): Set[A]

It expects and argument of type Set[A]. But you are instead providing Set[_ <: MyType].

Set[_ <: Mytype] is co-variant to Set[MyType]. But as the declaration says that the argument should be in-variant i.e. Set[MyType], hence the error.

PS: You can think of co-variance as type converting from narrow to broader. For ex: if Dog extends Animal and if you do Animal a = new Dog(), you have a Dog (narrow) converting to Animal (broader). Above it expects invariant type. i.e. if it expects Animal, you can only provide an Animal only. Another example is java.util.ArrayList which is in-variant.

Answer 2

A Set is not covariant on its type parameter.

So a simple solution is to convert to List (which is covariant):

def intersection(s1: Set[MyType], s2: Set[_ <: MyType]) =
    s1.toList.intersect(s2.toList).toSet

Answer 3

Set is invariant, however there is a surprisingly simple workaround:

def intersection(s1: Set[MyType], s2: Set[_ <: MyType]) =
  s2 filter s1

Or, if one wants to get better type inference for the result type:

def intersection[X <: MyType](s1: Set[MyType], s2: Set[X]): Set[X] =
  s2 filter s1

Here s1 is used as a function. Functions are contra-variant in arguments, therefore s1.apply of type (MyType) => Boolean is acceptable as (_ <: MyType) => Boolean.

Performance is the same as intersect, as this filter that is how is intersect implemented for Set.