how does scala's type check work in this case? [closed]

Question

// Start writing your ScalaFiddle code here
sealed trait DSL[A]{
  // def run(): A ={
  //   this match {
  //     case GetLength(something) =>
  //       something.length
  //     case ShowResult(number) =>
  //       s"the length is $number"
  //   }
  // }
}

case class GetLength(something: String) extends DSL[Int]
case class ShowResult(number: Int) extends DSL[String]

def run[A](fa:DSL[A]): A ={
  fa match {
    case GetLength(something) =>
      something.length
    case ShowResult(number) =>
      s"the length is $number"
  }
}

val dslGetLength = GetLength("123456789")
val length = run(dslGetLength)
val dslShowResult = ShowResult(length)
println(run(dslShowResult))
// print: the length is 9

scalafiddle here

• why does the run function not compile in the DSL[A] trait, but worked outside?
• how does type inference work in this case?

Answer 1

This is a case of generalized abstract data type.

When you have a DSL[A] and function returning A, compiler can prove that:

• for case GetLength A=Int so you can return Int there
• for case ShowResult A=String so you can return String

however, Scala 2 is known to not have a perfect support of GADTs, so sometimes compiler fails, even if it should work. I guess some compiler dev could figure out the exact case, but, interestingly, it can be worked around with:

sealed trait DSL[A]{
  def run(): A = DSL.run(this)
}
object DSL {
  def run[A](fa:DSL[A]): A ={
    fa match {
      case GetLength(something) =>
        something.length
      case ShowResult(number) =>
        s"the length is $number"
    }
  }
}

case class GetLength(something: String) extends DSL[Int]
case class ShowResult(number: Int) extends DSL[String]

My wild guess would be that pattern matching in a generic method is kind of a special case in a compiler, which is not triggered when A is fixed. I think that, because the following code also works:

sealed trait DSL[A]{
  def run(): A = runMe(this)
  private def runMe[B](dsl: DSL[B]): B = {
    dsl match {
      case GetLength(something) =>
        something.length
      case ShowResult(number) =>
        s"the length is $number"
    }
  }
}

whereas this fails as well:

sealed trait DSL[A]{
  def run(): A = {
    val fa: DSL[A] = this // make sure error is not related to special treatment of "this", this.type, etc
    fa match {
      case GetLength(something) =>
        something.length
      case ShowResult(number) =>
        s"the length is $number"
    }
  }
}

cmd4.sc:5: constructor cannot be instantiated to expected type;
 found   : ammonite.$sess.cmd4.GetLength
 required: ammonite.$sess.cmd4.DSL[A]
      case GetLength(something) =>
           ^
cmd4.sc:7: constructor cannot be instantiated to expected type;
 found   : ammonite.$sess.cmd4.ShowResult
 required: ammonite.$sess.cmd4.DSL[A]
      case ShowResult(number) =>
           ^
Compilation Failed

In other words, I suspect that type parameter change how things are being evaluated:

• def runMe[B](dsl: DSL[B]): B has a type parameter, so results of each case inside match are compared against B where for each case value of B can be proven to be some specific type (Int, String)
• in def run: A however compiler is somehow prevented from making such analysis - IMHO it is a bug, but perhaps it is a result of some obscure feature.

From what I see the same error occurs in Dotty, so it is either duplicated bug or a limitation of a type-level checker (after all GADT aren't widely use din Scala, yet) - I would suggest reporting issue to Scala/Dotty team and letting them decide what it is.

Answer 2

Pattern matching seems to work differently depending on if type parameter comes from the enclosing method versus enclosing class. Here is a simplified example where using class type parameter A

trait Base[T]
case class Derived(v: Int) extends Base[Int]

class Test[A] {
  def method(arg: Base[A]) = {
    arg match {
      case Derived(_) => 42
    }
  }
}

raises error

Error:(7, 12) constructor cannot be instantiated to expected type;
 found   : A$A87.this.Derived
 required: A$A87.this.Base[A]
      case Derived(_) => 42
           ^

whilst it works using method type parameter A

class Test {
  def method[A](arg: Base[A]) = {
    arg match {
      case Derived(_) => 42
    }
  }
}

SLS 8.4: Pattern Matching Expressions seems to explain what happens in the method scenario

Let 𝑇 be the type of the selector expression 𝑒 and let 𝑎1,…,𝑎𝑚 be the type parameters of all methods enclosing the pattern matching expression. For every 𝑎𝑖, let 𝐿𝑖 be its lower bound and 𝑈𝑖 be its higher bound. Every pattern 𝑝∈𝑝1,,…,𝑝𝑛 can be typed in two ways. First, it is attempted to type 𝑝 with 𝑇 as its expected type. If this fails, 𝑝 is instead typed with a modified expected type 𝑇′ which results from 𝑇 by replacing every occurrence of a type parameter 𝑎𝑖 by undefined.

AFAIU, we have

e = arg
a1 = A
T = Base[A]
p1 = Derived(_) 

First, it attempts to type 𝑝 with 𝑇 as its expected type, however Derived does not conform to Base[A]. Thus it attempts the second rule

If this fails, 𝑝 is instead typed with a modified expected type 𝑇′ which results from 𝑇 by replacing every occurrence of a type parameter 𝑎𝑖 by undefined.

Assuming undefined means something like existential type, then we have T' = Base[_], and because the following indeed holds

implicitly[Derived <:< Base[_]]

then pattern matching in the case of method type parameter becomes something like

class Test {
  def method[A](arg: Base[A]) = {
    (arg: Base[_]) match {
      case Derived(_) => 42
    }
  }
}

which indeed compiles. This seems to be confirmed by making the class type parameter case successfully compile like so

class Test[A] {
  def method(arg: Base[A]) = {
    (arg: Base[_]) match {
      case Derived(_) => 42
    }
  }
}

Therefore it seems the second rule is not attempted in type parameter inference for constructor patterns when type parameter comes from enclosing class.

---

^{At least these seems to be some of the moving pieces which hopefully someone with actual knowledge can assemble into coherent explanation, as I am mostly guessing.}

Answer 3

run returns a generic A, but this only works in the case you didn't comment because you're accepting A as a type parameter (which the compiler can figure out).

The following would work instead:

sealed trait DSL[A] {
  def run(): A
}

case class GetLength(something: String) extends DSL[Int] {
  def run(): Int = something.length
}
case class ShowResult(number: Int) extends DSL[String] {
  def run(): String = s"the length is $number"
}

val dslGetLength = GetLength("123456789")
val length = dslGetLength.run()
val dslShowResult = ShowResult(length)
println(dslShowResult.run())

You can play around with this code here on Scastie or alternatively on Scala Fiddle.