Friday, November 14, 2014

Pawn shops, refrigerators, and contravariant functors

Recently, I learned (by reading instance declarations in Haskell) that the composition of contravariant functors is covariant.

In this talk (around 27:30) Erik Meijer tells a colorful analogy for contravariance in subtyping. The analogy involves trashcans, which apparently are contravariant. I wonder if I can find a similar analogy for the case of composition, because I find it difficult to gain an intuition for it.

So, consider bananas. Bananas are a type of fruit.

Consider refrigerators as well. There are different types of refrigerators. Some have a technology advanced enough to freeze any fruit, but some are more modest and can only freeze bananas.

The refrigerators that can freeze any fruit are a subtype of the refrigerators that can freeze bananas. Because, any time you need to freeze a banana, you can freeze it in one of the refrigerators than can handle any kind of fruit.

In other words, refrigerators are contravariant.

Now consider pawn shops. Paws shops are contravariant as well: anything you can sell to a pawn shop that only takes rings, you can sell to a pawn shop that takes any jewelry. The pawn shops that take any jewelry are a subtype of the pawn shops that take rings.

There are also pawn shops for refrigerators. For example pawn shops for refrigerators that can freeze any fruit, or pawn shops for refrigerators that can freeze bananas. (Yes, they are quite specialized pawn shops, but bear with me.)

The pawnbrokers are very meticulous. Before accepting a refigerator for sale, they put inside it a viand of the type associated with the pawn shop, to check that the refrigerator indeed works.

Can you sell to the pawn shop of refrigerators that freeze bananas everything you could sell to the pawn shop of refrigerators that freeze any fruit? The answer is yes. You take the refrigerator that freezes any fruit to the pawn shop, the pawnbroker puts a banana on it, and it gets frozen. Deal!

So pawn shops for refrigerators are covariant on the type of viands that the refrigerators can freeze.

Whew, that was convoluted.