In scala 3, is it possible to make covariant/contravariant type constructor to honour coercive subtyping?

Question

This is a simple example:

object CoerciveCovariance {

  trait Cov[+T]

  def cast[A, B](v: Cov[A])(
      implicit
      ev: A <:< B
  ) = {
    v: Cov[B]
  }
}

It doesn't compile:

CoerciveCovariance.scala:11:5: Found:    (v : xxx.CoerciveCovariance.Cov[A])
Required: xxx.CoerciveCovariance.Cov[B]
one error found

Is it very hard to make to compiler to figure out the missing coercive upcasting from Cov[A] to Cov[B]? Why is it not the default behaviour?

Vaasta

Answer 1

Because type inference and implicit resolution are different. <: and + belong to type inference, <:< belongs to implicit resolution.

They make impact to each other. Indeed, type inference makes impact to implicit resolution

trait TC[A]
implicit val int: TC[Int] = null

def foo[A](a: A)(implicit tc: TC[A]) = null
foo(1) // compiles
foo("a") // doesn't compile

Here firstly type A is inferred to be Int (or String) and then it's checked that there is an implicit for Int (and no implicit for String).

Similarly, implicit resolution makes impact to type inference

trait TC[A, B]
implicit val int: TC[Int, String] = null

def foo[A, B](a: A)(implicit tc: TC[A, B]): B = ???
val x = foo(1)
// checking the type
x: String // compiles

Here the type String was inferred from the type class having the only instance.

So type inference and implicit resolution make impact to each other but are different.

If A <: B then A <:< B

def test[A <: B, B] = implicitly[A <:< B] // compiles

but if A <:< B then not necessarily A <: B

def checkSubtype[A <: B, B] = null

def test[A, B](implicit ev: A <:< B) = checkSubtype[A, B] // doesn't compile

<: is checked by the compiler according to the spec https://scala-lang.org/files/archive/spec/2.13/03-types.html#conformance

<:< is just a type class

sealed abstract class <:<[-From, +To] extends (From => To) with Serializable

with the only instance

object <:< {
  implicit def refl[A]: A =:= A = singleton.asInstanceOf[A =:= A] // the instance
}

sealed abstract class =:=[From, To] extends (From <:< To) with Serializable

So <:< doesn't have many properties of an order. By default there is no transitivity

def test[A, B, C](implicit ev: A <:< B, ev1: B <:< C) = implicitly[A <:< C] // doesn't compile

no antisymmetry

def test[A, B](implicit ev: A <:< B, ev1: B <:< A) = implicitly[A =:= B] // doesn't compile

no monotonicity

def test[A, B, F[+_]](implicit ev: A <:< B) = implicitly[F[A] <:< F[B]] // doesn't compile

Although starting from Scala 2.13 the following methods are defined in the standard library

sealed abstract class <:<[-From, +To] extends (From => To) with Serializable {
  def andThen[C](r: To <:< C): From <:< C = {
    type G[-T] = T <:< C
    substituteContra[G](r)
  }

  def liftCo[F[+_]]: F[From] <:< F[To] = {
    type G[+T] = F[From] <:< F[T]
    substituteCo[G](implicitly[G[From]])
  }
}

object <:< {
  def antisymm[A, B](implicit l: A <:< B, r: B <:< A): A =:= B = singleton.asInstanceOf[A =:= B]
}

but they do not define implicits. So if you need these properties you can define transitivity

implicit def trans[A, B, C](implicit ev: A <:< B, ev1: B <:< C): A <:< C = ev.andThen(ev1)

def test[A, B, C](implicit ev: A <:< B, ev1: B <:< C) = implicitly[A <:< C] // compiles

Antisymmetry is trickier

implicit def antisym[A, B](implicit ev: A <:< B, ev1: B <:< A): (A =:= B) = <:<.antisymm[A, B]

def test[A, B](implicit ev2: A <:< B, ev3: B <:< A) = implicitly[A =:= B] // doesn't compile

If you resolve implicits manually ... = implicitly[A =:= B](antisym[A, B]), you'll see the reason (although implicitly[A =:= B](antisym[A, B](ev2, ev3)) works)

ambiguous implicit values:
 both method antisym in object App of type [A, B](implicit ev: A <:< B, ev1: B <:< A): A =:= B
 and value ev2 of type A <:< B
 match expected type A <:< B

