Find greatest common subtype of two Scala types

Question

Along the lines of this question, I am trying to find a way to get the Scala compiler to infer the greatest common subtype of two types A and B.

Something like "A without B", where the definition is:

(A without B = C) === (A = C with B)

Or a type function that returns C, where:

EDIT:

A <: C && C <:!< B

ie. A is a subtype of C and C is not a subtype of B

In fact I expect someone will point out that this is not the same as the "greatest common subtype", since I don't actually require that A <: B.

Usage:

trait Syntax

trait ANYSYNTAX extends Syntax
trait NUMERIC extends ANYSYNTAX
trait DISCRETE extends ANYSYNTAX
trait POSITIVE extends ANYSYNTAX
trait CONST extends ANYSYNTAX     
type NUMCONST = NUMERIC with CONST
type POSCONST = POSITIVE with CONST
type ORDINALCONST = DISCRETE with CONST
type INTEGER = NUMERIC with DISCRETE
type POSNUM = POSITIVE with NUMERIC
type POSINT = POSNUM with INTEGER
type INTCONST = INTEGER with NUMCONST with ORDINALCONST
type POSNUMCONST = POSNUM with POSCONST with NUMCONST
type POSINTCONST = POSNUMCONST with INTCONST with POSINT

Then I would like to be able to propagate type constraints, as follows:

abstract class Expression[+R]( val args: Expression[_]* )

case class Add[A <: R, R <: NUMERIC]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {
case class Subtract[A <: R, R : A without POSITIVE]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {
case class Multiply[A <: R, R <: NUMERIC]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R]{
case class Divide[A <: R, R : A without DISCRETE]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {

I've been trying to come up with something using some type constraints borrowed from other SO answers:

sealed class =!=[A,B]

trait LowerPriorityImplicits {
  implicit def equal[A]: =!=[A, A] = sys.error("should not be called")
}
object =!= extends LowerPriorityImplicits {
  implicit def nequal[A,B](implicit same: A =:= B = null): =!=[A,B] =
    if (same != null) sys.error("should not be called explicitly with same type")
    else new =!=[A,B]
}

// Encoding for "A is not a subtype of B"
trait <:!<[A, B]

// Uses ambiguity to rule out the cases we're trying to exclude
implicit def nsub[A, B] : A <:!< B = null
implicit def nsubAmbig1[A, B >: A] : A <:!< B = null
implicit def nsubAmbig2[A, B >: A] : A <:!< B = null

I have some test cases:

implicitly[POSINT <:!< CONST]
implicitly[POSITIVE <:!< OPINION]
implicitly[DOGMA <:!< CONST]

implicitly[POSINTCONST <:< POSITIVE with CONST]
implicitly[POSINTCONST <:< POSCONST]
implicitly[POSITIVE with CONST <:!< POSINTCONST]

implicitly[POSITIVE =:= POSCONST without CONST]
implicitly[NUMERIC =:= INTEGER without DISCRETE]
implicitly[POSINT =:= POSINTCONST without CONST]

These should fail:

implicitly[POSINT =:= POSINTCONST without OPINION]
implicitly[POSINT with OPINION =!= POSINTCONST without OPINION]

Answer 1

Sounds like you want a Least Upper Bound (LUB) of the scala types? I would look to Miles' Shapeless library for inspiration where they actually have a LUBConstraint.

Or if you want the Greater Lower Bound (GLB) I'm afraid I'd have to refer you to using a macro definition wherein you can get either the LUB or the GLB, see Types.

Answer 2

Well after randomly bashing the keyboard a lot and reading as much as I could understand about type constraints, this is what I have come up with:

// A without B is C
sealed abstract class isWithout[A, B, C]

object Syntax {

  implicit def composedWithout[A <: C, B, C](implicit ev: C <:!< B): isWithout[A, B, C] = new isWithout[A, B, C] {
    def apply(a: A) = a
  }

  type without[A, B] = {
    type l[C] = isWithout[A, B, C]
  }
}

Test that it seems to work:

implicitly[isWithout[POSCONST, POSITIVE, CONST]]
implicitly[isWithout[POSINTCONST, DISCRETE, POSNUMCONST]]
implicitly[isWithout[POSINTCONST, DISCRETE, POSITIVE]]
implicitly[isWithout[POSNUM, CONST, POSNUM]]
implicitly[isWithout[POSCONST, CONST, POSITIVE ]]
implicitly[isWithout[POSCONST, POSITIVE, CONST ]]
implicitly[isWithout[INTEGER, DISCRETE, NUMERIC ]]
implicitly[isWithout[POSINTCONST, CONST, POSINT ]]

And fails when it should:

implicitly[isWithout[POSINTCONST, INTCONST, POSINTCONST]]
implicitly[isWithout[NUMERIC, ANYSYNTAX, ANYSYNTAX]]
implicitly[isWithout[INTEGER, POSITIVE, POSINT]]
implicitly[isWithout[POSNUM, DISCRETE, POSCONST]]

implicitly gets the compiler to look for an implicit function in the current implicit scope that can produce an object of the required type (in this case, an instance of the class isWithout). If it finds one that satisfies the type signature then it compiles (I don't think it matters what the apply method defined in the class returns). The important point is the type signature, which makes use of <:!< mentioned in the question and borrowed from another SO answer by Miles.

This type signature says: A is a subtype of C and C must not be a subtype of B. An alternative version (corresponding to the first definition in the question) would be:

implicit def composedWithout[A <: C with B, B, C](implicit ev: C <:!< B): isWithout[A, B, C] = new isWithout[A, B, C] {
  def apply(a: A, b: B) = a
}

This can be used in a few ways:

1. To check the validity of the type hierarchy (ie. test cases), as shown with the above use of implicitly.

2. To specify the type of a method parameter:

   def test[R : without[POSINTCONST, DISCRETE]#l](v: R) = v

   Note that this uses the type projection without#l[C] = isWithout[A, B, C] as a context bound which the compiler desugars to:

   def test[R](v: R)(implicit $ev0: isWithout[POSINTCONST, DISCRETE, R]) = v
   

   Thus it requires the specified implicit to be in scope.

3. As a type constraint, as requested in the original question:

   case class Subtract[A <: R, R <: A without POSITIVE]( arg1: Expression[A], arg2: Expression[A] ) extends BinaryPrimitive[A, R]( arg1, arg2 )

   This compiles, although I admit I haven't run anything yet so it might not be doing what I think it's doing.