title: Composition of two functors is a functor
body: <p>In <a href="https://stackoverflow.com/a/13939606/546084">a previous answer</a>, Petr Pudlak defined the <code>CFunctor</code> class, for functors other than those from <em>Hask</em> to <em>Hask</em>. Re-writing it a bit using type families, it looks like</p>
  
  <pre><code>class CFunctor f where
    type Dom f :: * -&gt; * -&gt; *               -- domain category
    type Cod f :: * -&gt; * -&gt; *               -- codomain category
    cmap :: Dom f a b -&gt; Cod f (f a) (f b)  -- map morphisms across categories
  </code></pre>
  
  <p>with instances that look like, e.g.</p>
  
  <pre><code>instance CFunctor Maybe where
    type Dom Maybe = (-&gt;)                   -- domain is Hask
    type Cod Maybe = (-&gt;)                   -- codomain is also Hask 
    cmap f = \m -&gt; case m of
                     Nothing -&gt; Nothing
                     Just x  -&gt; Just (f x)
  </code></pre>
  
  <p>In category theory, whenever <em>F : C --> D</em> is a functor and <em>G : D --> E</em> is a functor, then the composition <em>GF : C --> E</em> is also a functor.</p>
  
  <p>I'd like to express this in Haskell. Since I can't write <code>instance CFunctor (f  . g)</code> I introduce a wrapper class:</p>
  
  <pre><code>newtype Wrap g f a = Wrap { unWrap :: g (f a) }
  </code></pre>
  
  <p>In writing the <code>CFunctor</code> instance I get as far as</p>
  
  <pre><code>instance (CFunctor f, CFunctor g, Cod f ~ Dom g) =&gt; CFunctor (Wrap g f) where
    type Dom (Wrap g f) = Dom f
    type Cod (Wrap g f) = Cod g
    cmap = undefined
  </code></pre>
  
  <p>but I can't figure out what the implementation of <code>cmap</code> should be. Any advice?</p>
  
  <p><strong>PS</strong> the eventual reason for all this is to also introduce a class <code>Adjunction</code> with methods <code>unit</code> and <code>counit</code>, 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.</p>
  
  <p>I'm aware that I could use <code>cmap.cmap</code> on an object of type <code>g (f a)</code> 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?</p>