如何理解 Haskell 中 (fmap fmap fmap) 的类型？

Question

在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 的类型吗？

- Hao Yang

---

这能解决你的问题吗？如何使(fmap . fmap)通过类型检查。 - Bergi

参见 https://dev59.com/34rda4cB1Zd3GeqPPrBq，https://dev59.com/s2oy5IYBdhLWcg3wKq0S，https://dev59.com/eYjca4cB1Zd3GeqPv2AM 和 https://dev59.com/QmkMtIcB2Jgan1znbNTX - Bergi

如果你推导出类型，你会发现 fmap fmap 中的 f1 变成了函数函子。也就是说：(->) (a -> b) 在 fmap fmap fmap 中。 - lsmor

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。我认为你可以从这里继续，现在考虑 g=fmap` 的类型。 - chi

请参见 https://discourse.haskell.org/t/a-little-curiosity/3829 - michid

Answer 1

为了清晰明了，让我们介绍一下

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)}

要将此用作容器类型，fmapA 签名中的 f 需要与 (->) p 统一。这就是所谓的 函数函子。因此，尽管这里有三个多态的 fmap，但其中一个函子已经被表达式预定了。因此，最好立即解决只会使其更难理解的多态性，并用该特定函子实例的定义替换它，这实际上相当简单：

instance Functor ((->) a) where
  fmap = (.)

因此，我们的表达式可以简化为(.) fmapB fmapC - 或者更好地写成：

   fmapB . fmapC

在实际编码中，这是一个更明智的写法，并且已经在StackOverflow上讨论过。

- leftaroundabout

Answer 2

{-# 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 = (.) 实例化为 reader monad (.. ->)，难怪你觉得它很复杂。如果你看一下 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

- Iceland_jack