Why Type Check Error are not detected when Pattern Matching on Generic Type in Scala

Question

Defining the following structure:

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[A](head: A, tail: List[A]) extends List[A]

and the following function (please note that the second line which is the type check error spot is also an algorithmic mistake for short-circuiting the result, but nonetheless it came up and i wonder why type checking is not spotting it)

    def foldRight[A, B] (list: List[A], z: B)(f: (A,B) => B ): B = list match {
        case Nil => z
        case Cons(0, _) => z // problematic line
        case Cons(s, xs) => f(s, foldRight(xs, z) (f))
    }

I know scala also suffer from Type Erasure, but i am surprised that in this case, this can't be detected at compilation time ? Cons is Cons[A] in this case, and z is clearly of type B ?

Any reason why such code actually compile ?

EDIT1

Sounds like there is a lengthy explanation here https://gist.github.com/jkpl/5279ee05cca8cc1ec452fc26ace5b68b, but Long read. If someone could make it simpler :)

Answer 1

Why these or those decisions about language design were made is opinion based.

In Scala spec it's written:

https://scala-lang.org/files/archive/spec/2.13/08-pattern-matching.html#type-parameter-inference-for-constructor-patterns

8.3.2 Type parameter inference for constructor patterns

Assume a constructor pattern 𝐶(𝑝1,…,𝑝𝑛) where class 𝐶 has type parameters 𝑎1,…,𝑎𝑛. These type parameters are inferred in the same way as for the typed pattern (_: 𝐶[𝑎1,…,𝑎𝑛]).

So for pattern Cons(h, t) type parameter A in Cons[A](h, t) is inferred as if the pattern were _: Cons[A] (which becomes _: Cons[_] at runtime because of erasure).

There is example there in the spec how types are inferred for

class Term[A]
class Number(val n: Int) extends Term[Int]
def f[B](t: Term[B]): B = t match {
  case y: Number => y.n
}

It's explained there why for the pattern y: Number type parameter B (new type parameter B) is inferred Int.

Similarly, in our case for the pattern Cons(0, _) (as if it were _: Cons[A]) A is inferred Int.

After typer phase (scalacOptions ++= Seq("-Xprint:typer", "-Xprint-types")) the code becomes

def foldRight[A, B](list: App.List[A], z: B)(f: (A, B) => B): B = list{App.List[A]} match {
  case App.this{App.type}.Nil{App.Nil.type} => z{B}
  case (head: A, tail: App.List[A]): App.Cons[?A1](0{Int(0)}, _{App.List[A]}){App.Cons[?A1]} => z{B}
  case (head: A, tail: App.List[A]): App.Cons[?A2]((s @ _{A}){A}, (xs @ _{App.List[A]}){App.List[A]}){App.Cons[?A2]} => f.apply{(v1: A, v2: B): B}(s{A}, App.this{App.type}.foldRight{[A, B](list: App.List[A], z: B)(f: (A, B) => B): B}[A, B]{(list: App.List[A], z: B)(f: (A, B) => B): B}(xs{App.List[A]}, z{B}){(f: (A, B) => B): B}(f{(A, B) => B}){B}){B}
}{B}

and after erasure (scalacOptions += "-Xprint:erasure") it becomes

def foldRight(list: App$List, z: Object, f: Function2): Object = {
  <synthetic> var rc9: Boolean = false;
  <synthetic> <stable> var x2: App$Cons = (null: App$Cons);
  {
    case <synthetic> val x1: App$List = list;
    case11(){
      if (App$Nil.==(x1))
        matchEnd10(z)
      else
        case12()
    };
    case12(){
      if (x1.$isInstanceOf[App$Cons]())
        {
          rc9 = true;
          x2 = (x1.$asInstanceOf[App$Cons](): App$Cons);
          {
            <synthetic> val p3: Object = x2.head();
            if (scala.Int.box(0).==(p3))
              matchEnd10(z)
            else
              case13()
          }
        }
      else
        case13()
    };
    case13(){
      if (rc9)
        {
          val s: Object = x2.head();
          val xs: App$List = x2.tail();
          matchEnd10(f.apply(s, App.this.foldRight(xs, z, f)))
        }
      else
        case14()
    };
    case14(){
      matchEnd10(throw new MatchError(x1))
    };
    matchEnd10(x: Object){
      x
    }
  }
};

Actually, code similar to yours compiles even in Haskell if we add the information that a type parameter a belongs to type classes Eq and Num to the context of function signature

https://ideone.com/qqOsI2

data List a = Nil | Cons a (List a)
 
foldRight :: (Eq a, Num a) => List a -> b -> (a -> b -> b) -> b
foldRight list z f = case list of
  Nil -> z
  Cons 0 _ -> z
  Cons s xs -> f s (foldRight xs z f)

Type classes are not first-class citizens in Scala. So Scala can't request similar thing about something like Num (in Scala everything can be compared with ==, so Eq is "automatical").

Answer 2

Cons is Cons[A] in this case

This is not correct, or at very least it is confusing. There are two types A here: the type parameter in Cons[A] and the type parameter in foldRight[A,B]. There is nothing to say that they are the same type. You could equally well define

case class Cons[Z](head: Z, tail: List[Z]) extends List[Z]

So on the problematic line

case Cons(0, _) => z // problematic line

the compiler treats this as Cons[Int](0, _) because the type of head is Int. The compiler is promiscuous in this case and allows this match in all cases even though it can only succeed if foldLeft is called with a List[Int].