Why does scala fail to compile when method is overloaded in a seemingly unrelated way?

Question

class A {}
class B extends A {}

object Sample {
  def foo(a: Set[A]) {
    println("Hi Set[A]")
  }
  // def foo(a: String) {
  //   println("Hi A")
  // }
}

Sample.foo(Set(new B()))

The above code runs happily with scala. However, when I uncomment foo(a: String), the code fails to compile:

test.scala:13: error: overloaded method value foo with alternatives:
  (a: String)Unit <and>
  (a: Set[this.A])Unit
 cannot be applied to (scala.collection.immutable.Set[this.B])
Sample.foo(Set(new B()))
       ^
one error found

foo(a: String) seems like it should have nothing to do with trying to call foo with a Set[B]. What is going on?

EDIT:

The thing that confuses me isn't just why the uncommented version doesn't compile, but also why it does compile, when foo(a: String) is commented out. What am I changing by adding the method foo(a: String)?

Set being invariant doesn't explain why it compiles successfully when foo(a: String) is commented out.

Answer 1

Actually... the true answer of this question was hidden away in @pamu's answer. The answer to this is bit non-trivial and will take a lot of explaining.

Let us first consider op's first case which compiles,

class A {}
class B extends A {}

object Sample {
  def foo(a: Set[A]) {
    println("Hi Set[A]")
  }
}

Sample.foo(Set(new B()))

But why did it compile ? Well... the answer lies in the fact that Scala-compiler is a very intelligent creature and has the capability of type-inference. This means that if the type is not explicitly provided Scala tries to guess the type which user probably wanted by looking at the available information and the treats it as most suitable (closest fit) type.

Now, in Sample.foo(Set(new B())), Scala finds that the foo takes a Set[A] as a parameter. It looks at provided parameter Set(new B()) which looks more like a Set[B]... but how can the Scala-compiler's master "the programmer" can make a mistake. So it checks if it can actually infer it as a Set[A]. And it succeeds. Scala compiler is happy and proud that it is intelligent enough to understand it's master's profound intentions.

The Scala specification section 6.26.1 refers to this as Type Instantiation.

To explain it even more clearly... let me show what happens when you tell Scala types explicitly and Scala does not need to use any of its inference intelligence.

// tell scala that it is a set of A
// and we all know that any set of A can contain B
scala> val setA: Set[A] = Set(new B())
setA: scala.collection.immutable.Set[A] = Set(B@17ae2a19)

// Scala is happy with a Set[A]
scala> Sample.foo(setA)
// Hi Set[A]

// tell scala that it is a set of B
// and we all know that any set of B can contain B
scala> val setB: Set[B] = Set(new B())
// setB: scala.collection.immutable.Set[B] = Set(B@17ae2a19)

// But Scala knows that Sample.foo needs a Set[A] and not Set[B]
scala> Sample.foo(setB)
// <console>:20: error: type mismatch;
//  found   : scala.collection.immutable.Set[B]
//  required: Set[A]
// Note: B <: A, but trait Set is invariant in type A.
You may wish to investigate a wildcard type such as `_ <: A`. (SLS 3.2.10)
//        Sample.foo(setB)
              ^

Now that we know why first case worked for OP. Lets move on to the second case.

class A {}
class B extends A {}

object Sample {
  def foo(a: Set[A]) {
    println("Hi Set[A]")
  }
  def foo(a: String) {
    println("Hi A")
  }
}

Sample.foo(Set(new B()))

Now... all of a sudden Sample.foo(Set(new B())) does not compile.

The reason is again hidden in the "intelligence" of Scala compiler. Scala compiler now see's two Sample.foos. First wants a Set[A] and other wants a String. How should Scala go around deciding which one the programmer intended. Looking at what is knows, Scala finds something that looks more like a Set[B].

Now as we discussed about Type Instantiation and inference, once scala knows what type to expect it can try to infer that type. But here Scala can not decide on what type to expect as it sees multiple choices. So before moving to type inference, it should deal with the problem of overloaded choice only then can it set its expectations for inference.

This is discussed in Overload Resolution ( Section 6.26.3) of Scala specification. The specification may look a little opaque so lets discuss how it tries to differentiate.

overload resolution is actually composed of two problems,

• Problem 1 :: Just considering the arguments provided, out of all alternatives which one's are more specifically applicable. In other words we look at Applicability of arguments on the alternatives available. Applicability is discussed in Section 6.6. Applicability first considers the shape of arguments provided and is heavily dependant on Compatibility and Conformance of each type parameter for further analysis.

• Problem 2 :: Now, Considering the type of reference to the method call, we try to decide which among the above selected alternatives are Compatible to it.

Now, we come to realise the importance of Compatibility which is discussed in detail in section 3.5.4. To give a brief idea, Compatibility of two given types (which are not functions) depends on the implicit views (implicit conversions between two types)

If you go through the rules of overload resolution... you will see that Scala compiler will fail to resolve the multiple choices problem for call Sample.foo(Set(new B())). And thus no inference could be done and that argument which looks most like a Set[B] is still treated as Set[B].

To put it in very in-accurate (is just for easier visualization of the actual problem explained above and is not supposed to be treated as accurate in any way) but simple explanation -> You all should be aware that other than type-inference Scala has another magical thing call implicit conversions with the help of those magical implicit type-class. Scala compiler now see's two Sample.foos. First wants a Set[A] and other wants a String. But what Scala has looks more like a Set[B]. Now it can either try to infer it as a Set[A] or try to implicitly convert it to a String.

