Composition of two functors is a functor

Question

In a previous answer, Petr Pudlak defined the CFunctor class, for functors other than those from Hask to Hask. Re-writing it a bit using type families, it looks like

class CFunctor f where
  type Dom f :: * -> * -> *               -- domain category
  type Cod f :: * -> * -> *               -- codomain category
  cmap :: Dom f a b -> Cod f (f a) (f b)  -- map morphisms across categories

with instances that look like, e.g.

instance CFunctor Maybe where
  type Dom Maybe = (->)                   -- domain is Hask
  type Cod Maybe = (->)                   -- codomain is also Hask 
  cmap f = \m -> case m of
                   Nothing -> Nothing
                   Just x  -> Just (f x)

In category theory, whenever F : C --> D is a functor and G : D --> E is a functor, then the composition GF : C --> E is also a functor.

I'd like to express this in Haskell. Since I can't write instance CFunctor (f . g) I introduce a wrapper class:

newtype Wrap g f a = Wrap { unWrap :: g (f a) }

In writing the CFunctor instance I get as far as

instance (CFunctor f, CFunctor g, Cod f ~ Dom g) => CFunctor (Wrap g f) where
  type Dom (Wrap g f) = Dom f
  type Cod (Wrap g f) = Cod g
  cmap = undefined

but I can't figure out what the implementation of cmap should be. Any advice?

PS the eventual reason for all this is to also introduce a class Adjunction with methods unit and counit, and then automatically derive monad instances from adjunctions. But first, I need to show the compiler that the composition of two functors is also a functor.

I'm aware that I could use cmap.cmap on an object of type g (f a) and that would work, but it seems a little like cheating - surely a functor is just a functor, and the compiler shouldn't have to know that it's actually the composition of two other functors?

Answer 1

Given functors F : C → D and G : D → E, a functor composition G ∘ F : C → E is a mapping of objects between categories C and E, such that (G ∘ F)(X) = G(F(X)) and a mapping between morphisms such that (G ∘ F)(f) = G(F(f)).

This suggests that your CFunctor instance should be defined as follows:

instance (CFunctor f, CFunctor g, Cod f ~ Dom g) => CFunctor (Wrap g f) where
  type Dom (Wrap g f) = Dom f
  type Cod (Wrap g f) = Cod g
  cmap f = cmap (cmap f)

However, composing cmap twice gives you Dom f a b -> Cod g (g (f a)) (g (f b)) and cmap in this instances has a type Dom f a b -> Cod g (Wrap g f a) (Wrap g f b).

We can get from g (f a) to Wrap g f and vice versa, but since the instance declaration doesn't make any assumptions about the structure of Cod g, we are out of luck.

Since we know that functor is a mapping between categories, we can use the fact that Cod g is a Category (on Haskell side, this requires a Category (Cod g) constraint), this gives us few operations to work with:

cmap f = lift? unWrap >>> cmap (cmap f) >>> lift? Wrap

This, however, requires a convenient lifting operator lift?, which lifts a function from Hask category to Cod g category. Writing Cod g as (~>), the type of lift? must be:

lift? :: (a -> b) -> (a ~> b)

lift? unWrap  :: Wrap g f a ~> g (f a)
cmap (cmap f) :: g (f a)    ~> g (f b)
lift? Wrap    :: g (f b)    ~> Wrap g f b

lift? unWrap >>> cmap (cmap f) >>> lift? Wrap :: Wrap g f a ~> Wrap g f b

Now, there are at least two choices for this lifting operator:

• You could expand the constrait from Category (Cod g) to Arrow (Cod g) in which case the lifting operator becomes arr,
• or, as Sjoerd Visscher mentions in comments, you could use the fact that Wrap and unWrap are semantically id at runtime, in which case the use of unsafeCoerce is justified.