Find the most common subtype of two Scala types

Question

In the lines of this question , I am trying to find a way to get the Scala compiler to output the most common common subtype of the 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 

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

In fact, I expect someone to point out that this is not the same as the “most common generic subtype,” since I don't really require A <: B

Using:

 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 shown below:

 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 tried to come up with something using type restrictions 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] 

They must fail:

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

Answer 1

Well, after accidentally beating the keyboard and reading as much as I could understand about type restrictions, this is what I came 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] } } 

Verify that this works:

 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 it fails if necessary:

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

implicitly compiler implicitly gets to search for an implicit function in the current implicit region that can create an object of the required type (in this case, an instance of the isWithout class). If it finds one that satisfies the type signature, then it compiles (I don’t think it matters that the apply method defined in the class returns). An important point is a type signature that uses the <:!< Mentioned in the question and is borrowed from another SO answer from Miles.

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

 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 several ways:

• To verify the correctness of the type hierarchy (for example, test cases), as shown when using the above implicitly .

• To indicate the type of method parameter:

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

  Note that this uses a projection of type without#l[C] = isWithout[A, B, C] as the context boundary that the compiler assigns as follows:

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

  Thus, it requires the specified implicit to be in scope.

• As a type restriction asked 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 that I have not run anything yet, so that he does not do what I think he does.

Answer 2

Looks like you want the smallest upper bound (LUB) of scala types? I would look at the Miles' Shapeless library for inspiration, where they really have LUBConstraint .

Or, if you want Greater Lower Bound (GLB), I am afraid that I will have to refer to the use of macros in which you can get LUB or GLB, see Types .