重复 fmap 的乐趣
我在玩仿函数时，注意到一些有趣的事情：
简单地说，id 可以在类型 (a -> b) ->; 上实例化。一个-> b.。
通过列表函子，我们有 fmap :: (a -> b) -> [一]-> [b]，与map相同。
对于 ((->) r) 函子（来自 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 时开始消耗太多内存。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我无法解释原因，但这是循环的证明：
假设
k >= 2和fmap^(4k) :: (a -> b) -> F1 F2 F3 a-> F1 F2 F3 b，其中Fx代表未知/任意Functor。fmap^n代表应用于n-1fmap的fmap，而不是n>-折叠迭代。感应的启动可以通过手动或查询 ghci 来验证。与 -> 统一b 产生 a = x -> y,
b = F4 x -> F4 y，所以现在，对于
fmap^(4k+2)，我们必须将F1 F2 F3 (x -> y)与( a->b）-> F5a-> 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+3)，我们必须统一a ->; (x -> y) 与
(m -> n) -> F6米-> F6 n)，给出a = m -> n,x = F6 m和y = F6 n，所以最后，我们必须将
F3 (m -> n)与( a->b）-> F7a->; F7 b，因此F3 = (->) (a -> b)、m = F7 a且n = F7 b< /code>，因此循环完成。当然，结果是通过查询 ghci 得出的，但也许这个推导可以揭示它的工作原理。
I can't explain why, but here's the proof of the cycle:
Assume
k >= 2andfmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b, whereFxstands for an unknown/arbitraryFunctor.fmap^nstands forfmapapplied ton-1fmaps, notn-fold iteration. The induction's start can be verified by hand or querying ghci.unification with a -> b yields
a = x -> y,b = F4 x -> F4 y, soNow, for
fmap^(4k+2)we must unifyF1 F2 F3 (x -> y)with(a -> b) -> F5 a -> F5 b.Thus
F1 = (->) (a -> b)andF2 F3 (x -> y)must be unified withF5 a -> F5 b.Hence
F2 = (->) (F5 a)andF3 (x -> y) = F5 b, i.e.F5 = F3andb = x -> y. The result isFor
fmap^(4k+3), we must unifya -> (x -> y)with(m -> n) -> F6 m -> F6 n), givinga = m -> n,x = F6 mandy = F6 n, soFinally, we must unify
F3 (m -> n)with(a -> b) -> F7 a -> F7 b, soF3 = (->) (a -> b),m = F7 aandn = F7 b, thereforeand the cycle is complete. Of course the result follows from querying ghci, but maybe the derivation sheds some light on how it works.
我会给出一个稍微简单一点的答案：
map是fmap的特化，(.)也是fmap的专业化。所以，通过替换，你就得到了你发现的身份！如果您有兴趣进一步了解，Bartosz Milewski 有一篇不错的文章 使用米田引理来明确为什么函数组合是一个 monad。
I'll give a slightly simpler answer:
mapis a specialization offmapand(.)is also a specialization offmap. So, by substitution, you get the identity you discovered!If you're interested in going further, Bartosz Milewski has a nice writeup that uses the Yoneda Lemma to make explicit why function composition is a monad.