Как понять тип (fmap fmap fmap) в Haskell?
В Haskell у Functor есть функция fmap, тип которой:
ghci> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
Для меня имеет смысл то, что fmap поднимает функцию из типа a -> b в f a -> f b.
Тогда мне любопытно, что это за тип fmap fmap, поэтому я попробовал и получил кое-что странное:
ghci> :t fmap fmap
fmap fmap
:: (Functor f1, Functor f2) => f1 (a -> b) -> f1 (f2 a -> f2 b)
Хм, этот тип несколько сложен, но я могу объяснить это, заменив a на a -> b и b на f2 a -> f2 b.
Затем я хотел сделать еще один шаг вперед:
fmap fmap fmap
:: (Functor f1, Functor f2) => (a -> b) -> f1 (f2 a) -> f1 (f2 b)
О, подождите! Если собрать 3 fmap вместе, будет весело. Как это объяснить?
Может ли кто-нибудь помочь объяснить, как я могу получить тип fmap fmap fmap?
Если вы тренируете типы, вы получаете, что f1 в fmap fmap становится функтором функции. то есть: (->) (a -> b) в fmap fmap fmap
fmap g x требует x :: f a. Теперь в вашем случае g=fmap :: ... (что сейчас не имеет значения) и x :: (t->u)-> f2 t -> f2 u. Следовательно, нам нужно равенство типов f a = (t->u) -> f2 t -> f2 u, которое, если мы правильно напишем конструкторы типов в форме префикса, станет f a = (->) (t->u) (f2 t -> f2 u). Затем мы получаем f = (->) (t->u) и a = f2 t -> f2 u. I think you can continue from here, now taking into account the type of g=fmap`.
Смотрите также discourse.haskell.org/t/a-little-curiousity/3829
Ответы 2
Для наглядности представим
fmapA, fmapB, fmapC :: Functor f => (a -> b) -> f a -> f b
fmapA = fmapB = fmapC = fmap
и рассмотреть
fmapA fmapB fmapC :: ?
Забудьте немного о fmapB, начните с fmapA _ fmapC. Вы рассматриваете fmapC справа как контейнер, на который вы что-то наносите. Имеет ли это смысл? Ну посмотрите на тип в неинфиксной форме. Напомним, что x -> y -> z совпадает с x -> (y -> z), а p -> q совпадает с ((->) p) q, поэтому
fmapC :: ((->) p) q where {p ~ (a->b), q ~ (f a->f b)}
Чтобы использовать это как тип контейнера, f в подписи fmapA должен быть унифицирован с (->) p. Это функтор функции. Итак, несмотря на наличие здесь трех полиморфных fmap, один из функторов уже предопределен выражением. Поэтому было бы лучше сразу разрешить полиморфизм, который только усложняет понимание, и заменить его определением этого конкретного экземпляра функтора, что оказывается довольно простым:
instance Functor ((->) a) where
fmap = (.)
Таким образом, наше выражение сводится к (.) fmapB fmapC — или, как предпочтительнее писать,
fmapB . fmapC
Что гораздо разумнее писать в реальном коде, и это обсуждалось ранее на StackOverflow.
{-# Language BlockArguments #-}
{-# Language ScopedTypeVariables #-}
{-# Language TypeApplications #-}
fffmap
:: forall f g a b. ()
=> Functor f
=> Functor g
=> (a -> b)
-> (f (g a) -> f (g b))
fffmap = fmap fmap fmap
Полиморфная функция принимает тип в качестве аргумента. Квантификация forall. невидима и неявно решается путем унификации, но мы можем явно создать ее экземпляр с помощью приложения типа @...
Я использую блочные аргументы, что позволяет мне писать fmap fmap fmap как
do fmap
do fmap
do fmap
просто чтобы было понятнее. Вот как они на самом деле создаются:
fffmap
:: forall f g a b. ()
=> Functor f
=> Functor g
=> (a -> b)
-> (f (g a) -> f (g b))
fffmap =
do fmap @((->) (a -> b)) @(g a -> g b) @(f (g a) -> f (g b))
do fmap @f @(g a) @(g b)
do fmap @g @a @b
Первая fmap = (.) инстанцируется читающей монаде (.. ->), неудивительно, что она кажется вам сложной. Если вы посмотрите на тип f1, это сложно.
fffmap
:: forall f g a b.
Functor f
=> Functor g
=> (a -> b)
-> (f (g a) -> f (g b))
fffmap = f1 f2 f3 where
f1 :: ((g a -> g b) -> f (g a) -> f (g b)) -> ((a -> b) -> g a -> g b) -> (a -> b) -> f (g a) -> f (g b)
f1 = fmap
f2 :: (g a -> g b) -> (f (g a) -> f (g b))
f2 = fmap
f3 :: (a -> b) -> (g a -> g b)
f3 = fmap
Отвечает ли это на ваш вопрос? Как (fmap .fmap) проверяет типы