haskell - 计算 Haskell 函数的类型

Question

周末考试时在 Haskell 中手动计算给定函数的类型时遇到麻烦。

我了解以下基础知识:

• i x = x::t -> t
• k x y = x::t -> t1 -> t

但是在解决更复杂的问题时遇到困难，例如:

• 两个 f x = f (f x)
• s x y z = x z (y z)

任何解释将不胜感激!

Answer 1

在这两个示例中，您对函数类型的唯一提示来自于观察应用程序的运行情况。在 Haskell 应用程序中几乎没有任何语法，因此我将更明显地重写它们。

two f x = f(f(x))
s x y z = x(z)(y(z))

<小时/>

我们现在将通过逐步细化来发现这些函数的类型。例如，以 two 开头我们知道它接受两个参数，因此必须具有与(更一般的)类型一致的类型

two :: a -> b -> c

我们还知道a上面的类型变量实际上对应于一个函数，因为 f正在应用于 x和f(x) 。

two :: (a -> b) -> c -> d

自 f应用于x我们知道这里a和c必须相同。

two :: (a -> b) -> a -> d

既然我们申请了f再次查看结果 f(x)我们知道结果类型必须与输入类型相同

two :: (a -> a) -> a -> b

最后，调用 f 的结果是 two 的总结果所以d还必须等于 a

two :: (a -> a) -> a -> a

这使用了我们在定义中拥有的所有信息，并且是与 two 的定义兼容的最通用类型。 .

<小时/>

我们可以对 s 执行基本相同的过程。 。我们知道它有 3 个参数

s :: a -> b -> c -> d

我们知道第一个和第二个参数是某种函数。我们看到第二个参数应用于单个值，第一个参数应用于两个值。

s :: (a -> b -> c) -> (d -> e) -> f -> g

我们还知道两个函数的第一个输入是相同的(即每次都是z)。这让我们推断 a , d ，和f是同一类型

s :: (a -> b -> c) -> (a -> d) -> a -> e

我们还知道调用第二个函数的结果是第一个函数的第二个参数，因此b和d必须相同。

s :: (a -> b -> c) -> (a -> b) -> a -> e

最后，完全应用第一个函数的结果就是最终结果s所以c和e是一样的

s :: (a -> b -> c) -> (a -> b) -> a -> c

<小时/>

虽然这可能需要消化很多内容并且有点模糊，但需要强调的是，我用来解决这个问题的工具都是原始的。实际上，我引入了箭头 (->)当我看到该类型应用于某些值，因此必须是一定数量的参数的函数时，我通过遵循这些值的表达式来统一类型变量。这些工具足以推断简单函数的类型，例如 two和s .