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