So you have to resolve this ambiguity prioritizing implicits. You can't decrease the priority of implicit parameter ev2. So you have to decrease the priority of antisym, which is your implicit in the current scope, you can't put it to the implicit scope (companion object etc.). The only way I found is with shapeless.LowPriority

implicit def antisym[A, B](implicit ev: A <:< B, ev1: B <:< A, lp: LowPriority): (A =:= B) = <:<.antisymm[A, B]

def test[A, B](implicit ev2: A <:< B, ev3: B <:< A) = implicitly[A =:= B] //  compiles

Similarly you can define monotonicity

implicit def liftCo[A, B, F[+_]](implicit ev: A <:< B): F[A] <:< F[B] = ev.liftCo[F]

def test[A, B, F[+_]](implicit ev: A <:< B) = implicitly[F[A] <:< F[B]] // compiles
def test1[A, B](implicit ev: A <:< B) = implicitly[Cov[A] <:< Cov[B]] // compiles

But if you put all instances into the scope you'll have compile-time Stackoverflow

implicit def liftCo[A, B, F[+_]](implicit ev: A <:< B): F[A] <:< F[B] = ev.liftCo[F]
implicit def trans[A, B, C](implicit ev: A <:< B, ev1: B <:< C): A <:< C = ev.andThen(ev1)
implicit def antisym[A, B](implicit ev: A <:< B, ev1: B <:< A, lp: LowPriority): (A =:= B) = <:<.antisymm[A, B]

def test[A, B, F[+_]](implicit ev: A <:< B) = implicitly[F[A] <:< F[B]] // doesn't compile, Stackoverflow

So I guess you see why those methods are not defined as implicits by default. This would pollute the implicit scope.

More about the difference <: vs. <:< https://blog.bruchez.name/posts/generalized-type-constraints-in-scala/

Besides (compile-time) type class <:< there is also (runtime) method <:< from scala-reflect

import scala.language.experimental.macros
import scala.reflect.macros.blackbox

def checkSubtype[A, B]: Unit = macro checkSubtypeImpl[A, B]

def checkSubtypeImpl[A: c.WeakTypeTag, B: c.WeakTypeTag](c: blackbox.Context): c.Tree = {
  import c.universe._
  println(weakTypeOf[A] <:< weakTypeOf[B])
  q"()"
}

type A <: B
type B 
checkSubtype[A, B] // scalac: true    // scalacOptions += "-Ymacro-debug-lite"

type A
type B 
checkSubtype[A, B] // scalac: false

Scala 2.13.10.

Ensure arguments to generic method have same type in trait method

What is the implicit resolution chain of `<:<`

Type parameter under self-type doesn't conform to upper bound despite evidence

Covariance type parameter with multiple constraints

How to do type-level addition in Scala 3?

Limes

stackoverflow.com/questions/62849306 https://mcmap.net/q/111971/-t-lt-a-return-t-method typelevel.org/blog/2014/07/02/type_equality_to_leibniz.html typelevel.org/blog/2014/09/20/higher_leibniz.html stackoverflow.com/questions/76019334 – Limes

Answer 2

Technically, A <:< B is an implicit conversion, it doesn't enable compiler access the knowledge that for every A where there is covariance B can be used instead, and for every B when there is contravariance A could be used.

And the value of <:< is provided by scala.<:< companion (summoning <:< finds implicit def for =:= and then uses variances and subtyping rules to change it into A <:< B), so kind of on standard library level rather than language level. So you could e.g. disable importing scala and provide your own things.

For informing the type system directly about type relations, you should use type bounds rather than evidence values and "generalized type bounds":

object CoerciveCovariance {

  trait Cov[+T]

  def cast[A, B >: A](v: Cov[A]) = {
    v: Cov[B]
  }
}

or if you are really interested in expanding <:< abilities in particular you can provide your own implicit conversion:

object CoerciveCovariance {

  trait Cov[+T]

  import scala.language.implicitConversions
  implicit def castF[F[+_], A, B](fa: F[A])(implicit ev: A <:< B): F[B] =
    ev.substituteCo(fa)

  def cast[A, B](v: Cov[A])(implicit
      ev: A <:< B
  ): Cov[B] = {
    v: Cov[B]
  }
}

Theravada