重复fmap的乐趣

Question

我在玩弄玩家,我发现了一些有趣的东西:

平凡的,id可以在类型中实例化(a -> b) -> a -> b.

使用我们拥有的列表仿函数fmap :: (a -> b) -> [a] -> [b],它与之相同map.

在((->) r)函子(from Control.Monad.Instances)的情况下,fmap是函数组合,所以我们可以实例化fmap fmap fmap :: (a -> b) -> [[a]] -> [[b]],这相当于(map . map).

有趣的是,fmap八次给我们(map . map . map)!

所以我们有

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

这种模式会继续吗？为什么/为什么不呢？是否有一个公式表示fmap我需要在n次嵌套列表上映射函数的数量？

我尝试编写一个测试脚本来搜索n = 4的解决方案,但GHC在40 fmap秒左右开始吃太多内存.

Answer 1

我无法解释为什么,但这是周期的证明:

假设k >= 2和fmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b,其中Fx代表未知数/任意Functor.fmap^n代表fmap应用于n-1 fmaps,而不是n重复迭代.感应开始可以通过手工验证或查询ghci.

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

统一用- >乙产量a = x -> y,b = F4 x -> F4 y,所以

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

现在,fmap^(4k+2)我们必须统一F1 F2 F3 (x -> y)使用(a -> b) -> F5 a -> F5 b.
因此F1 = (->) (a -> b),F2 F3 (x -> y)必须与之统一F5 a -> F5 b.
因此F2 = (->) (F5 a)和F3 (x -> y) = F5 b,即F5 = F3和b = x -> y.结果是

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

对于fmap^(4k+3),我们必须统一a -> (x -> y)使用(m -> n) -> F6 m -> F6 n),给予a = m -> n,
x = F6 m和y = F6 n,因此

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

最后,我们必须统一F3 (m -> n)使用(a -> b) -> F7 a -> F7 b,所以F3 = (->) (a -> b),m = F7 a和n = F7 b,因此

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

并且循环完成.当然,结果来自于查询ghci,但也许推导可以解释它是如何工作的.