Type inference and pattern maching in Scala

Question

This doesn't type:

sealed trait BinOp[-InA, -InB, +Out]
case object Add extends BinOp[Int, Int, Int]

sealed trait Expression[+A]
final case class IntegerAtom(value: Int) extends Expression[Int]
final case class BinaryExp[-A, -B, +C](op: BinOp[A, B, C], lhs: Expression[A], rhs: Expression[B]) extends Expression[C]

def optimizeStep[A](x: Expression[A]): Expression[A] = x match {
  case BinaryExp(Add, IntegerAtom(a), IntegerAtom(b)) => IntegerAtom(a + b)
}

The most immediate thing is the usage of a case object in pattern match:

[error] (...) pattern type is incompatible with expected type;
[error]  found   : minimumexample.Add.type
[error]  required: minimumexample.BinOp[Any,Any,A]

It seems that this can be solved by introducing the eye-bleeding:

val AddOp = Add

And then:

case BinaryExp(AddOp, IntegerAtom(a), IntegerAtom(b)) => IntegerAtom(a + b)

But then:

[error] (...) type mismatch;
[error]  found   : minimumexample.IntegerAtom
[error]  required: minimumexample.Expression[A]
[error]     case BinaryExp(AddOp, IntegerAtom(a), IntegerAtom(b)) => IntegerAtom(a + b)
[error]                                                                         ^

I want to solve this as type-safely as possible, without resorting to .asInstanceOf[]. Thoughts?

Answer 1

The main issue with your code is a variance issue in the definition of BinaryExp, but that doesn't seem in scope of the question. Once you get the variance fixed, you're left with the only inconvenience that case object does not introduce a new type.

A typical pattern for solving this issue is to declare a sealed trait and then have a case object to extend it.

Here's an example that compiles

sealed trait BinOp[-InA, -InB, +Out]
sealed trait Add extends BinOp[Int, Int, Int]
case object Add extends Add

sealed trait Expression[+A]
final case class IntegerAtom(value: Int) extends Expression[Int]
final case class BinaryExp[A, B, C](op: BinOp[A, B, C], lhs: Expression[A], rhs: Expression[B]) extends Expression[C]

def optimizeStep[A](x: Expression[A]): Expression[A] = x match {
  case BinaryExp((_: Add), IntegerAtom(a), IntegerAtom(b)) => IntegerAtom(a + b)
}

where:

• the variance is "fixed" in a naive way (removing it)
• Add is now a type thanks to the sealed trait definition
• the match is performed with (_: Add)