반복되는 fmap으로 재미

반복되는 fmap으로 재미

---

나는 펑 터들과 놀다가 흥미로운 것을 발견했습니다.

간단하게 id유형에서 인스턴스화 할 수 있습니다 (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)!

그래서 우리는

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 번 중첩 된 목록에 fmap대해 함수를 매핑하는 데 필요한 s에 대한 공식이 있습니까?

n = 4 케이스 에 대한 해결책을 찾기 위해 테스트 스크립트를 작성하려고 했지만 GHC는 약 40 fmap초에 너무 많은 메모리를 먹기 시작합니다 .

---

이유를 설명 할 수는 없지만 여기에주기의 증거가 있습니다.

가정 k >= 2및 fmap^(4k) :: (a -> b) -> F1 F2 F3 a -> F1 F2 F3 b경우, Fx알 수없는 / 임의의 약자 Functor. fmap^n- 접기 반복이 아닌 s 에 fmap적용됨을 의미합니다 . 유도의 시작은 손으로 확인하거나 ghci를 쿼리하여 확인할 수 있습니다.n-1 fmapn

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)우리는 통일해야한다 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를 쿼리 한 결과를 따르지만 아마도 파생은 그것이 어떻게 작동하는지에 대한 약간의 빛을 비춰 줄 것입니다.

---

나는 약간 간단한 답을주지 : map의 전문화가 fmap와 (.)입니다 도 의 전문화 fmap. 그래서, 대체함으로써 당신은 당신이 발견 한 정체성을 얻습니다!

더 나아가고 싶다면 Bartosz Milewski가 Yoneda Lemma를 사용하여 함수 구성이 모나드 인 이유를 명시 하는 멋진 글 을 작성했습니다.

참조 URL : https://stackoverflow.com/questions/8736995/fun-with-repeated-fmap