Weird behavior of & function in Set

Question

Set is defined as Set[A]. It takes a in-variant parameter. Doing below works as expected as we are passing co-variant argument:

scala> val a = Set(new Object)
a: scala.collection.immutable.Set[Object] = Set(java.lang.Object@118c38f)

scala> val b = Set("hi")
b: scala.collection.immutable.Set[String] = Set(hi)

scala> a & b
<console>:10: error: type mismatch;
 found   : scala.collection.immutable.Set[String]
 required: scala.collection.GenSet[Object]
Note: String <: Object, but trait GenSet is invariant in type A.
You may wish to investigate a wildcard type such as `_ <: Object`. (SLS 3.2.10)
              a & b

But the below works:

scala> Set(new Object) & Set("hi")
res1: scala.collection.immutable.Set[Object] = Set()

Above as I see it, the scala compiler converts Set("hi") to Set[Object] type and hence works.

What is the type-inference doing here? Can someone please link to specification explaining the behavior and when does it happen in general? Shouldn't it be throwing a compile time error for such cases? As 2 different output for the same operation type.

Answer 1

Not sure, but I think what you're looking for is described in the language spec under "Local Type Inference" (at this time of writing, section 6.26.4 on page 100).

Local type inference infers type arguments to be passed to expressions of polymorphic type. Say e is of type [ a₁ >: L₁ <: U₁, ..., a_n >: Ln <: U_n ] T and no explicit type parameters are given.

Local type inference converts this expression to a type application e [ T₁, ..., T_n ]. The choice of the type arguments T₁, ..., T_n depends on the context in which the expression appears and on the expected type pt. There are three cases.

[ ... ]

If the expression e appears as a value without being applied to value arguments, the type arguments are inferred by solving a constraint system which relates the expression's type T with the expected type pt. Without loss of generality we can assume that T is a value type; if it is a method type we apply eta-expansion to convert it to a function type. Solving means finding a substitution σ of types T_i for the type parameters a_i such that

• None of inferred types T_i is a singleton type

• All type parameter bounds are respected, i.e. σ L_i <: σ a_i and σ a_i <: σ U_i for i = 1, ..., n.

• The expression's type conforms to the expected type, i.e. σ T <: σ pt.

It is a compile time error if no such substitution exists. If several substitutions exist, local-type inference will choose for each type variable a_i a minimal or maximal type T_i of the solution space. A maximal type T_i will be chosen if the type parameter a_i appears contravariantly in the type T of the expression. A minimal type T_i will be chosen in all other situations, i.e. if the variable appears covariantly, nonvariantly or not at all in the type T. We call such a substitution an optimal solution of the given constraint system for the type T.

In short: Scalac has to choose values for the generic types that you omitted, and it picks the most specific choices possible, under the constraint that the result compiles.

Answer 2

The expression Set("hi") can be either a scala.collection.immutable.Set[String] or a scala.collection.immutable.Set[Object], depending on what the context requires. (A String is a valid Object, of course.) When you write this:

Set(new Object) & Set("hi")

the context requires Set[Object], so that's the type that's inferred; but when you write this:

val b = Set("hi")

the context doesn't specify, so the more-specific type Set[String] is chosen, which (as you expected) then makes a & b be ill-typed.