如何推导Haskell中map . filter对应的泛型类型

首先为了避免不同函数的泛型变量重名干扰推导，我们先把所有用到的函数的类型变量重命名，确保唯一：

• 函数组合符 (.) 的类型重命名为：(.) :: (t2 -> t3) -> (t1 -> t2) -> t1 -> t3
• map 的类型重命名为：map :: (u -> v) -> [u] -> [v]
• filter 的类型重命名为：filter :: (w -> Bool) -> [w] -> [w]

首先回忆函数组合的定义：(f . g) x = f (g x)，因此 map . filter 等价于 \p -> map (filter p)，我们基于这个结构做类型匹配：

1. (.) 接收的第一个参数是 map，需要匹配 (.) 第一个参数的类型 t2 -> t3。因为Haskell的函数都是柯里化的，map 可以看作接收一个函数参数、返回另一个单参数函数的结构：map :: (u -> v) -> ([u] -> [v])，因此可以直接匹配得到：
   • t2 = u -> v
   • t3 = [u] -> [v]
2. (.) 接收的第二个参数是 filter，需要匹配 (.) 第二个参数的类型 t1 -> t2。同样把 filter 拆成柯里化的单参数结构：filter :: (w -> Bool) -> ([w] -> [w])，匹配得到：
   • t1 = w -> Bool
   • t2 = [w] -> [w]
3. 现在我们得到了两个关于 t2 的相等约束，合并两个约束做类型匹配：
   • 从map得到 t2 = u -> v，从filter得到 t2 = [w] -> [w]，因此可以推出 u = [w]、v = [w]
4. 最后把所有约束代入 (.) 最终返回的函数类型 t1 -> t3：
   • t1 是 w -> Bool
   • t3 原本是 [u] -> [v]，代入 u = [w]、v = [w] 后得到 [[w]] -> [[w]]
   • 因此组合后函数的类型为 (w -> Bool) -> [[w]] -> [[w]]，和你看到的结果完全一致，只是把变量名w换成了常用的a而已。

疑问解答 #

1. 为什么会出现二维列表？
   因为filter p返回的函数类型是[a] -> [a]，这个函数会作为map的第一个参数。map要求传入的函数能处理列表的元素类型，因此map要处理的输入列表的元素就必须是[a]类型，输入列表自然就是[[a]]二维列表，输出也对应是[[a]]。
   举个实际运行的例子：

   (map . filter) even [[1,2,3],[4,5,6]]
   -- 等价于 map (filter even) [[1,2,3],[4,5,6]]
   -- 运行结果：[[2],[4,6]]
   

2. 为什么组合后只需要传一个函数参数？
   你之前的误解是以为需要分别给filter和map传两个函数参数，但实际上filter接收的第一个参数p :: a->Bool就是组合函数的第一个参数，这个参数传入后返回的[a]->[a]函数会直接作为map的第一个参数，不需要再额外给map传函数，因此组合后的函数只需要接收一个函数参数，再加最后的二维列表参数即可。

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