Type mismatch on abstract type used in pattern matching

Question

This code compiles with an error:

def f1[T](e: T): T = e match {
  case i:Int => i
  case b:Boolean => b
}
// type mismatch;
// found   : i.type (with underlying type Int)
// required: T
// case i:Int => i ...

And this code implementing GADT looks pretty identical from type checking perspective, but compiles without error:

sealed trait Expr[T]
case class IntExpr(i: Int) extends Expr[Int]
case class BoolExpr(b: Boolean) extends Expr[Boolean]

def eval[T](e: Expr[T]): T = e match {
  case IntExpr(i) => i
  case BoolExpr(b) => b
}

In both cases inside pattern matching expression we know that i and b are Int and Boolean. Why compilation failed on first example and succeeded on the second one?

Answer 1

The first case is unsound because you underestimate the variety of types in Scala type system. It would make sense if, when we took case i:Int branch we knew T was Int, or at least a supertype of Int. But it doesn't have to be! E.g. it could be 42.type or a tagged type.

There's no such problem in the second case, because from IntExpr <: Expr[T], the compiler does know T must be exactly Int.

Answer 2

You ask of your function to return a type T, then you pattern-match against Int and Boolean. Except your function has no evidence that Int and Boolean are also of type T: when you pattern-match, you introduce the constraint that Int <: T and Boolean <: T. You could either replace the return type T by a fixed type like String and return a String, or introduce a constraint that will satisfy both the case Int and Boolean.

//this compiles
def f1[T](e: T ): String = e match {
  case _:Int => "integer"
  case _:Boolean => "boolean"
}

//this compiles too, but will return AnyVal
def f1[T >: AnyVal](e: T ): T = e match {
   case i:Int => i
   case b:Boolean => b
}

Basically you can't just return any type T dynamically because you need to prove at compile time that your function type-checks out.

The other function in your example avoids the issue by encapsulating type constraints within case classes IntExpr <: Expr[Int] and BoolExpr <: Expr[Boolean] (notice how Expr[_] would be the equivalent of T in the constraints I mentioned above). At compile time, T is properly identified in all cases (e.g in the IntExpr you know it's an Int)

Answer 3

In addition to @Esardes answer, this worked by defining a type bound for T:

scala> def f1[T >: AnyVal](e: T):T = e match {
     |   case i:Int => i
     |   case b:Boolean => b
     | }
f1: [T >: AnyVal](e: T)T

scala> f1(1)
res3: AnyVal = 1

scala> f1(true)
res4: AnyVal = true