type stable parametric polymorphism

Question

I don't understand why the following scala code doesn't compile:

sealed trait A
case class B() extends A {
  def funcB: B = this
}
case class C() extends A {
  def funcC: C = this
}
def f[T <: A](s:T): T = s match {
  case s: B => s.funcB
  case s: C => s.funcC
}

It works to replace f with

def f[T <: A](s:T): A = s match {
  case s: B => s.funcB
  case s: C => s.funcC
}

and then cast to the subtype when f is called, using asInstanceOf, for example. But I would like to be able to construct a function which unifies some previously defined methods, and have them be type stable. Can anyone please explain?

Also, note that the following f also compiles:

def f[T <: A](s:T): T = s match {
  case s: B => s
  case s: C => s
}

Answer 1

What makes it work?

In particular, in Scala 3 you could use match types

scala> type Foo[T <: A] = T match {
     |     case B => B
     |     case C => C
     | }
     |
     | def f[T <: A](s:T): Foo[T] = s match {
     |   case s: B => s.funcB
     |   case s: C => s.funcC
     | }
def f[T <: A](s: T): Foo[T]

scala> f(B())
val res0: B = B()

scala> f(C())
val res1: C = C()

In general, for the solution to "return current type" problems see Scala FAQ How can a method in a superclass return a value of the “current” type?

Compile-time techniques such as type classes and match types can be considered as kind of compile-time pattern matching which instruct the compiler to reduce to the most specific informationally rich type used at call site instead of otherwise having to determine a probably poorer upper bound type.

Why it does not work?

The key concept to understand is that parametric polymorphism is a kind of universal quantification which means it must make sense to the compiler for all instantiations of type parameters at call-sites. Consider typing specification

def f[T <: A](s: T): T

which the compiler might interpret something like so

For all types T that are a subtype of A, then f should return that particular subtype T.

hence the expression expr representing the body of f

def f[T <: A](s:T): T = expr

must type to that particular T. Now lets try to type our expr

s match {
  case s: B => s.funcB
  case s: C => s.funcC
}

The type of

case s: B => s.funcB

is B, and the type of

case s: C => s.funcC

is C. Given we have B and C, now compiler has to take the least upper bound of the two which is A. But A is certainly not always T. Hence the typecheck fails.

Now lets do the same exercise with

def f[T <: A](s: T): A

This specification means (and observe the "for all" again)

For all types T that are a subtype of A, then f should return their supertype A.

Now lets type the method body expressions

s match {
  case s: B => s.funcB
  case s: C => s.funcC
}

As before we arrive at types B and C, so compiler takes the upper bound which is the supertype A. And indeed this is the very return type we specified. So typecheck succeeds. However despite succeeding, at compile-time we lost some typing information as compiler will no longer consider all the information that comes with specific T passed in at call-site but only the information available via its supertype A. For example, if T has a member not existing in A, then we will not be able to call it.

What to avoid?

Regarding asInstanceOf, this is us telling the compiler to stop helping us because we will take the rains. Two groups of people tend to use it in Scala to make things work, the mad scientist library authors and ones transitioning from other more dynamically typed languages. However in most application level code it is considered bad practice.

Answer 2

To answer the question why it does not work. f returns the result of the statement s match {...}.

The type of that statement is A (sometimes it returns B, and sometimes it returns C), not T as it is supposed to be. T is sometimes C, and sometimes B, s match {...} is never either of those. It is the supertype of them, which is A.

Re. this:

 s match {
  case s: B => s
  case s: C => s
}

The type of this statement is obviously T, because s is T. It certainly does compile despite what @jwvh might be saying :)

Answer 3

It all comes down to our old friend (fiend?) the compile-time/run-time barrier. (And ne'er the twain shall meet.)

T is resolved at compile-time at the call site. When the compiler sees f(B) then T means B and when the compiler sees f(C) then T becomes C.

But match { case ... is resolved at run-time. The compiler can't know which case branch will be chosen. From the compiler's point of view all case options are equally likely. So if T is resolved to B but the code might take a C branch...well, the compiler can't allow that.

Looking at what does compile:

def f[T <: A](s:T): A = s match { //f() returns an A
  case s: B => s.funcB            //B is an A sub-type
  case s: C => s.funcC            //C is an A sub-type
}                                 //OK, all is good

Your 2nd "also works" example does not compile for me.