Haskell嵌套fmap的类型统一问题解析求助

核心前提：函数类型是Functor实例 #

Haskell中，函数类型(->) r（即r -> *）是Functor的实例，它的fmap实现就是函数复合：

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

也就是说，当h是函数时，fmap g h等价于g . h，这是理解该问题的关键。

逐步推导类型 #

先明确各组件的类型（替换部分变量避免冲突）：

1. 基础fmap类型：

   fmap :: Functor F => (X -> Y) -> F X -> F Y
   

2. fmap foo的类型：

   fmap foo :: (Functor f, Num b) => f c -> f b
   

3. foo的类型：

   foo :: Num a => p -> a
   

步骤1：匹配外层fmap的第一个参数 #

外层fmap的第一个参数要求是X -> Y，而fmap foo的类型是f c -> f b，直接匹配得：

• X = f c
• Y = f b
  此时外层fmap被特化为：

fmap :: Functor F => (f c -> f b) -> F (f c) -> F (f b)

步骤2：匹配外层fmap的第二个参数 #

外层fmap的第二个参数需要是F (f c)，我们传入的foo类型是Num a => p -> a。这里将F (f c)与p -> a匹配：

• 函数类型p -> a本质是(->) p a，因此F就是(->) p（对应F (f c)为p -> f c）
• 由此可得a = f c，结合foo的Num a约束，推导出需要Num (f c)（重命名变量后为Num (f a)）

步骤3：推导返回类型 #

外层fmap的返回类型是F Y，代入F = (->) p和Y = f b，得到p -> f b。

整合约束与最终类型 #

合并所有推导约束：

• 内层fmap foo需要Functor f
• fmap foo需要Num b
• foo作为F (f c)时需要Num (f a)

最终得到的类型为：

fmap (fmap foo) foo :: (Functor f, Num b, Num (f a)) => p -> f b

直观理解 #

从函数复合角度看，fmap (fmap foo) foo等价于(fmap foo) . foo：

• foo接收p类型参数，返回Num实例化的f a类型值
• fmap foo接收f a类型值，返回f b类型值
• 复合后整体接收p，返回f b，完全符合推导结果。

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