Covariant and Contravariant Functors

coContraFunctors.md

Covariant and Contravariant Functors

This article contains more than enough examples to hopefully understand Covariant and Contravariant Functors and how to create them for many situtations.

Note that all type annotations use Int as the concrete type but any concrete type would be equivalent as would any mix of concrete types.

It assumes a general understanding of Functor and a basic understanding of Haskell type classes and data types.

Mapping from a to b(#1)

We would like to map a's to b's using a mapping function whose signature is a -> b.

The following is the canonical Functor definition and an implemenation for F1:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

newtype F1 a = F1 a

instance Functor F1 where
  fmap f (F1 g) = F1 (f g)

f is our mapping function that takes an a and returns a b.

g has type a and f g has type b.

Mapping from Int -> a to Int -> b (#2)

Now we map the result of a function call.

newtype F2 a = F2 (Int -> a)

instance Functor F2 where
  fmap f (F2 g) = F2 (f . g)

Essentially, we call our original function g and then convert the return from a to b using f.

Type substitution on f . g yields a -> b . Int -> a which reduces to Int -> b.

Mapping from a -> Int to b -> Int (#3)

newtype F3 a = F3 (a -> Int)

instance Functor F3 where
  fmap f (F g) = F (???)

We may think that g . f would work by first converting the input using f and then calling the original function g.

Problem is that f would need to be b -> a which is NOT how Functor was defined in #1.

What we need a different Functor-like class that will work with mapping functions with reversed signatures.

class Contravariant f where
  contramap :: (b -> a) -> f a -> f b

The only difference between Contravariant and Functor (which is considered Covariant) is the mapping function's signature order.

In Functor, it is a -> b. In Contravariant, it is b -> a.

Now that we have Contravariant with its reversed signature, we can write a mapping function for F3 the way we had originally hoped, i.e. by using g . f:

instance Contravariant F3 where
  contramap f (F3 g) = F3 (g . f)

Compare F2's instance (Functor) with F3's instance (Contravariant).

The only difference is the order the composition of f and g and the class changed from Functor to Contravariant.

Generalization #1

Note that mapping from Int -> a to Int -> b with a -> b (#2) used Functor, but mapping from a -> Int to b -> Int with a -> b (#3) was not possible and required a mapping function of b -> a and Contravariant.

Why? Because the position of the a and b changed which affects the composition of f and g.

At this point, the best generalization that we can make is that for 2 parameters, if the polymophic parameter, in this case a, is on the right side then Functor should be used.

And if a function has 2 parameters and the polymorphic parameter is on the left side then Contravariant should be used.

This generalization is far from complete since it is restricted to functions of 2 parameters. Let's continue to look at more complex examples to see if we can get a better understanding of when to use Functor and when to use Contravariant.

Mapping from (Int -> Int) -> a to (Int -> Int) -> b (#4)

If Generalization #1 is right, then we should use Functor since the polymorphic parameter is in the rightmost position.

newtype F4 a = F4 ((Int -> Int) -> a)

instance Functor F4 where
  fmap f (F4 g) = F4 (f . g)

Here g takes (Int -> Int) and returns an a into f which takes an a and returns a b. Now the final result takes a (Int -> Int) and returns a b which is what we wanted.

And so far, Generalization #1 is holding.

Mapping from (a -> Int) -> Int to (b -> Int) -> Int (#5)

newtype F5 a = F5 ((a -> Int) -> Int)

Unfortunately, Generalization #1 doesn't help us here. The left side has 2 parameters of which the leftmost is polymorphic, i.e. a, and the rightmost is concrete, i.e. Int.

Looking at past implementations, we see that f's signature is either a -> b if we use Functor or b -> a if we use Contravariant. And g's signature is the signature that we're starting with, in this case (a -> Int) -> Int.

Also in the past, we simply composed f and g but this time f has a signature that doesn't compose with g. So some sort of simple composition isn't going to work here.

What we ultimately need is a function that takes a b -> Int which will get converted to an a -> Int so that it can be applied to the function we started with, i.e. (a -> Int) -> Int.

We know that to convert a b -> Int to an a -> Int using composition will require an a -> b mapping function which tells us that we need a Functor.

So we create a new function, h, with a type we can convert, i.e. b -> Int and we have f, our conversion function convert it. Then we apply that to our original function, g, giving us:

instance Functor F5 where
  fmap f (F5 g) = F5 (\h -> g (h . f))

Looking at h in detail and replacing types and reducing gives us:

\h             ->   g                   (   h          .    f        )
(b -> Int)     ->   (a -> Int) -> Int   (   b -> Int   .    a -> b   )
(b -> Int)     ->   (a -> Int) -> Int   (          a -> Int          )
(b -> Int)     ->                      Int

This is exactly what we were aiming for, i.e. (b -> Int) -> Int.

Mapping from (Int -> a) -> Int to (Int -> b) -> Int (#6)

newtype F6 a = F6 ((Int -> a) -> Int)

This is sort of an inverse of the previous example. So we can expect to use a Contravariant instead of a Functor.

And if our past experience is right regarding the differences between the implementation of a Functor vs Contravariant we'll probably compose reversed in the Contravariant compared with the Functor.

Turns out that both patterns hold:

instance Contravariant F6 where
  contramap f (F6 g) = F6 (\h -> g (f . h))

Lookin at h in detail and replacing types and reducing gives us:

\h             ->   g                   (   f          .    h        )
(Int -> b)     ->   (Int -> a) -> Int   (   b -> a     . Int -> b    )
(Int -> b)     ->   (Int -> a) -> Int   (          Int -> a          )
(Int -> b)     ->                      Int

Once again, this is exactly what we were aiming for, i.e. (Int -> b) -> Int.

Generalization #2

Now that we've done some more complex mappings, it's time to revisit Generalization #1, which we knew was incomplete.

When we mapped from (Int -> Int) -> a to (Int -> Int) -> b (#4), Generalization #1 was helpful since a and b were in the rightmost position. As a reminder, we wound up using a Functor.

But when we mapped from (a -> Int) -> Int to (b -> Int) -> Int (#5), we wound up with a Functor even though a and b were the leftmost of their parenthesis.

And we used Contravariant when we mapped from (Int -> a) -> Int to (Int -> b) -> Int) (#6) even though a and b were the rightmost of their parenthesis.

So a simple rightmost/leftmost model is naive and won't work helping us decide whether we are working with the Covariant or Contravariant case.

In fact, the rules seemed to change to the polar opposite every time we enter a parenthetical.

So let's assume that it flips as we enter parenthesis and see if this flipping continues by mapping with yet another parenthetical group to get a better understanding of when we use a Covariant as opposed to a Contravariant.

A mapping strategy emerges

In #2 and #3, the function composed with f, our mapping function, has converted either an a -> Int to b -> Int or an Int -> a to Int -> b. In those cases that was sufficient since these were simple type mappings.

It was also sufficient in #4 since it's mapping (Int -> Int) -> a can be thought of a just a simple mapping of the form c -> a.

In #5 and #6, however, we had more complex mappings and although we started with f, we applied it to an anonymous function h that we had to create with the specific type signature that would allow our f to replace the a with a b.

Then we applied that to the original function to get our final type mapping.

As we move to more complex mappings, we can expect to use the strategy from #5 and #6 to get us part of the way there.

Mapping from ((a -> Int) -> Int) -> Int to ((b -> Int) -> Int) -> Int (#7)

newtype F7 a = F7 (((a -> Int) -> Int) -> Int)

Let's assume our flipping theory is correct and each time we move from right to left into another parenthesis, the rules for Covariant and Contravariant switch.

(((a -> Int) -> Int) -> Int)
           3       2       1

Starting at the rightmost parenthetical (1), we start with Covariant being the rightmost side. Then we move leftwards to the next parenthetical (2) and Contravariant is rightmost. Then we move one more time to the leftmost parenthetical (3) and the rules flip back to Covariant is the rightmost.

Since we are out of parenthesis and are done flipping, we will assume that the rightmost is Covariant and the leftmost is Contravariant.

a is in the leftmost position of the final parenthetical group (3), which means that if Generalization #2 is correct, we will be using Contravariant.

Let's see if that holds.

We have:

newtype F7 a = F7 (((a -> Int) -> Int) -> Int)

Since we expect this to be a Contravariant, our mapping function f is b -> a.

We can also expect that this will look similar to #5 since the leftmost part of the original function signature, (a -> Int) -> Int is exactly equal to #5.

Our h must be of type a -> Int to compose with f as b -> a, therefore h . f is b -> Int.

We cannot apply this to our original function, ((a -> Int) -> Int) -> Int, like before since this function has an extra Int parameter. Also, h . f is in terms of b not a.

So we must create yet another function, let's call it hh, which has the type that we can apply h . f to that finally returns an Int, viz. (b -> Int) -> Int.

So far, we have:

h :: (a -> Int)
f :: (b -> a)

h . f :: b -> Int
hh :: (b -> Int) -> Int

\h -> hh(h . f) :: (a -> Int) -> Int

\h -> hh(h . f) is perfect for applying to our original function g, i.e. ((a -> Int) -> Int) -> Int giving us our final solution:

newtype F7 a = F7 (((a -> Int) -> Int) -> Int)

instance Contravariant F7 where
  contramap f (F7 g) = F7 (\hh -> g (\h -> hh(h . f)))

Looking at the final function in detail:

\hh                 -> g                            (\h         -> hh                 (h          . f       ))
((b -> Int) -> Int) -> (((a -> Int) -> Int) -> Int) ((a -> Int) -> (b -> Int) -> Int) ((a -> Int) . (b -> a)))
((b -> Int) -> Int) -> (((a -> Int) -> Int) -> Int) ((a -> Int) -> (b -> Int) -> Int) (        b -> Int     ))
((b -> Int) -> Int) -> (((a -> Int) -> Int) -> Int) ((a -> Int) ->                Int                        )
((b -> Int) -> Int) -> (((a -> Int) -> Int) -> Int) (                 (a -> Int) -> Int                      )
((b -> Int) -> Int) ->                                       Int

Looks like we can keep Generalization #2 for now. Maybe with enough experience we can further generalize it.

Mapping from ((Int -> a) -> Int) -> Int to ((Int -> b) -> Int) -> Int (#8)

Looking at the pattern of solutions for #5 and #6, we can see that there are 2 difference:

1. one is Functor and the other is Contravariant
2. one uses h . f and the other uses f . h

Note that we make no assumption that there is any correlation between 1 and 2 here, i.e. Functor doesn't necessarily always use h . f. We just want to pick the opposite of whichever one #7 uses to create #8.

So let's take a stab at this mapping by just applying these 2 inversions to solution for #7, viz.:

1. Contravariant in #7 becomes Functor
2. h . f in #7 becomes f . h

newtype F8 a = F8 (((Int -> a) -> Int) -> Int)

instance Functor F8 where
  fmap f (F8 g) = F8 (\hh -> g (\h -> hh(f . h)))

Turns out that that approach worked great.

Mapping from (((a -> Int) -> Int) -> Int) -> Int to (((b -> Int) -> Int) -> Int) -> Int (#9)

It would be nice, at this point, if we could just follow some pattern and not have to figure this out type by type.

Although, it's not a simple pattern, there are some rules to this pattern that arise:

1. When adding an additional -> Int, a Functor becomes a Contravariant
2. When dealing with a -> Int, h . f is used
3. When dealing with Int -> a, f . h is used
4. When adding an additional -> Int beyond 2, we have to create an additional anonymous function that we can apply our h . f or f . h conversion to

We can see an example of rule #1 when going from #3 (Contravariant) to #5 (Covariant) or #4 (Covariant) to #6 (Contravariant).

Rule #2 can be seen in #5 and rule #3 in #6.

Rule #4 has an interesting pattern. Starting with #5, things get complicated but repetitive.

The a -> Int cases:

• #3: (g . f)
• #5: (\h -> g (h . f))
• #7: (\hh -> g (\h -> hh(h . f)))

The Int -> a cases:

• #4: (f . g)
• #6: (\h -> g (f . h))
• #8: (\hh -> g (\h -> hh(f . h)))

The two cases only differ by the order of composition.

But as additional -> Int's got added, e.g. moving from #4 to #6, g gets pulled out and replaced with an anonymous function, we progressively called h then hh, etc.

This new construct gets applied to g, our original function as the final step.

Then the whole thing is wrapped by this anonymous function.

If we continue this pattern, we can build #9 with these steps:

Start with #7, the version with 1 less -> Int:

(\hh -> g (\h -> hh(h . f)))

Pull g out and place it front (leaving the hole _ for now):

g (\hh -> _(\h -> hh(h . f)))

Replace the hole with a new anonymous function (adding one more h to help keep things straight, i.e. hhh):

g (\hh -> hhh(\h -> hh(h . f)))

Then wrapping it up in this new anonymous function, viz. hhh:

(\hhh -> g (\hh -> hhh(\h -> hh(h . f))))

Since #7 is a Contravariant, rule #1 would say that #9 will need to be Functor.

So applying our pattern rules and starting with #7 as a starting point, we now have:

newtype F9 a = F9 ((((a -> Int) -> Int) -> Int) -> Int)

instance Functor F9 where
  fmap f (F9 g) = F9 (\hhh -> g (\hh -> hhh(\h -> hh(h . f))))

which compiles making us confident that we can continue to build these ad infinitum, e.g. the next few in this iteration are:

(\hhhh -> g (\hhh -> hhhh(\hh -> hhh(\h -> hh(h . f)))))
(\hhhhh -> g (\hhhh -> hhhhh(\hhh -> hhhh(\hh -> hhh(\h -> hh(h . f))))))
(\hhhhhh -> g (\hhhhh -> hhhhhh(\hhhh -> hhhhh(\hhh -> hhhh(\hh -> hhh(\h -> hh(h . f)))))))

All of these h's are making my eyes glaze over. Let's simplify:

(\h4 -> g (\h3 -> h4(\h2 -> h3(\h -> h2(h . f)))))
(\h5 -> g (\h4 -> h5(\h3 -> h4(\h2 -> h3(\h -> h2(h . f))))))
(\h6 -> g (\h5 -> h6(\h4 -> h5(\h3 -> h4(\h2 -> h3(\h -> h2(h . f)))))))

Mapping from (((Int -> a) -> Int) -> Int) -> Int to (((Int -> b) -> Int) -> Int) -> Int (#10)

Going from #9 to #10 is far easier than going from #7 to #9.

The rules are simpler (see the pattern rules under #8). The differences here are Functor to Contravariant (and visa versa) and h . f to f . h (and visa versa).

Therefore:

newtype F10 a = F10 ((((Int -> a) -> Int) -> Int) -> Int)

instance Contravariant F10 where
  contramap f (F10 g) = F10 (\hhh -> g (\hh -> hhh(\h -> hh(f . h))))

Now what?

No sense in continuing since a pattern has arisen that can be used to generate more and more complex versions.

Besides, we've long since surpassed any reasonable likelihood that we'll see such signatures in the wild.

But what about other signature forms?

Mapping from Int -> Int -> a to Int -> Int -> b (#11)

This mapping can be written like:

Int -> (Int -> a)

which are not necessary since arrows, ->, associate to the right. But it's important to draw them like this for just long enough for us to recognize that we are dealing with the polar opposite signatures than we've been dealing with so far which were associated to the left.

But it is clear that these forms are going to be easier to deal with.

This particular mapping is easy. We simply call the function and then map the results.

Since we are converting a return value of type a to be of type b, we need a mapping function from a -> b which means we need to use Functor.

But first we need a few helper functions with it's parameter names written backwards from what would be traditional to help us keep track of our mapping functions f:

compose2 :: (a -> b -> c) -> (c -> d) -> a -> b -> d
compose2 g f = (f .) . g

compose3 :: (a -> b -> c -> d) -> (d -> e) -> a -> b -> c -> e
compose3 g f = ((f .) .) . g

compose4 :: (a -> b -> c -> d -> e) -> (e -> f) -> a -> b -> c -> d -> f
compose4 g f = (((f .) .) .) . g

compose5 :: (a -> b -> c -> d -> e -> f) -> (f -> g) -> a -> b -> c -> d -> e -> g
compose5 g f = ((((f .) .) .) .) . g

We need compose2 here but will use the other functions for functions that take more parameters.

Now we can map:

newtype F11 a = F11 (Int -> Int -> a)

instance Functor F11 where
  fmap f (F11 g) = F11 (compose2 g f)

In compose2, our mapping function, f, is executed last to convert the return of g from a to b.

Mapping from Int -> a -> Int to Int -> b -> Int (#12)

Here, we are mapping a parameter of type a instead of a return value, which means we'll need to map the parameter from b to a before we call our original function, g.

That requires a mapping function from b -> a, telling us that we need to use a Contravariant.

Before we do that though, we'll need some helpers to map our parameters:

callMap2of2 :: (b -> a) -> (c -> a -> d) -> c -> b -> d
callMap2of2 f g x y = g x (f y)

callMap1of2 :: (b -> a) -> (a -> c -> d) -> b -> c -> d
callMap1of2 f g x = g (f x)

callMap2of2 will call our original function, g, after mapping the 2nd parameter of a 2 parameter function call.

callMap1of2 does the same except it maps the 1st parameter and we'll use it later.

So our map is:

newtype F12 a = F12 (Int -> a -> Int)

instance Contravariant F12 where
  contramap f (F12 g) = F12 (callMap2of2 f g)

Mapping from a -> Int -> Int to b -> Int -> Int (#13)

Once again we are mapping a parameter except the only difference between this mapping and #12 is that parameter is the 1st.

So, we do what we did in #12 except use callMap1of2 instead:

newtype F13 a = F13 (a -> Int -> Int)

instance Contravariant F13 where
  contramap f (F13 g) = F13 (callMap1of2 f g)

Mapping from Int -> ... -> a to Int -> ... -> b (#14)

This is a general case of #11 and will look something like:

-- Pseudocode
newtype F14 a = F14 (Int -> ... -> a)

instance Functor F14 where
  fmap f (F14 g) = F14 (composeN g f)

where composeN is the compose function where N is the count of concrete parameters.

Mapping from a -> ... -> Int to b -> ... -> Int (#15)

This is the general case of #12 and #13 and will look something like:

-- Pseudocode
newtype F15 a = F15 (a -> ... -> Int)

instance Contravariant F15 where
  contramap f (F15 g) = F15 (callMapNofM f g)

where callMapNofM is the parametric mapping function that maps the Nth parameter of a function of M parameters.

Conclusion

Hopefully, working through all of these examples will help to inform how and when to use Functor or Contravariant.