haskell - Haskell 中的函数类型推断

Question

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

test3 x y = x (x y)

我必须为此找到类型。

解决方案是

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

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

标签： haskell

Answer 1

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

test3 x y = x (x y)

首先要注意的是，它test3需要 2 个参数（xand y）并产生某种结果。所以类型必须是形式

a -> b -> c

剩下的只是弄清楚它们之间存在什么a，b并且c是，或者至少是什么关系。

因此，让我们更详细地检查该结果x (x y)。它告诉我们这x是一个可以y作为参数的函数。我们已经说过 that yhas type b（这是一个完全任意的名称，但现在让我们坚持使用它） - 所以x必须是一个接受 ab并产生某种类型结果的函数。我们暂时称其为该类型d。所以我们知道的类型test3是形式

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

最后，再次从表达式x (x y)中，我们看到它x必须采用x y- 我们已经分配了类型d- 并返回一个结果。这个结果是 的整体结果test3，我们选择调用它的类型c。所以，在上面，x- 我们已经分配了 type b -> d，必须有 type d -> c。唯一b -> d可以等于的方法d -> c是 if b，c并且d都是相同的类型。（因为函数的类型是由它们的输入类型和结果类型决定的。）所以整体的类型test3必须是形式

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

这正是您被告知的内容 - 直到重命名为ato b。（正如我所说，这些名称无论如何都是任意的 - 所以它不相关。）