How to understand the type of (fmap fmap fmap) in Haskell?

Question

In Haskell, the Functor has a function fmap which the type of it is:

ghci> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

This makes sense to me that fmap lifts a function from the type of a -> b to f a -> f b.

Then I am curious about what is the type of fmap fmap, so I tried and got something weird to me:

ghci> :t fmap fmap
fmap fmap
  :: (Functor f1, Functor f2) => f1 (a -> b) -> f1 (f2 a -> f2 b)

Hmm, this type is somewhat complicate, but I can explain it by replacing a with a -> b and b with f2 a -> f2 b.

Then, I wanted to one step further:

fmap fmap fmap
  :: (Functor f1, Functor f2) => (a -> b) -> f1 (f2 a) -> f1 (f2 b)

Oh, wait! Things go to be fun when putting 3 fmap together. How to explain this?

Could someone help to explain how could I derive the type of fmap fmap fmap?

Answer 1

For clarity, let's introduce

fmapA, fmapB, fmapC :: Functor f => (a -> b) -> f a -> f b
fmapA = fmapB = fmapC = fmap

and consider

   fmapA fmapB fmapC :: ?

Forget about fmapB for a bit, start with fmapA _ fmapC. You're treating fmapC on the right as a container here, over which you map something. Does that make sense? Well, look at the type in non-infix form. Recall that x -> y -> z is the same as x -> (y -> z), and p -> q is the same as ((->) p) q, thus

fmapC :: ((->) p) q where {p ~ (a->b), q ~ (f a->f b)}

To use this as a container type, the f in fmapA's signature needs to unify with (->) p. That's the function functor. So, despite having three polymorphic fmaps here, one of the functors is already predetermined by the expression. Therefore, it would be better to immediately resolve the polymorphism that only makes it more difficult to understand, and replace it with the definition of that particular functor instance, which turns out to be rather simple:

instance Functor ((->) a) where
  fmap = (.)

So, that reduces our expression to (.) fmapB fmapC – or, as it's preferrably written,

   fmapB . fmapC

Which is a far more sensible thing to write in actual code, and has been discussed previously on StackOverflow.