Type inference fails on Set made with .toSet?

Question

Why is type inference failing here?

scala> val xs = List(1, 2, 3, 3)
xs: List[Int] = List(1, 2, 3, 3)

scala> xs.toSet map(_*2)
<console>:9: error: missing parameter type for expanded function ((x$1) => x$1.$times(2))
       xs.toSet map(_*2)

However, if xs.toSet is assigned, it compiles.

scala> xs.toSet
res42: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> res42 map (_*2)
res43: scala.collection.immutable.Set[Int] = Set(2, 4, 6)

Also, going the other way, converting to Set from List, and mapping on List complies.

scala> Set(5, 6, 7)
res44: scala.collection.immutable.Set[Int] = Set(5, 6, 7)

scala> res44.toList map(_*2)
res45: List[Int] = List(10, 12, 14)

Answer 1

Q: Why doesn't toSet do what I want?

A: That would be too easy.

Q: But why doesn't this compile? List(1).toSet.map(x => ...)

A: The Scala compiler is unable to infer that x is an Int.

Q: What, is it stupid?

A: Well, List[A].toSet doesn't return an immutable.Set[A]. It returns an immutable.Set[B] for some unknown B >: A.

Q: How was I supposed to know that?

A: From the Scaladoc.

Q: But why is toSet defined that way?

A: You might be assuming immutable.Set is covariant, but it isn't. It's invariant. And the return type of toSet is in covariant position, so the return type can't be allowed to be invariant.

Q: What do you mean, "covariant position"?

A: Let me Wikipedia that for you: http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) . See also chapter 19 of Odersky, Venners & Spoon.

Q: I understand now. But why is immutable.Set invariant?

A: Let me Stack Overflow that for you: Why is Scala's immutable Set not covariant in its type?

Q: I surrender. How do I fix my original code?

A: This works: List(1).toSet[Int].map(x => ...). So does this: List(1).toSet.map((x: Int) => ...)

(with apologies to Friedman & Felleisen. thx to paulp & ijuma for assistance)

EDIT: There is valuable additional information in Adriaan's answer and in the discussion in the comments both there and here.

Answer 2

The type inference does not work properly as the signature of List#toSet is

def toSet[B >: A] => scala.collection.immutable.Set[B]

and the compiler would need to infer the types in two places in your call. An alternative to annotating the parameter in your function would be to invoke toSet with an explicit type argument:

xs.toSet[Int] map (_*2)

UPDATE:

Regarding your question why the compiler can infer it in two steps, let's just look at what happens when you type the lines one by one:

scala> val xs = List(1,2,3)
xs: List[Int] = List(1, 2, 3)

scala> val ys = xs.toSet   
ys: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

Here the compiler will infer the most specific type for ys which is Set[Int] in this case. This type is known now, so the type of the function passed to map can be inferred.

If you filled in all possible type parameters in your example the call would be written as:

xs.toSet[Int].map[Int,Set[Int]](_*2)

where the second type parameter is used to specify the type of the returned collection (for details look at how Scala collections are implemented). This means I even underestimated the number of types the compiler has to infer.

In this case it may seem easy to infer Int but there are cases where it is not (given the other features of Scala like implicit conversions, singleton types, traits as mixins etc.). I don't say it cannot be done - it's just that the Scala compiler does not do it.

Answer 3

I agree it would be nice to infer "the only possible" type, even when calls are chained, but there are technical limitations.

You can think of inference as a breadth-first sweep over the expression, collecting constraints (which arise from subtype bounds and required implicit arguments) on type variables, followed by solving those constraints. This approach allows, e.g., implicits to guide type inference. In your example, even though there is a single solution if you only look at the xs.toSet subexpression, later chained calls could introduce constraints that make the system unsatisfiable. The downside of leaving the type variables unsolved is that type inference for closures requires the target type to be known, and will thus fail (it needs something concrete to go on -- the required type of the closure and the type of its argument types must not both be unknown).

Now, when delaying solving the constraints makes inference fail, we could backtrack, solve all the type variables, and retry, but this is tricky to implement (and probably quite inefficient).