What does it mean to compose two Functors?

Question

Exercise 5 of the Haskell Typeclassopedia Section 3.2 asks for a proof or counterexample on the statement

The composition of two Functors is also a Functor.

I thought at first that this was talking about composing the fmap methods defined by two separate instances of a Functor, but that doesn't really make sense, since the types wouldn't match up as far as I can tell. For two types f and f', the types of fmap would be fmap :: (a -> b) -> f a -> f b and fmap :: (a -> b) -> f' a -> f' b, and that doesn't really seem composable. So what does it mean to compose two Functors?

Answer 1

A Functor gives two mappings: one on the type level mapping types to types (this is the x in instance Functor x where), and one on the computation level mapping functions to functions (this is the x in fmap = x). You are thinking about composing the computation-level mapping, but should be thinking about composing the type-level mapping; e.g., given

newtype Compose f g x = Compose (f (g x))

can you write

instance (Functor f, Functor g) => Functor (Compose f g)

? If not, why not?

Answer 2

What this is talking about is the composition of type constructors like [] and Maybe, not the composition of functions like fmap. So for example, there are two ways of composing [] and Maybe:

newtype ListOfMabye a = ListOfMaybe [Maybe a]
newtype MaybeOfList a = MaybeOfList (Maybe [a])

The statement that the composition of two Functors is a Functor means that there is a formulaic way of writing a Functor instance for these types:

instance Functor ListOfMaybe where
    fmap f (ListOfMaybe x) = ListOfMaybe (fmap (fmap f) x) 

instance Functor MaybeOfList where
    fmap f (MaybeOfList x) = MaybeOfList (fmap (fmap f) x)

In fact, the Haskell Platform comes with the module Data.Functor.Compose that gives you a Compose type that does this "for free":

import Data.Functor.Compose

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

Compose is particularly useful with the GeneralizedNewtypeDeriving extension:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype ListOfMaybe a = ListOfMaybe (Compose [] Maybe a)
   -- Now we can derive Functor and Applicative instances based on those of Compose
   deriving (Functor, Applicative)

Note that the composition of two Applicatives is also an Applicative. Therefore, since [] and Maybe are Applicatives, so is Compose [] Maybe and ListOfMaybe. Composing Applicatives is a really neat technique that's slowly becoming more common these days, as an alternative to monad transformers for cases when you don't need the full power of monads.

Answer 3

The composition of two functions is when you put one function inside another function, such as

round (sqrt 23)

This is the composition of the two functions round and sqrt. Similarly, the composition of two functors is when you put one functor inside another functor, such as

Just [3, 5, 6, 2]

List is a functor, and so is Maybe. You can get some intuition for why their composition also is a functor if you try to figure out what fmap should do to the above value. Of course it should map over the contents of the inner functor!