有趣的重复的fmap

我正在玩function游戏,我注意到一些有趣的事情:

普通的id可以在types(a -> b) -> a -> b实例化。

使用列表函子,我们有fmap :: (a -> b) -> [a] -> [b] ,它与map相同。

((->) r)函子(来自Control.Monad.Instances )中, fmap是函数组合, fmap fmap fmap :: (a -> b) -> [[a]] -> [[b]] ,相当于(map . map)

有趣的是, fmap八次给了我们(map . 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) 

这种模式是否继续? 为什么/为什么不呢? 有一个公式,我需要映射一个函数在n次嵌套列表中有多less个fmap

我尝试编写一个testing脚本来searchn = 4的解决scheme,但是GHC开始在大约40个fmap吃太多的内存。

我无法解释为什么,但这是循环的certificate:

假设k >= 2fmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b ,其中Fx代表未知/任意Functorfmap^n代表应用于n-1 fmap ,不代表n n-1 fmap迭代。 感应的开始可以通过手动或查询ghci来validation。

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

与a – > b统一产生a = x -> yb = F4 x -> F4 y

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

现在,对于fmap^(4k+2)我们必须将(a -> b) -> F5 a -> F5 bF1 F2 F3 (x -> y)
因此F1 = (->) (a -> b)F2 F3 (x -> y)必须与F5 a -> F5 b统一。
因此F2 = (->) (F5 a)F3 (x -> y) = F5 b ,即F5 = F3b = 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) fmap^(4k+3) a -> (x -> y) (m -> n) -> F6 m -> F6 n) ,给出a = m -> n
x = F6 my = F6 n ,所以

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

最后,我们必须把(a -> b) -> F7 a -> F7 bF3 (m -> n)合并(a -> b) -> F7 a -> F7 b F3 = (->) (a -> b)m = F7 an = F7 b ,因此

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

周期完成。 当然,结果是从查询ghci得到的,但也许这个推导揭示了它如何工作。

我会给出一个更简单的答案: mapfmap一个特殊化, (.) 也是 fmap一个特殊化。 所以,通过replace,你得到你发现的身份!

如果你有兴趣进一步研究,Bartosz Milewski有一个很好的写法 ,使用Yoneda引理明确了为什么函数组合是一个monad。