算法 W（或 Haskell）中的函数参数不是多态的吗？

Question

我正在为一种玩具语言实施算法 W。我遇到了一个我认为会进行类型检查的案例，但事实并非如此。我在 Haskell 中尝试了同样的方法，但令我惊讶的是它在那里也不起作用。

> (\id -> id id 'a') (\x -> x)
Couldn't match type ‘Char -> t’ with ‘Char’
Expected type: Char -> t
Actual type: (Char -> t) -> Char -> t

我认为这id将是多态的，但似乎不是。请注意，如果id使用 let 而不是作为参数传递定义，则此示例有效：

let id x = x in id id 'a'
'a'
:: Char

在查看算法 W 的推理规则时，这是有道理的，因为它具有 let 表达式的泛化规则。

但我想知道这是否有任何原因？函数参数不能被泛化，以便它可以多态使用吗？

Answer 1

泛化 lambda 绑定变量的问题是它需要更高阶的多态性。拿你的例子来说：

(\id -> id id 'a')

如果这里的类型id是forall a. a -> a，那么整个 lambda 表达式的类型一定是(forall a. a -> a) -> Char，这是一个 2 级类型。

除了该技术点之外，还有一个论点，即较高排名的类型非常不常见，因此与其推断非常不常见的类型，不如说用户更有可能犯了错误。