The question

What is it that makes Functor.widen safe? I think I remember someone explaining it at some point but I can’t remember. Something about “all functors are covariant” or something like that.

– @Billzabob in gitter.im/typelevel/cats

What does Functor.widen do?

Functor.widen lets you transform some container F[A] into F[B], if A is a subtype of B. For example, a list of cats can also be viewed as a list of animals:

import cats.implicits._

val cats: List[Cat] = ???
val animals: List[Animal] = cats.widen

(Naturally, Cat is a subtype of Animal in these examples.)

Now, using widen on a List is actually redundant, as List is marked as covariant: it is defined as List[+A]. The + before the type parameter A means covariant, and if something is covariant it means you can replace some F[A] with F[B], if A is a subtype of B. So we could have instead written:

val cats: List[Cat] = ???
val animals: List[Animal] = cats // no widen necessary, because List[+A]

We might actually use widen on a type that isn’t marked as covariant, such as cats.data.EitherT:

import cats._
import cats.data.EitherT
import cats.implicits._

val cat: EitherT[Id, Throwable, Cat] = ???
val animal: EitherT[Id, Throwable, Animal] = cat.widen

How is Functor.widen implemented?

Here’s the definition from Cats:

def widen[A, B >: A](fa: F[A]): F[B] = fa.asInstanceOf[F[B]]

We see the implementation is a type cast that is guarded by the subtype constraint B >: A: type B must be a supertype of type A. The compiler won’t allow the use of widen where the subtype relationship doesn’t hold.

Back to the Question

What is it that makes Functor.widen safe?

I replied–correctly–that widen is safe because:

the signature requires the super type witness: def widen[A, B >: A](fa: F[A]): F[B]

where I conflate the term “witness” (a value that “proves” some condition holds) with the presence of the subtype bound B >: A.

However, I then misspoke:

also remember that [B >: A] is actually passed as an implicit value ev: A <:< B, and <:<[A, B] extends Function1[A, B]

I thought that subtype bounds were syntactic sugar, just as context bounds are, but I was wrong! Recall that context bounds are a way to succinctly write typeclass instance constraints, so

def something[A : Monoid] // Monoid context bound

is desugared and equivalent to

def something[A](implicit m: Monoid[A]) // implicit Monoid typeclass instance

There is an analogous implicitly passed value for subtype bounds, but the subtype bound is not syntactic sugar for it. (I thought it was.) That is, the type signature

def widen[A, B >: A](fa: F[A]): F[B]

is equivalent to the type signature

def widen[A, B](fa: F[A])(implicit ev: A <:< B): F[B]

but the former is not converted to the latter by the compiler,
as is the case for context bounds. ("B is a supertype of A" is equivalent to "A is a subtype of B"; ev stands for “evidence”.)

What is this <:< type?

The higher-kinded type <:<[A, B] represents the subtype relationship between two types, where A is a subtype of B. Types with two parameters may be written infix, so the previous type is usually written as A <:< B. If you have a value of this type, then the subtype relationship holds.

As shown above, you can “summon” an implicit value (named ev above) of type A <:< B if type A is a subtype of B. The compiler will then supply the value if it exists.

What’s the point of having this alternate representation of the subtype relationship? If an A is a subtype of B, we can rely on the compiler to “automatically” cast an A into a B. Like a typeclass instance, you only need it if you’re going to use it, which begs the question, what can you do with a A <:< B?

Using a <:< value

It turns out that A <:< B is a subtype of the function type A => B:

trait <:<[A, B] extends Function1[A, B]

This makes sense: subtyping means we can transform a value of (sub-)type A into a value of (super-)type B. And the value ev: A <:< B is the function that can do that.

It’s not common to use this value explicitly, but the fact that it exists can help demystify covariance.

Covariance without subtypes

Covariance is usually explained in terms of containers and subtypes. That is, the covariant List[A] can be cast to a List[B] if A is a subtype of B. (Cue list of cats and animals example.)

What if we could “turn off” the covariant + annotation on List, but still perform the same conversion of the container? How might we implement that ourselves? Well, to convert one list into another, we can use map:

val cats: List[Cat] = ???
val animals: List[Animal] = cats.map(???)

We need to replace ??? with a function that converts a Cat into an Animal. That’s our implicit-subtype-evidence-function thing!

val cats: List[Cat] = ???
val ev: Cat <:< Animal = implicitly
val animals: List[Animal] = cats.map(ev)

Instead of viewing covariance as the ability to convert containers of subtypes into containers of supertypes, we can recast the former definition in terms of map with the “subtype evidence” function. Covariance is a more general phenomenon: the ability to map; that is, a (covariant) Functor.

Back to Functor.widen

We can rewrite Functor.widen to explicitly convert every element using the subtype evidence, rather than using the type casting machinery of the compiler:

def explicitWiden[A, B](fa: F[A])(implicit ev: A <:< B): F[B] =
  fa.map(ev)

(Remember, F is a Functor, so there is a map method available.)

The actual implementation of Functor.widen doesn’t use this definition, as it’s unnecessary to actually perform the sub- to supertype conversion given the semantics of Scala. So instead the implementation does a cast. But I find it very illuminating to know they are equivalent!

Summary

  • It is always possible to convert a value of a subtype to its supertype. This doesn’t require any extra code at runtime, only at compile-time.
  • You can get evidence of the subtype relation as an implicit parameter. This evidence has type <:<[A, B], which is most often written infix as A <:< B. The <:<[A, B] type extends Function1[A, B], because one can always tranform subtypes into supertypes.
  • Containers of a subtype can be transformed into containers of its supertype, if you can map over the container. The usual defintion of covariance emphasizes subtypes, but the ability to map is a more general, and useful, definition.