有趣的重复的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吃太多的内存。

Answer 1

我无法解释为什么，但这是循环的certificate：

假设k >= 2且fmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b ，其中Fx代表未知/任意Functor 。 fmap^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 -> y ， b = 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 b与F1 F2 F3 (x -> y)
因此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) 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) 

最后，我们必须把(a -> b) -> F7 a -> F7 b与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得到的，但也许这个推导揭示了它如何工作。

Answer 2

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

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