Functors in Haskell, co- contra- and pro-

Warning

The following blog post, which started out as an unruly unkempt footnote, was hastily written to be a link to reference whenever I finish this other (even longer) blog post on profunctors and lenses. If you are not familiar with negative/positive signing for type variables I point you toward this wonderful article on co/contravariance in Haskell, which probably explains this all better than I could.

Functors

So I was told a functor in Haskell is any type with kind * -> * that admits an instance for the class

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

And I am here to tell you that this is a lie. Or, well, not a lie but at least a slightly myopic way of thinking about things.

I like to think about functors like this: any type parametrized on a where a only appears in non-negative positions usually is a functor on the type a. This sounds like nonsense, but take as an example this type:

newtype FromInt = FromInt (Int -> a)

This type easily admits a Functor instance: given an a -> b, we simply compose it onto our Int -> a to get an Int -> b. A more complicated example:

data [a] = [] | a:[a]

It turns out that a never appears in a negative position here, but it is hard to see because we have obfuscated the actual type with Haskell’s lovely ADT syntax. We can convert this to its equivalent type:

newtype List a = List (forall r. r -> (a -> List a -> r) -> r)

To implement the Functor instance: given an a -> b, we destructure the list. In the nil case we have no work to do; in the cons case we apply our function and recurse:

instance Functor List where
  fmap a2b (List alist) =
    List (\nil cons -> alist nil (\a as -> cons (a2b a) (fmap a2b as)))

Take a moment to convince yourself that this works precisely because a never appears in the negative position. We can illustrate this point better by looking at a type where this rule is violated:

Contravariant functors

newtype Predicate a = Predicate (a -> Bool)

Given an a -> b … there is not much we can do. There is no way to get a b -> Bool out. What would be really nice however is if we had a b -> a, because then we could just compose the two functions and get a Predicate b. As a matter of fact, this little nugget of intuition holds true for type over a where a never appears in a positive position. To give this idea life we create a Functor-like class but with the arrow going the other way. We call it Contravariant:

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

instance Contravariant Predicate where
  contramap a2b (Predicate b2bool) = Predicate (b2bool . a2b)

We can call this new type of functor a “contravariant” functor and realize that the functor we were talking all along above was a “covariant” functor. Just names to distinguish between the never-positive/never-negative rules, although theoretically speaking we are sort of deriving our vocabulary backwards.

Another example:

newtype Const constant a = Const constant

instance Contravariant Const where
  contramap _ (Const c) = Const c

instance Functor Const where
  fmap _ (Const c) = Const c

Because a appears in neither a positive nor negative position (nonvariant/invariant) we were able to demonstrate Const r to be both a covariant and contravariant functor.

Armed with this knowledge, this type from the lens package takes on a charged meaning:

type Getter s a = forall f. (Contravariant f, Functor f) => (a -> f a) -> s -> f s

What can we say about the a or the s in f a/f s? What types could f be? What type will f usually be?

Profunctors

What about types parametrized over both covariant variable and contravariant variables? They could admit both a Functor and a Contravariant (if we allow the order of their variables to be reordered in the declaration) but it would be much more useful to do both at the same time. And for that we have

class Profunctor p where
  dimap :: (contra' -> contra) -> (co -> co') -> p contra co -> p contra' co'

The typeclass of * -> * -> * types where the first star never appears in a negative position and the second star never appears in a positive position. Examples include:

-- a negative
-- b positive
newtype (->) a b = a -> b

instance Profunctor (->) where
  dimap s2a b2t a2b =
    b2t . a2b . s2a

-- a negative
-- b positive (if m is a covariant functor)
newtype Kleisli m a b = Kleisli (a -> m b)

instance Monad m => Profunctor (Kleisli m) where
  dimap s2a b2t (Kleisli a2mb) =
    Kleisli (fmap b2t . a2mb . s2a)

I believe it is difficult for newcomers to this idea to see profunctors as anything except obfuscation, especially when the only two instances ever presented are the (->) or the Kleisli ones. I am highly sympathetic to this point of view. Profunctors as a tool for the Haskell programmer require a little extra juice to motivate, and it comes in the form of our old friend parametricity. Parametricity is a tool to make arguments about what kinds of values can inhabit a given tyupe.

