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?

Venal

I removed my answer (it's wrong). I also found that if you remove the explicit return type from your example it compiles and runs. If it had been a case of C++ pre C++17 (with compile-time generics, but without compile-time if) I would have told that the method body is not correct for any type T, as T is never both Int and Boolean. – Emprise

@Emprise that's cos it infers a return type of AnyVal – Tigress

your function as is is just def f1[T](e: T) = e. If you want a solution, context would be helpful. Though perhaps you're just after a why – Tigress

@JoelBerkeley The question is mainly theoretical than practical. I'm trying to understand compilation logic. – Venal

@JoelBerkeley how about { case i: Int => i+1; case b: Boolean => !b}? :D – Yamada

@Yamada yes - in which the compiler error doesn't mention i.type, but Int - so we can surmise that singleton types aren't the cause – Tigress

This seems to be dependent on the pattern being a value pattern or a type pattern. This fails as well case class Expr[T](v: T); def eval[T](e: Expr[T]): T = e match { case Expr(i: Int) => i; case Expr(b: Boolean) => b } – Greff

I think it depends on the constraints and the fact that the compiler should be able to prove that your function is able to return the same type for all inputs. Hopefully someone answers but in the meantime this might be helpful: users.scala-lang.org/t/… – Greff

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.

Silversmith

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)

Roaster

He matches e, which is of type T. Consider the second example in the question, case IntExpr(i) => i does compile, while case i: Int => i does not. The question is what is the difference – Yamada

"Your function has no evidence" - do you mean the compiler can't work it out? After all, the evidence is there, in the match cases (granted perhaps you'd need an exhaustive match with case e => e). It would be a shame to have to lose type-checking on calls to f1 with Any. – Tigress

Int an Boolean have a common supertype, namely AnyVal. The compiler could infer T to be AnyVal – Participate

@Tigress Yes, the problem is in the return type of the function. I tried to offer a solution to your issue. – Roaster

@Participate if it did that, anytime you have type issues, it would fall back to AnyVal: I like types to catch errors early, not sure this would help – Roaster

@Tigress fair enough, tried to adjust the answer accordingly – Roaster

"You can't just return type T dynamically due to type erasure". This is not true. The second example in the question does exactly that. – Yamada

True - long day T_T. Fixed. – Roaster

@Esardes thanks for your answer. Especially for the link to scala spec. It did answer my question. – Venal

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

Fideliafidelio