Both of these choices look fairly reasonable to Scala and now this "intelligent" being is confused about what its noble master "the programmer" wanted. It dares not to make any mistake in its master's affairs and thus decides to tell the master about its confusion and ask for his wishes.

Now... how do we programmers help with its confusion... well we simply provide more information.

for example,

scala> Sample.foo(Set[A](new B()))
// Hi Set[A]

// Or for string

scala> Sample.foo(Set[A](new B()).toString)
// Hi A

// Or,

scala> val setA: Set[A] = Set(new B())
// setA: scala.collection.immutable.Set[A] = Set(B@17ae2a19)

scala> Sample.foo(setA)
// Hi Set[A]

// Or for string

scala> Sample.foo(setA.toString)
// Hi A

Answer 2

In the working case, the type param to Set.apply[T] is inferred to be A because Set[A] is the expected type of the function param.

Overloading resolution typechecks arguments without an expected type, so the compiler can no longer use Set[A] to guide inference of what set you intend.

That's an important take-away from the spec, though now it is a bit buried by more words about SAMs.

Otherwise, let Si... be the list of types obtained by typing each argument as follows. [Something about functions.] All other arguments are typed with an undefined expected type.

If it knows a Set[A] is expected, your set is typed that way, not as a Set[B].

You can observe typing decisions with -Ytyper-debug, which emits output that is occasionally not inscrutable.

Given

class A ; class B extends A

object X { def f(as: Set[A]) = ??? ; def f(s: String) = ??? }

object Main extends App {
  X.f(Set(new B))
}

Here, the value argument is typed as Set[B], and then it attempts and fails to find an implicit conversion to the param types of the overload.

It also looks for a conversion of the X object to a type with an f method that takes Set[B].

|    |-- X.f(Set(new B())) BYVALmode-EXPRmode (site: value <local Main> in Main)
|    |    |-- X.f BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |-- X EXPRmode-POLYmode-QUALmode (silent: value <local Main> in Main)
|    |    |    |    \-> X.type
|    |    |    \-> (s: String)Nothing <and> (as: Set[A])Nothing
|    |    |-- Set(new B()) BYVALmode-EXPRmode (silent: value <local Main> in Main)
|    |    |    |-- Set BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |-- scala.Predef.Set.apply BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |    [adapt] [A](elems: A*)CC[A] adapted to [A](elems: A*)CC[A]
|    |    |    |    |    \-> (elems: A*)scala.collection.immutable.Set[A]
|    |    |    |    [adapt] => scala.collection.immutable.Set.type adapted to [A](elems: A*)CC[A]
|    |    |    |    \-> (elems: A*)scala.collection.immutable.Set[A]
|    |    |    |-- new B() BYVALmode-EXPRmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |-- new B BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |    |-- new B EXPRmode-POLYmode-QUALmode (silent: value <local Main> in Main)
|    |    |    |    |    |    |-- B FUNmode-TYPEmode (silent: value <local Main> in Main)
|    |    |    |    |    |    |    \-> B
|    |    |    |    |    |    \-> B
|    |    |    |    |    \-> ()B
|    |    |    |    \-> B
|    |    |    solving for (A: ?A)
|    |    |    \-> scala.collection.immutable.Set[B]
|    |    [search #1] start `(s: String)Nothing <and> (as: Set[A])Nothing`, searching for adaptation to pt=scala.collection.immutable.Set[B] => String (silent: value <local Main> in Main) implicits disabled
|    |    15 implicits in companion scope
|    |    [search #2] start `(s: String)Nothing <and> (as: Set[A])Nothing`, searching for adaptation to pt=(=> scala.collection.immutable.Set[B]) => String (silent: value <local Main> in Main) implicits disabled
|    |    15 implicits in companion scope
|    |    [search #3] start `(s: String)Nothing <and> (as: Set[A])Nothing`, searching for adaptation to pt=scala.collection.immutable.Set[B] => Set[A] (silent: value <local Main> in Main) implicits disabled
|    |    15 implicits in companion scope
|    |    [search #4] start `(s: String)Nothing <and> (as: Set[A])Nothing`, searching for adaptation to pt=(=> scala.collection.immutable.Set[B]) => Set[A] (silent: value <local Main> in Main) implicits disabled
|    |    15 implicits in companion scope
|    |    second try: <error> and Set(new B())
|    |    |-- Set(new B()) EXPRmode (silent: value <local Main> in Main)
|    |    |    |-- Set BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |-- scala.Predef.Set.apply BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Main> in Main)
|    |    |    |    |    [adapt] [A](elems: A*)CC[A] adapted to [A](elems: A*)CC[A]
|    |    |    |    |    \-> (elems: A*)scala.collection.immutable.Set[A]
|    |    |    |    [adapt] => scala.collection.immutable.Set.type adapted to [A](elems: A*)CC[A]
|    |    |    |    \-> (elems: A*)scala.collection.immutable.Set[A]
|    |    |    solving for (A: ?A)
|    |    |    \-> scala.collection.immutable.Set[B]
|    |    [search #5] start `X.type`, searching for adaptation to pt=X.type => ?{def f(x$1: ? >: scala.collection.immutable.Set[B]): ?} (silent: value <local Main> in Main) implicits disabled
|    |    [search #6] start `X.type`, searching for adaptation to pt=(=> X.type) => ?{def f(x$1: ? >: scala.collection.immutable.Set[B]): ?} (silent: value <local Main> in Main) implicits disabled
badset.scala:7: error: overloaded method value f with alternatives:
  (s: String)Nothing <and>
  (as: Set[A])Nothing
 cannot be applied to (scala.collection.immutable.Set[B])