Fun with repeated fmap

Question

I was playing around with functors, and I noticed something interesting:

Trivially, id can be instantiated at the type (a -> b) -> a -> b.

With the list functor we have fmap :: (a -> b) -> [a] -> [b], which is the same as map.

In the case of the ((->) r) functor (from Control.Monad.Instances), fmap is function composition, so we can instantiate fmap fmap fmap :: (a -> b) -> [[a]] -> [[b]], which is equivalent to (map . map).

Interestingly, fmap eight times gives us (map . map . map)!

So we have

0: id = id 1: fmap = map 3: fmap fmap fmap = (map . map) 8: fmap fmap fmap fmap fmap fmap fmap fmap = (map . map . map) 

Does this pattern continue? Why/why not? Is there a formula for how many fmaps I need to map a function over an n-times nested list?

I tried writing a test script to search for a solution to the n = 4 case, but GHC starts eating too much memory at around 40 fmaps.

Answer 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.