Как (fmap. Fmap) typechecks

Ответ 1

Сначала измените имена типов переменных на уникальные:

(.)  :: (a -> b) -> (r -> a) -> (r -> b)
fmap :: Functor f => (c -> d) -> f c -> f d
fmap :: Functor g => (x -> y) -> g x -> g y

Теперь первый параметр . имеет тип a -> b и мы приводим аргумент типа (c -> d) -> (f c -> f d), поэтому a - c -> d и b - f c -> f d. Итак, до сих пор мы имеем:

(.) :: Functor f => -- Left operand
                    ((c -> d) -> (f c -> f d)) ->
                    -- Right operand
                    (r -> (c -> d)) ->
                    -- Result
                    (r -> (f c -> f d))

Второй параметр . имеет тип r -> a aka r -> (c -> d), а аргумент, который мы приводим, имеет тип (x -> y) -> (g x -> g y), поэтому r становится x -> y, c становится g x и d становится g y. Итак, теперь мы имеем:

(.)       :: (Functor f, Functor g) => -- Left operand
                                       ((g x -> g y) -> (f (g x) -> f (g y))) -> 
                                       -- Right operand
                                       ((x -> y) -> (g x -> g y)) ->
                                       -- Result
                                       (x -> y) -> f (g x) -> f (g y)
fmap.fmap :: (Functor f, Functor g) => (x -> y) -> f (g x) -> f (g y)

Ответ 2

Выражение fmap . fmap имеет два экземпляра fmap, которые могут, в принципе, иметь разные типы. Так что пусть их типы

fmap :: (x -> y) -> (g x -> g y)
fmap :: (u -> v) -> (f u -> f v)

Наша задача - унифицировать типы (что соответствует появлению отношений равенства между этими переменными типа), так что правая часть первого fmap совпадает с левой частью второго fmap. Надеюсь, вы увидите, что если вы установите u = g x и v = g y, вы получите

fmap :: (  x ->   y) -> (   g x  ->    g y )
fmap :: (g x -> g y) -> (f (g x) -> f (g y))

Теперь тип компоновки

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Чтобы сделать это, вы можете выбрать a = x -> y и b = g x -> g y и c = f (g x) -> f (g y), чтобы тип можно было записать

(.) :: ((g x -> g y) -> (f (g x) -> f (g y)))    ->    ((x -> y) -> (g x -> g y))    ->    ((x -> y) -> (f (g x) -> f (g y)))

который довольно громоздкий, но это просто специализация исходной сигнатуры типа для (.). Теперь вы можете проверить, что все соответствует такому, что fmap . fmap typechecks.

Альтернативой является подход к нему с противоположного направления. Скажем, что у вас есть объект, имеющий два уровня функториальности, например

>> let x = [Just "Alice", Nothing, Just "Bob"]

и у вас есть функция, которая добавляет удары в любую строку

bang :: String -> String
bang str = str ++ "!"

Вы хотите добавить удар по каждой из строк в x. Вы можете перейти от String -> String к Maybe String -> Maybe String с одним уровнем fmap

fmap bang :: Maybe String -> Maybe String

и вы можете перейти к [Maybe String] -> [Maybe String] с другим приложением fmap

fmap (fmap bang) :: [Maybe String] -> [Maybe String]

Это делает то, что мы хотим? Ад, да!

>> fmap (fmap bang) x
[Just "Alice!", Nothing, Just "Bob!"]

Пусть напишите функцию утилиты fmap2, которая принимает любую функцию f и применяет к ней fmap дважды, чтобы мы могли просто написать fmap2 bang x. Это будет выглядеть как

fmap2 f x = fmap (fmap f) x

Вы можете отказаться от x с обеих сторон

fmap2 f = fmap (fmap f)

Теперь вы понимаете, что шаблон g (h x) совпадает с (g . h) x, поэтому вы можете написать

fmap2 f = (fmap . fmap) f

чтобы теперь вы могли отбросить f с обеих сторон

fmap2 = fmap . fmap

которая является интересующей вас функцией. Таким образом, вы видите, что fmap . fmap просто принимает функцию и дважды применяет к ней fmap, чтобы ее можно было снять с двух уровней функториальности.

Ответ 3

Старый вопрос, но для меня, концептуально, fmap представляет "принятие a -> b и приведение его" на один уровень вверх "на f a -> f b".

Итак, если у меня есть a -> b, я могу fmap дать мне f a -> f b.

Если у меня был f a -> f b, я могу fmap снова дать мне g (f a) -> g (f a). Поднимите функцию f a -> f b на новые высоты - новый уровень.

Итак, "fmapping" один раз поднимает функцию один раз. fmapping дважды лифты, которые подняли функцию... так что двойной подъем.

Вставьте язык синтаксиса haskell:

f                    ::         a   ->         b
fmap f               ::       f a   ->       f b
fmap (fmap f)        ::    g (f a)  ->    g (f b)
fmap (fmap (fmap f)) :: h (g (f a)) -> h (g (f b))

Обратите внимание, как каждый следующий fmap поднимает исходный a -> b на новый уровень. Таким образом,

fmap               :: (a -> b) -> (      f a  ->        f b  )
fmap . fmap        :: (a -> b) -> (   g (f a) ->     g (f b) )
fmap . fmap . fmap :: (a -> b) -> (h (g (f a)) -> h (g (f a)))

Любая "функция более высокого порядка", которая возвращает функцию той же степени, что и ее вход, может это сделать. Возьмите zipWith :: (a -> b -> c) -> ([a] -> [b] -> [c]), который принимает функцию, берущую два аргумента, и возвращает новую функцию с двумя аргументами. Мы можем цепью zipWith так же:

f                   ::   a   ->   b   ->   c
zipWith f           ::  [a]  ->  [b]  ->  [c]
zipWith (zipWith f) :: [[a]] -> [[b]] -> [[c]]

Итак,

zipWith           :: (a -> b -> c) -> ( [a]  ->  [b]  ->  [c] )
zipWith . zipWith :: (a -> b -> c) -> ([[a]] -> [[b]] -> [[c]])

liftA2 работает практически так же:

f                 ::      a  ->      b  ->      c
liftA2 f          ::    f a  ->    f b  ->    f c
liftA2 (liftA2 f) :: g (f a) -> g (f b) -> g (f c)

Один довольно удивительный пример, который широко используется в современной реализации библиотеки объективов, traverse:

f                                ::         a   -> IO          b
traverse f                       ::       f a   -> IO (      f b  )
traverse (traverse f)            ::    g (f a)  -> IO (   g (f b) )
traverse (traverse (traverse f)) :: h (g (f a)) -> IO (h (g (f b)))

Итак, вы можете иметь такие вещи, как:

traverse            :: (a -> m b) -> (   f a  -> m (   f b ))
traverse . traverse :: (a -> m b) -> (g (f a) -> m (g (f b)))