Monoidal Contravariant Functors are actually useful!

Tl;dr

The tl;dr is that we can take functions that are concrete in their output, combine them with concat, and contramap over their input. This allows us to do cool things like combine filter predicates and sort comparisons while providing flexibility on their arguments. I ran out of acceptable blog post space, but it also is wonderfully useful when transducing.

Prereq

I expect you already know what a monoid is before reading this. If not, checkout https://www.youtube.com/watch?v=JZSoPZUoR58 to get a feel for monoids as well as transducers which I’ll touch on toward the end of this post. Also, you should be comfortable with functors before tackling contravariant ones.

Lastly, here’s a quick set of imports if you’d like to follow along. You’ll just want to npm install ramda pointfree-fantasy daggy. I’m using babel-node to run this locally.

Covariant Functors

The functors we’re used to are called covariant functors. We don’t normally mention the covariant part since it’s the norm.

Since contravariant functors usually hold functions, it’s helpful to know how functions are normal, covariant functors before we discuss a different type of variance.

Function Functors

If we think of a function as a container for an eventual value — the output we get by running the function — then mapping it would just be composition. Check it out:

The functor instance is literally just composition:

The part to notice is in a function (a -> b), we map over the output b. So we get (String -> Int), (String -> Bool), etc. This trick of composing as we map works just fine because of the composition law of functors:

compose(map(f), map(g)) == map(compose(f, g))

Many functors are built this way including IO, Task, and Stream. Mapping simply builds up a computation to run later — kind of like the command pattern. It’s also worth mentioning the function functor is the basis of the Reader monad.

Contravariant Functors

With contravariant functors, we map over the a in (a -> b). In other words, the input, not the output. We usually need to do this when the b is a concrete type that we can’t change and the a is stuck inside a type already. Um. er. Let’s just look at some examples to get a feel.

Predicates

Let’s make ourselves a Pred type:

We call its one property run because it’s holding a function inside the type. This function must be (a -> Bool) which is parameterized on its input, but concrete on its output. This is the typical shape of a contravariant functor as we’ll be mapping over the input, not the output.

For a type to be a contravariant functor, we must provide a method called contramap :: (b -> a). Here it is for Pred:

Contrast this with the covariant function functor (say that 10 times quickly in a mirror to summon Kmett). It simply composes g beforehand, which has the effect of transforming our a before it gets to the (a -> Bool) function. We’re contravariant baby!

I find it’s much cooler to see in use if we first make it a monoid so let’s do that before playing with it.

Pred Monoid

We’ll concat two Preds by running both and keeping the conjunction. We should make the empty method always returns true so it acts as identity.

This is basically the All monoid under the hood. We could make it more generic by calling concat on the return values or parameterizing the underlying monoid, but let’s stick with this for simplicity.

Pred Examples

Now to use this crazy thing:

What’s so cool about this is that we can make a flexible rule engine. We combine multiple predicate functions with concat and map over the input before we have to return the Bool. This isn’t specific to Array — we could apply this to Stream or Tree or Option or other types that have a filter method (which can be derived from any foldable monoid).

Comparisons

Time to look at a different contravariant functor. We need to do a bit of setup first, however. JavaScript’s sort() expects a return type of 1,0,-1. We should make an enum to make it easier to understand and talk about this output.

Also since we’re going to use Ordering directly as a monoid and we didn’t make a full on Ordering type wrapper, let’s just make some normal functions to act as our monoid instance.

That’s a weird looking monoid instance, but it’s pretty simple. If the first ordering is EQ, it uses the second one: o2. So if given to sort(), it acts like “sort by this, then by that”. We could formalize this further and use cool tricks like valueOf to make Ordering a type that actually works with sort(), but let’s get to the good stuff.

Comparison Type

Here’s the definition:

Just like Pred, we have a function inside which we’ll call compare. This function is concrete on its output, but not its input so we know it’d be useful as a contravariant functor. Let’s make it so:

Check it out — we hit both our inputs with f before comparing. In effect, we map over our input and keep the concrete output. Again, the monoid instance makes this infinitely cooler, so let’s use our Ordering stuff to make it happen before playing with it.

We just defer to our previous Ordering monoid under the hood. So this will act like “sort by this, then by that” when we concat two Comparisons.

Comparison Examples

Now let’s play around with our Comparison type. I think it’d be interesting to sort by a specific set of rules.

We’re using a standard JS sort() here. This can almost certainly be made nicer by using a sortBy(f) function that understands Ordering (perhaps by using a valueOf trick). In any case, we can combine and sort by our blackjack rules. But what if we don’t have Int’s? contramap to the rescue:

Check that out! We can convert our cards to ints before comparing them. Mapping input ftw!

Conclusion…or is it?

I wanted to talk about how transducers are monoidal contravariant functors, but this post is pretty long as it is. I’ll probably write a follow up post soon on that, but if you want to see the example, here is a gist link (they’re at the bottom): https://gist.github.com/DrBoolean/fdef9e08352ac42754f1

I hope this post helped you gain an intuition about contravariant functors. There are many more instances out there so keep an eye out!

*Artwork by Olle Eksell via http://www.doodlersanonymous.com/