Haskell中类型统一与函数应用及(fmap .)类型签名推导疑问

基础类型回顾 #

先明确两个核心函数的类型签名：

• fmap :: (x -> y) -> f x -> f y，本质等价于(x -> y) -> (f x -> f y)（Haskell函数类型默认右结合），表示接收一个函数x->y，返回另一个接收f x并返回f y的函数。
• (.) :: (b -> c) -> (a -> b) -> a -> c，函数组合算子，接收两个函数（第一个输入b输出c，第二个输入a输出b），返回一个输入a输出c的函数。

(fmap .)的正确类型推导 #

(fmap .)等价于(.) fmap，即把fmap作为第一个参数传给(.)，因此需要让fmap的类型匹配(.)的第一个参数类型b -> c：

1. fmap的整体类型是(x -> y) -> (f x -> f y)，这是一个“输入为x->y，输出为f x->f y”的函数，因此直接匹配b -> c可得：
   • b = x -> y（(.)第一个参数的输入类型）
   • c = f x -> f y（(.)第一个参数的输出类型）
2. 将b和c代入(.)的类型，得到：
   (a -> (x -> y)) -> a -> (f x -> f y)，去掉冗余括号后就是(a -> x -> y) -> a -> f x -> f y，和GHC推导的(a1 -> a2 -> b) -> a1 -> f a2 -> f b（变量重命名后）完全一致。

第一种分组错误的原因 #

你尝试将fmap拆分为x -> (y -> (f x -> f y))，这是对fmap类型的错误解读：

• fmap的第一个参数必须是完整的函数类型x->y，而非单个类型x。类型签名中(x -> y)是一个不可拆分的参数类型组，fmap从设计上就是接收函数作为第一个参数，用来将函数“提升”到函子上下文，因此不能把(x -> y)拆分为x和y作为独立的参数层级。

fmap 'c'报错的本质 #

fmap 'c'报错Couldn't match expected type 'a -> b' with actual type 'Char'，原因很直接：

• fmap的第一个参数类型要求是a->b（函数类型），但'c'是Char类型，不属于函数类型范畴，完全不匹配fmap的参数要求。fmap的设计目的是操作函数与函子，因此无法用非函数值部分应用它的第一个参数位。

带类型的lambda演算验证 #

用lambda表达式拆解更直观：

• fmap的lambda形式：\g -> \fx -> fmap g fx，类型为(x->y) -> (f x -> f y)
• (.)的lambda形式：\h -> \k -> \a -> h (k a)，类型为(b->c) -> (a->b) -> a->c
• 代入(.) fmap后得到：\k -> \a -> fmap (k a)
  • k的类型必须是a -> (x->y)（因为k a要作为fmap的第一个参数，即x->y类型）
  • fmap (k a)的类型是f x -> f y
  • 最终整体类型就是(a -> x->y) -> a -> f x -> f y，和正确推导结果一致。

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