Fun with repeated fmap

Solution 1:

I can't explain why, but here's the proof of the cycle:

Assume k >= 2 and fmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b, where Fx stands for an unknown/arbitrary Functor. fmap^n stands for fmap applied to n-1 fmaps, not n-fold iteration. The induction's start can be verified by hand or querying ghci.

fmap^(4k+1) = fmap^(4k) fmap
fmap :: (x -> y) -> F4 x -> F4 y

unification with a -> b yields a = x -> y, b = F4 x -> F4 y, so

fmap^(4k+1) :: F1 F2 F3 (x -> y) -> F1 F2 F3 (F4 x -> F4 y)

Now, for fmap^(4k+2) we must unify F1 F2 F3 (x -> y) with (a -> b) -> F5 a -> F5 b.
Thus F1 = (->) (a -> b) and F2 F3 (x -> y) must be unified with F5 a -> F5 b.
Hence F2 = (->) (F5 a) and F3 (x -> y) = F5 b, i.e. F5 = F3 and b = x -> y. The result is

fmap^(4k+2) :: F1 F2 F3 (F4 x -> F4 y)
             = (a -> (x -> y)) -> F3 a -> F3 (F4 x -> F4 y)

For fmap^(4k+3), we must unify a -> (x -> y) with (m -> n) -> F6 m -> F6 n), giving a = m -> n,
x = F6 m and y = F6 n, so

fmap^(4k+3) :: F3 a -> F3 (F4 x -> F4 y)
             = F3 (m -> n) -> F3 (F4 F6 m -> F4 F6 n)

Finally, we must unify F3 (m -> n) with (a -> b) -> F7 a -> F7 b, so F3 = (->) (a -> b), m = F7 a and n = F7 b, therefore

fmap^(4k+4) :: F3 (F4 F6 m -> F4 F6 n)
             = (a -> b) -> (F4 F6 F7 a -> F4 F6 F7 b)

and the cycle is complete. Of course the result follows from querying ghci, but maybe the derivation sheds some light on how it works.

Solution 2:

I'll give a slightly simpler answer: map is a specialization of fmap and (.) is also a specialization of fmap. So, by substitution, you get the identity you discovered!

If you're interested in going further, Bartosz Milewski has a nice writeup that uses the Yoneda Lemma to make explicit why function composition is a monad.