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?

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`. — bobah, Sep 24 '18 at 13:02
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 — joel, Sep 24 '18 at 13:11
@JoelBerkeley The question is mainly theoretical than practical. I'm trying to understand compilation logic. — Bogdan Vakulenko, Sep 24 '18 at 13:18
@JoelBerkeley how about `{ case i: Int => i+1; case b: Boolean => !b}`? :D — Dima, Sep 24 '18 at 13:53
@Dima yes - in which the compiler error doesn't mention i.type, but Int - so we can surmise that singleton types aren't the cause — joel, Sep 24 '18 at 13:57
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 }` — Nader Ghanbari, Sep 24 '18 at 13:57
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: https://users.scala-lang.org/t/dry-matching-generic-types-of-a-specific-type/1644 — Nader Ghanbari, Sep 24 '18 at 14:15

score 6 · Accepted Answer · answered Sep 24 '18 at 19:24

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.

John K · Answer 2 · 2020-06-19T14:42:07.523

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)

edited Jun 19 '20 at 14:42

answered Sep 24 '18 at 14:39

John K

1,285
6
18

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 – Dima Sep 24 '18 at 14:44
"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. – joel Sep 24 '18 at 14:45
Int an Boolean have a common supertype, namely `AnyVal`. The compiler could infer `T` to be `AnyVal` – fusion Sep 24 '18 at 14:55
@joel Yes, the problem is in the return type of the function. I tried to offer a solution to your issue. – John K Sep 24 '18 at 14:58
@fusion 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 – John K Sep 24 '18 at 14:58
@joel fair enough, tried to adjust the answer accordingly – John K Sep 24 '18 at 15:05
"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. – Dima Sep 24 '18 at 15:24
True - long day T_T. Fixed. – John K Sep 24 '18 at 15:42
@Esardes thanks for your answer. Especially for the link to scala spec. It did answer my question. – Bogdan Vakulenko Sep 24 '18 at 16:19

score 1 · Answer 3 · answered Sep 24 '18 at 16:31

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

Type mismatch on abstract type used in pattern matching

3 Answers3

Linked