For example: the type forall a. a -> a can only admit one non-trivial value: id. It is impossible to write a function more specific than id because the forall a. constraint gives us very little to work with. Another way is to cast this into mathematical logic: by assuming the fewest possible premises, we must only derive the most general theorem. As such, forall a. a -> a is an excellent way to represent the identity function.

By a similar argument, type Mirror s a = forall p. Profunctor p => p a a -> p s s is an excellent way to represent an isomorphism between the type s and t. For example, an isomorphism between Data.Text.Text and String might look like this:

packed :: Profunctor p => p Text Text -> p String String
packed = dimap pack unpack

We can then use this to go forwards (recovering pack)…

λ> newtype Forget r a b = Forget { unForget :: a -> r }
λ> instance Profunctor (Forget r) where
     -- Here we are "forgetting" the b2b' value, which
     -- would be `unpack` in our example above. Assuming
     -- a2r = id (which it is in our example below), this
     -- neatly grabs the `pack` function and throws away
     -- the rest.
     dimap a'2a b2b' (Forget a2r) = Forget (a2r . a'2a)
λ> :t unForget $ packed (Forget id)
unForget $ packed (Forget id) :: String -> Text

… and backwards (recovering unpack).

λ> newtype Reverse p s t a b = Reverse { unReverse :: p b a -> p t s }
λ> instance Profunctor p => Profunctor (Reverse p s t) where
     -- Here we are reversing the order of the functions
     -- passed to `dimap`. Assuming mirror = id (which
     -- is in our example below), this is the simple
     -- switcheroo we need to obtain the reverse iso.
     dimap a'2a b2b' (Reverse mirror) = Reverse (mirror . dimap b2b' a'2a)
λ> :t unReverse $ packed (Reverse id)
unReverse $ packed (Reverse id) :: Profunctor p => p String String -> p Text Text
λ> let unpacked = unReverse $ packed (Reverse id)
λ> :t unForget $ unpacked (Forget id)
unForget $ unpacked (Forget id) :: Text -> String

As laid out in Phil Freeman’s excellent “Fun with Profunctors” talk, this type – by virtue of parametricity over the Profunctor p – can only represent an isomorphism. Because this type is so general (again, assuming the fewest premises to derive the most general theorems) we can only act upon it in a couple of ways:

We can compose isomorphisms together. The arrow -> in the middle of the type allows us to use our old friend (.); note that this requires no knowledge of p and thus can be done without having to specify one.
We can choose a profunctor p, construct a p s s, apply it to the type, and recover a p t t. With Forget above, we unwrap to retreive a weakened forward version of the isomorphism. With Reverse, we unwrap to retrieve the flipped isomorphism, as if we meant to construct it backwards all along (dimap unpack pack instead of dimap pack unpack). This might be surprising! It would seem as if dimap pack unpack would “lose information” about the functions we passed, but here we see evidence that dimap in fact preserves just enough information to allow us to retrieve both the functions we pass in.

Far be it for me to talk about parametricity as some sort expert; for that I refer you to Bartosz’s wonderful blog post Money for Nothing and Theorems for Free.

This representation of isomorphisms is especially potent. By introducing additional constraints on top of Profunctor p, we can represent lenses and prisms – type Lens s a = forall p. (Profunctor p, Strong p) => p a a -> p s s, type Prism s a = forall p. (Profunctor p, Choice p) => p a a -> p s s. For a full presentation of this idea, watch Phil’s talk! For me profunctors were a complete mystery until I saw functional, composable optics derived this way. Another benefit of watching the talk? The design of the lens package makes sense. I used to view lens as a UML diagram of impossible ideas and strange nouns. Now? Now I have a newfound appreciation for the work Haskellers have done in making higher-kinded types, rank-n polymorphism, and typeclasses available in a production-quality language. These are tools by which we build powerful, user-friendly, eminently-composable libraries and tools. So ends this overstuffed footnote.

Warning

Functors

Contravariant functors

Profunctors

See also