函数g = (.).(.)的类型是什么？如何推导该函数的对应类型？

前置基础：(.) 函数组合子的定义与类型 #

Haskell 中函数组合运算符 (.) 的定义为：

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)

它的作用是将两个单参数函数组合，将第二个函数的输出作为第一个函数的输入。

推导步骤 #

方法1：逐层展开表达式 #

我们直接按照(.)的定义对(.).(.)做等价展开：

1. 中缀表达式 f . g 等价于 (.) f g，因此 (.).(.) 等价于 (.) (.) (.)
2. 逐层展开组合定义后可以得到等价的lambda表达式：\f g x y -> f (g x y)

现在我们给这个lambda的每个参数分配类型：

• 最终输出的类型为 b，它是函数 f 的输出，因此 f 的类型为 a -> b，其中 a 是f的输入类型
• f的输入是 g x y 的输出，因此 g 的输出类型为 a
• g 接收两个参数 x 和 y，我们给它们分配类型 c 和 d，因此 g 的类型为 c -> d -> a
• 剩下的两个参数 x、y 的类型对应 c、d，最终返回 b

把所有类型按参数顺序组合，就得到完整的类型签名：
(a -> b) -> (c -> d -> a) -> c -> d -> b
和你查询到的结果完全一致。

方法2：类型变量匹配推导 #

为了避免同名变量冲突，我们给表达式中三个不同位置的(.)分配独立的类型变量：

1. 外层作为高阶函数的(.)（记为F）类型：F :: (u -> v) -> (w -> u) -> w -> v
2. 第一个参数位置的(.)（记为f1）类型：f1 :: (a -> b) -> (c -> a) -> c -> b
3. 第二个参数位置的(.)（记为f2）类型：f2 :: (d -> e) -> (f -> d) -> f -> e

首先将f1传入F，F的第一个参数要求类型为u -> v，和f1的类型匹配可得：
u ~ (a -> b)，v ~ (c -> a) -> c -> b
因此F f1的类型为：(w -> (a -> b)) -> w -> (c -> a) -> c -> b

再将f2传入F f1，F f1的参数要求类型为w -> (a -> b)，和f2的类型匹配可得：
w ~ (d -> e)，a ~ (f -> d)，b ~ (f -> e)
将匹配结果代入返回类型，替换变量名后即可得到最终的类型签名：(a -> b) -> (c -> d -> a) -> c -> d -> b

功能验证 #

这个函数的作用是把单参数函数适配到双参数函数的输出上，举个实际用例：

• 双参数加法函数 add :: Int -> Int -> Int
• 单参数转字符串函数 show :: Int -> String
• (.).(.) show add 得到的函数类型为 Int -> Int -> String，输入两个整数会返回它们相加后的字符串结果，和我们推导的类型完全匹配。

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