haskell - Haskell 中的函数类型推断

Question

我正在为 Haskell 做练习题，其中一个问题是

test3 x y = x (x y)

我必须为此找到类型。

解决方案是

test3 :: (a -> a) -> a -> a

我不明白为什么解决方案中的变量都是 a，而不是将 x 和 y 称为两个不同的变量，如 a 和 b。有人可以解释一下，并通过如何找到这个问题的类型。

Answer 1

实际上，这是一个非常有趣的练习。它不需要任何特定于 Haskell 的知识——它实际上只是基本逻辑。

test3 x y = x (x y)

首先要注意的是 test3接受 2 个参数( x 和 y )并产生某种结果。所以类型必须是形式

a -> b -> c

只需弄清楚 a 是什么, b和 c是，或者至少它们之间存在什么关系。

所以让我们检查一下结果 x (x y)更详细。它告诉我们 x是一个可以取 y 的函数作为论据。我们说过 y有类型 b (这是一个完全任意的名称，但现在让我们坚持使用它) - 所以 x必须是一个接受 b 的函数并产生某种类型的结果。我们称该类型为 d目前。所以我们知道 test3的类型是形式

(b -> d) -> b -> c

最后，再次来自表达式 x (x y) ，我们看到 x必须采取 x y - 我们分配了类型 d - 并返回一个结果。而这个结果就是 test3的整体结果，我们选择调用它的类型 c .所以，在上面， x - 我们已经为其分配了类型 b -> d , 必须有类型 d -> c .唯一的办法 b -> d可以等于 d -> c如果 b , c和 d都是同一类型。 (因为函数的类型是由它们的输入类型和结果类型决定的。)所以 test3的整体类型必须是形式

(b -> b) -> b -> b

这正是您被告知的内容 - 最多重命名为 a至 b . (正如我所说，这些名称无论如何都是任意的 - 所以它不相关。)