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?

For endofunctors on Hask, the DeriveFunctor extension would certainly handle that (and many other cases) automatically. But if you have to manually implement it, I don't see why you'd expect anything simpler than mapping over composed functors by composing maps over each? — C. A. McCann
Basically, cmap f = cmap (cmap f) is the definition of the composition of functors, so why should using that be cheating in any way? — Daniel Fischer
@C.A.McCann I'd be happy to write cmap = cmap . cmap as the implementation, but that's not correct for the type constructor Wrap g f (in particular, it takes Dom f a b to Cod g (g (f a)) (g (f b)) rather than Cod g (Wrap g f a) (Wrap g f b). As stated, I'm particularly interested in cases other than endofunctors on Hask. — Chris Taylor
@DanielFischer Because g (f a) isn't just the composition of two functors, it's also a functor itself, so I think I should be able to use cmap on it (kind of similar to how you don't have to write lift . lift . lift all over the place when using monad transformers, if you can tell the compiler how to lift certain functions automatically -- here I want to tell the compiler how to map a morphism across two categories with a single application of cmap). — Chris Taylor
I meant using that in the definition of cmap for Wrap f g. But, looking at it, I don't see how to do it for general g; only for Cod g = (->) is it obvious. — Daniel Fischer

Vitus Vitus · Accepted Answer · 2012-12-24T00:10:25

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.

Composition of two functors is a functor

1 Answers