Introduce bivariance

[neko-kai]

Given two type classes

trait ContravariantFunctor[F[-_]] {
  def contramap[A, B](fa: F[A])(f: B => A): F[B]
}

trait Functor[F[+_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

and a type

case class Const[A, B](a: A)

There's no way to define both instances:

given [A] Functor[[+B] => Const[A, B]]
given [A] ContravariantFunctor[[-B] => Const[A, B]]

At most one instance could be defined for Const, if Const's B parameter is declared with suitable variance:

case class Const[A, -B](a: A)
case class Const[A, +B](a: A)

However, there's no way to specify Const's true, phantom variance or bivariance, that is compatible with both covariant and contravariant placeholders. If a bivariance annotation was available it would be possible to declare a Const type compatible with both typeclasses:

case class Const[A, +-B](a: A)

given [A] Functor[[+B] => Const[A, B]]
given [A] ContravariantFunctor[[-B] => Const[A, B]]

Previous content on bivariance for Scala: https://failex.blogspot.com/2016/09/the-missing-diamond-of-scala-variance.html https://www.benjamin.pizza/posts/2019-01-11-the-fourth-type-of-variance.html

[smarter]

While bivariance does make sense for Const, I wonder if there are other situations in which it would be helpful ? Otherwise, I'm not sure it's worth adding to the language if the usecase is extremely narrow.

[neko-kai]

@smarter I think that alone is a good usecase – e.g. I'm trying to make yet another typeclass hierarchy, using as much variance as possible, and without a bivariant Const a lot of things become inexpressible – this is the main obstacle to viable use of variance in typeclasses.

[smarter]

Do you actually need a data type to represent Const? You could define:

given [T]: Functor[[+S] =>> T] {
  def map[A, B](fa: T)(f: A => B): T = fa
}

given [T]: ContravariantFunctor[[-S] =>> T] {
  def contramap[A, B](fa: T)(f: B => A): T = fa
}

[neko-kai]

@smarter These type lambdas still have incompatible kinds, i.e. there's no way to instantiate the following placeholder with a type lambda:

type Given[F[_[_]], G[_[_]], H[_]] = [A] =>> (F[H], G[H]) => H[A]

def x[A]: Given[Functor, ContravariantFunctor, [S] => A] = ???
//Type argument Functor does not conform to upper bound [_$3 <: [_$4] => Any] => Any

There's no type lambda or synonym that would be compatible with H in this position.

^ scala 2 actually instantiates above Given with mismatched variance, but that's just a bug – you can't write out the expansion without an error

[Odomontois]

Such type would collapse very easy. Consider For all A B and X

Const[X, A] <:  Const[X, Any] //  covariance
Const[X, Any] <: Const[X, B]  // contravariance

so we get

Const[X, A] <: Const[X, B]
Const[X, B] <: Const[X, A]

which means

Const[X, A] =:= Const[X, B]

so such type should basically be equivalent to the following

case class Const1[A](a: A)
type Const[A, B] = Const1[A]

[neko-kai]

Another use-case for bivariance: using a type parameter purely to modify the implicit scope, without affecting the compatibility of instances in which only this phantom type parameter is different.

Real-world example: https://github.com/7mind/izumi/pull/1036

Encoding this in Scala 2 requires adding an ugly casting implicit rule, like:

  // emulate bivariance for ModuleMake. The only purpose of the first parameter is to initiate
  // the search in its companion object, otherwise the parameter should be ignored when deciding
  // whether instances are subtypes of each other (aka bivariance)
  @inline implicit final def makeSelf[T <: ModuleBase](implicit T: ModuleMake.Aux[Nothing, T]): ModuleMake[T] =
    T.asInstanceOf[ModuleMake[T]]

To coerce instances with different phantom type parameter.

[neko-kai]

Another reason for bivariance: no-nonsense polymorphic values. A type with a bivariant parameter X[+-T] is very similar to a polymorphic type forall T. X[T], moreover, it's even more powerful than a polymorphic type, since its instantiation can also be reinstantiated and its polymorphism is transient when its used in parameter position of another variant type.

Moreover, bivariance opens a path to yes-nonsense polymorphic values - A bivariant parameter + @uncheckedVariance allows crafting your own super-polymorphic values.