Веселье с повторным Fmap

Question

Я играл с функторами и заметил кое-что интересное:

Тривиально, 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)

Продолжается ли эта модель?Почему, почему нет?Есть ли формула для того, сколько 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 fmap с, а не n кратной итерации.Начало индукции можно проверить вручную или запросив ghci.

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, но, возможно, вывод проливает некоторый свет на то, как он работает.

Answer 2

Я дам несколько более простой ответ: map - это специализация fmap, а (.) - это , а также - специализация fmap.Таким образом, заменив, вы получите идентичность, которую вы обнаружили!

Если вы заинтересованы в дальнейшем продвижении, у Бартоша Милевского есть хорошая запись , в которой используется лемма Йонеды, чтобы ясно указать, почему состав функцииэто монада.