如何推导Haskell中(fmap fmap fmap)的类型？

我们从已知类型出发，逐步替换推导：

1. 基础类型回顾 #

先明确核心函数的类型：

• fmap 的基础类型：

  fmap :: Functor f => (a -> b) -> f a -> f b
  

• 已推导的 fmap fmap 类型：

  fmap fmap :: (Functor f1, Functor f2) => f1 (a -> b) -> f1 (f2 a -> f2 b)
  

2. 分析结构 #

fmap fmap fmap 等价于 (fmap fmap) fmap，即把第三个 fmap 作为参数传给 fmap fmap。我们需要让第三个 fmap 的类型匹配 fmap fmap 的参数类型 f1 (a -> b)。

3. 匹配参数类型 #

第三个 fmap 的类型是：

fmap :: Functor f3 => (c -> d) -> f3 c -> f3 d

这个类型是函数类型 (c -> d) -> (f3 c -> f3 d)，而 Haskell 中函数类型 (r -> s) 是函子 (->) r 的实例（(->) r s 等价于 r -> s）。

对比 fmap fmap 的参数类型 f1 (a -> b)，做如下替换：

• 令 f1 = (->) (c -> d)（函子为函数类型）
• 令 a -> b = f3 c -> f3 d，因此 a = f3 c，b = f3 d

4. 代入得到结果类型 #

将替换代入 fmap fmap 的返回类型 f1 (f2 a -> f2 b)：

1. f1 X 等价于 (c -> d) -> X（因为 f1 是 (->) (c -> d)）
2. X = f2 a -> f2 b，替换 a 和 b 后得到 X = f2 (f3 c) -> f2 (f3 d)

组合后得到：

(c -> d) -> f2 (f3 c) -> f2 (f3 d)

最后统一重命名类型变量（c→a，d→b，f3→f2，f2→f1），就得到和 GHCi 一致的结果：

fmap fmap fmap :: (Functor f1, Functor f2) => (a -> b) -> f1 (f2 a) -> f1 (f2 b)

内容的提问来源于stack exchange，提问作者Hao Yang