## 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.

## 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.EitherTimport 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 = implicitlyval 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.