haskell 中作为参数的函数的多态类型？

Question

我正在尝试定义以下函数的多态类型：

flip f x y = f y x

我的想法如下：

1. flip的第一个参数，f有两个参数，所以(t1 -> t2 -> t3)

2. flip的第二个参数，x的类型是t1 因为 f 函数中的参数 t1.

3. flip的第三个参数，y类型为t3 因为 f 函数中的参数 t3.

4. 不知道整体的多态类型return.

但是当我检查 ghci 中的类型时，我得到：

flip :: (t2 -> t1 -> t) -> t1 -> t2 -> t

有人可以帮忙看看这个例子是怎么回事吗？

谢谢

Answer 1

你的第二个假设是错误的:

2nd parameter of flip, x is of type t1 because of the parameter t1 inside f function.

我们先来分析一下函数：

flip f x y = f y x

我们看到 flip 的头部有三个参数。所以我们首先制作类型：

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

当然，我们现在的目标是填写类型。有：

f :: a
x :: b
y :: c
flip f x y :: d

我们在右手边看到：

(f y) x

所以这意味着 f 是一个以 y 作为输入的函数。所以这意味着 a 与 c -> e 是同一类型（或更短的 a ~ c -> e）。

所以现在：

flip :: (c -> e) -> (b -> (c -> d))
f :: (c -> e)
x :: b
y :: c

此外我们还看到：

(f x) y

所以 (f x) 的结果是另一个函数，输入 y。所以这意味着 e ~ b -> f。因此：

flip :: (c -> (b -> f)) -> (b -> (c -> d))
f :: c -> (b -> f)
x :: b
y :: c

最后我们看到(f y) x是flip f x y的结果。所以这意味着 (f y) x 的结果类型与 d 的类型相同。所以这意味着 f ~ d。这意味着：

flip :: (c -> (b -> d)) -> (b -> (c -> d))

或者如果我们删除一些多余的括号：

flip :: (c -> b -> d) -> b -> c -> d

Answer 2

这只是求解方程组的问题。首先，分配未知类型：

f : a1
x : a2
y : a3

接下来，f 应用于 y。因此，f 必须是一个函数类型，其参数类型与 y 相同，即

f : a1 = a3 -> a4
f y : a4

同样，f y被应用到x，所以

f y : a4 = a2 -> a5
f y x : a5

将其代回，我们得到

f : a3 -> a2 -> a5
x : a2
y : a3

我们可以重命名这些类型

t2 = a3
t1 = a2
t  = a5

并得到

f : t2 -> t1 -> t
x : t1
y : t2

函数体是f y x，类型是t = a5。