Is PartialFunction orElse looser on its type bounds than it should be?

Question

Let's define a PartialFunction[String, String] and a PartialFunction[Any, String]

Now, given the definition of orElse

def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]): PartialFunction[A1, B1] 

I would expect not to be able to compose the the two, since

A → String
A1 → Any

and therefore the bound A1 <: A (i.e. Any <: String) doesn't hold.

Unexpectedly, I can compose them and obtain a PartialFunction[String, String] defined on the whole String domain. Here's an example:

val a: PartialFunction[String, String] = { case "someString" => "some other string" }
// a: PartialFunction[String,String] = <function1>

val b: PartialFunction[Any, String] = { case _ => "default" }
// b: PartialFunction[Any,String] = <function1>

val c = a orElse b
// c: PartialFunction[String,String] = <function1>

c("someString")
// res4: String = some other string

c("foo")
// res5: String = default

c(42)
// error: type mismatch;
//   found   : Int(42)
//   required: String

Moreover, if I explicitly provide the orElse type parameters

a orElse[Any, String] b
// error: type arguments [Any,String] do not conform to method orElse's type parameter bounds [A1 <: String,B1 >: String]

the compiler finally shows some sense.

Is there any type system sorcery I'm missing that causes b to be a valid argument for orElse? In other words, how come that A1 is inferred as String?

If the compiler infers A1 from b then it must be Any, so where else does the inference chain that leads to String start?

---

Update

After playing with the REPL I noticed that orElse returns an intersection type A with A1 when the types don't match. Example:

val a: PartialFunction[String, String] = { case "someString" => "some other string" }
// a: PartialFunction[String,String] = <function1>

val b: PartialFunction[Int, Int] = { case 42 => 32 }
// b: PartialFunction[Int,Int] = <function1>

a orElse b
// res0: PartialFunction[String with Int, Any] = <function1>

Since (String with Int) <:< String this works, even though the resulting function is practically unusable. I also suspect that String with Any is unified into Any, given that

import reflect.runtime.universe._
// import reflect.runtime.universe._   

typeOf[String] <:< typeOf[String with Any]
// res1: Boolean = true

typeOf[String with Any] <:< typeOf[String]
// res2: Boolean = true

So that's why mixing String and Any results into String.

That being said, what is going on under the hood? Under which logic are the mismatching types unified?

Update 2

I've reduced the issue to a more general form:

class Foo[-A] {
  def foo[B <: A](f: Foo[B]): Foo[B] = f
}

val a = new Foo[Any]
val b = new Foo[String]

a.foo(b) // Foo[String] Ok, String <:< Any
b.foo(a) // Foo[String] Shouldn't compile! Any <:!< String
b.foo[Any](a) // error: type arguments [Any] do not conform to method foo's type parameter bounds [A <: String]

Answer 1

You're getting this upside down.

You can always pass to a method requiring a parameter of type A any argument of type B <: A, i.e. any subtype of A. That is if you have

def foo(a: Animal)

you can pass a Dog to foo, because Dog <: Animal.

In the same way, if you have

def foo(l: List[Animal])

you can pass a List[Dog] to it, because List is covariant with its type parameter and since Dog <: Animal, then List[Dog] <: List[Animal]

Now if you have

def foo(pf: PartialFunction[String, String])

you can pass a PartialFunction[Any, String], because PartialFunction is contravariant with the first type parameter and covariant with the second. Since Any >: String, then PartialFuncion[Any, String] <: PartialFunction[String, String].

Now, for the type bounds, the compiler will try to infer A1 and B1, such that

• A1 is subtype of A
• B2 is subtype of B

To do so, it will look for:

• the greatest common subtype of Any and String, since A and A1 are in contravariant position
• the least common supertype of String and String, since B and B1 is covariant position

Results

• A1 → String
• B1 → String

---

The case in which you compose a PartialFunction[String, String] with a PartialFunction[Int, Int] is an odd-looking case of the previous example, in which:

• the greatest common subtype of String and Int is String with Int, i.e. the interesection of the two types, which is subtype of both (in this case is pretty much as saying Nothing: being both a String and an Int doesn't seem very likely)
• the least common supertype of String and Int is Any

therefore

val a: PartialFunction[String, String] = ...
val b: PartialFunction[Int, Int] = ...
a orElse b // PartialFunction[String with Int, Any] // as expected, although not very useful...

Answer 2

I was going to say that PartialFunction[Any, String] is a subtype of PartialFunction[String, String] because of contra-variance if I understand correctly. This would explain the behavior described in your question before the update, but you got me all mixed up with this union type stuff.

I don't even know what the hell String with Int means!

Answer 3

This is of course vague and only my humble opinion. Suggestions and comments are appreciated.

Taking from this SO question. (How to know if an object is an instance of a TypeTag's type?)

import scala.reflect.runtime.universe._
implicit class MyInstanceOf[U: TypeTag](that: U) {
  def myIsInstanceOf[T: TypeTag] = 
    typeOf[U] <:< typeOf[T]
}

We have a proper way to check isInstanceOf without erasure.

val b: PartialFunction[Any, String] = { case _ => "default" }
b.myIsInstanceOf[PartialFunction[String, String]] //true

And it only makes sense. If you have a function from Any => String, then it accepts any input. So it also accepts String input. That's why it can also be treated as a Function from String => String. Basically it can be treated as T => String for any T.

So in the end the compiler agrees on A -> String and A1 -> String.

 a.orElse[String,String](b) //works

Edit: Final thoughts

You should not think of A1 <: A as a restriction. It will only infer the type of the resulting PartialFunction. There is no way that orElse cannot be applied. Both PF involved are contra-variant on A and therefore a common subtype for BOTH can always be found that satisfies A1 <: A.

I think an analogy would be addition of fractions, where you think, oh, they have not a common denominator and therefore can not be added. Both fractions can be adjusted (or: seen differently) to have a common denominator. The compiler although wants to find the smallest common denominator and not resort to the easy way with multiplying with the other denominator. (A with A')

For the other type B it's the same. Both are co-variant and therefore a common super type can also always be found. Any in the worst case.

Answer 4

You already typed this in, but:

scala> val a: PartialFunction[String, String] = { case "a" => "b" }
a: PartialFunction[String,String] = <function1>

scala> val b: PartialFunction[Any, String] = { case 1 => "one" }
b: PartialFunction[Any,String] = <function1>

scala> a orElse b
res0: PartialFunction[String,String] = <function1>

scala> a orElse[String,String] b
res1: PartialFunction[String,String] = <function1>

scala> a orElse[Any,String] b
<console>:10: error: type arguments [Any,String] do not conform to method orElse's type parameter bounds [A1 <: String,B1 >: String]
              a orElse[Any,String] b
              ^

scala> import reflect.runtime._ ; import universe._
import reflect.runtime._
import universe._

scala> typeOf[PartialFunction[Any,String]] <:< typeOf[PartialFunction[String,String]]
res3: Boolean = true

Because of the contravariant type param, you can use PF[Any, String] here.

To answer the question, where does it say what it will pick?

http://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html#local-type-inference

E.g., it promises to infer a maximal A1 in contravariant position, but still conforming to the constraint <: A.