I was recently started reading Thinking with Types and came upon a great explanation of variance and the role it plays in reasoning about functions.
You’re probably familiar with Functor, which says that for some t a, if given a function f :: a -> b, you can transform the t a -> t b. Essentially, the essence of “functor-ness” is the ability to transform a result into another type.
What about “anti-functorn-ness”, where you want to transform the input rather than the result of a function from a -> b? Is that something interesting and worth exploring?
Indeed it is! The “functor-ness” described above is actually called Covariance, and simply means that you can transform the output of some computation T a.
Similarly, the “anti-functor-ness” of T a is called Contravariance, and means that you can transform a T b into a T a by mapping the input of the computation. There is a third form of variance called Invariance, but its not as much fun as co & contra variance.
Type variables in an expression are either positive or negative. In the function a -> b, the b is positive, while the a is negative. Just like integer mathematics, two negatives make a positive, so (a -> b) -> b actually has a in positive position, meaning this covariant in a.
In fact, whether a T a is co or contra variant in a is determined only by whether a is positive or negative. Positive a means Covariance, while negative a means Contravariance. If the a appears in both positive and negative positions, then its invariant, and therefore not particularly exciting.
Now that we have a few types of variance, lets use them to reason about whether or not some type signatures are Functors in a or not.
foo :: a -> b
bar :: b -> a
baz :: (b -> a) -> b
fiz :: (a -> b) -> b
In foo, a is the input rather than output, and since we’ve already established that Functors transform the output, foo may not be a functor. To confirm this intuition, we can use our newfound knowledge about variance & notice that a occurs in negative position. Since Functor relies on the type being covariant in a, and covariance is determined by a positive a, we can be certain that foo is contravariant and therefore not a Functor. By the same reasoning, we can be certain that bar, where a occurs in positive position, is a Functor. baz is an interesting case because a occurs in positive position in the argument function, but the argument function occurs in negative position. Just like basic arithmetic, a positive multiplied by a negative is a negative, so baz is contravariant in a and not a Functor. Again, using the same logic, by flipping the position of a in the argument function to negative position & creating a double negative, a occurs in positive position in fiz. So fiz is a Functor.
I’ll dive deeper into how (a -> b) -> b manifests itself as JavaScript style continuations in my next post.