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.

It degenerates pretty quickly into a cycle or something like it, but I've forgotten the exact formula. (Incidentally, lambdabot actually defines (.) as fmap.) — ehird
@ehird: I think you're right. It seems like fmap n = 4k times (for n at least 8) gives (map . map . map). I'm still curious about why this happens, though. Especially because the instances change. At n = 8 it's (.) (.) (.) (.) (.) map map map, while for n = 12 it's (.) (.) (.) (.) (.) (.) (.) (.) map (.) map map. — hammar

Daniel Fischer Daniel Fischer · Accepted Answer · 2012-01-05T05:23:00

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.

Fun with repeated fmap

2 Answers