为什么两个具有不同类型变量的多态高阶函数在类型方面是等价的？
Why are two polymorphic higher order functions with different type vars equivalent regarding their types?
来自 Javascript 我了解到 Haskell 的列表类型强制执行同类列表。现在令我惊讶的是，以下不同的函数类型满足此要求：
f :: (a -> a) -> a -> a
f g x = g x
g :: (a -> b) -> a -> b
g h x = h x
let xs = [f, g] -- type checks
尽管 g 比 f 适用范围更广：
f(\x -> [x]) "foo" -- type error
g(\x -> [x]) "foo" -- type checks
(a -> a) 不应与 (a -> b) 区别对待。在我看来，后者似乎是前者的亚型。但是 Haskell 中没有子类型关系，对吗？那么为什么这样做有效？
Haskell 是静态类型的，但这并不意味着它是 Fortran。每种类型都必须在编译时得到固定，但不一定在单个定义中。 f和g的类型都是polymorphic。对此的一种解释是 f 不仅仅是一个函数，而是一整套重载函数。喜欢（在 C++ 中）
int f (function<int(int)> g, int x) { return g(x); }
char f (function<char(char)> g, char x) { return g(x); }
double f (function<double(double)> g, double x) { return g(x); }
...
当然，实际生成 所有这些函数 是不切实际的，因此在 C++ 中，您可以将其编写为 模板
template <typename T>
T f (function<T(T)> g, T x) { return g(x); }
...意思是，每当编译器找到 f 如果你的项目代码，它会找出 T 在特定情况下是什么，然后创建一个具体的 模板实例化（固定到具体类型的单态函数，就像我上面写的示例一样）并且只在运行时使用具体实例化。
这两个模板函数的具体实例可能具有相同的类型，即使模板看起来有点不同。
现在，Haskell 的参数多态性的解析与 C++ 模板略有不同，但至少在您的示例中它们是相同的：g 是一整套函数，包括实例化 g :: (Int -> Char) -> Int -> Char（与 f 的类型不兼容）以及 g :: (Int -> Int) -> Int -> Int，这是。当您将 f 和 g 放在一个列表中时，编译器会自动意识到只有类型与 f 兼容的 g 的子家族与此处相关。
是的，这确实是一种子类型化形式。当我们说“Haskell 没有子类型”时，我们的意思是任何 具体 (Rank-0) 类型与所有其他 Rank-0 类型不相交，但是 多态类型 可能重叠。
@leftroundabout 的回答很可靠；这里有一个更技术性的补充回答。
是一种在Haskell中起作用的子类型关系：System F“通用实例”关系。这是编译器在根据其签名检查函数的推断类型时使用的内容。基本上，函数的推断类型必须 至少与其签名 一样多态：
f :: (a -> a) -> a -> a
f g x = g x
这里f的推断类型是forall a b. (a -> b) -> a -> b，和你给的g的定义一样。但是签名限制更多：它添加约束a ~ b（a等于b）。
Haskell 通过首先用 Skolem 类型变量 替换签名中的类型变量来检查这一点——这些是新的唯一类型常量，它们只与自身（或类型变量）。我将使用符号 $a 来表示 Skolem 常数。
forall a. (a -> a) -> a -> a
($a -> $a) -> $a -> $a
当您意外地拥有一个“超出其范围”的类型变量时，您可能会看到对“rigid, Skolem”类型变量的引用：它在引入它的 forall 量词之外使用。
接下来，编译器执行包含检查。这本质上与正常的类型统一相同，其中 a -> b ~ Int -> Char 给出 a ~ Int 和 b ~ Char；但因为它是子类型关系，所以它也考虑了函数类型的协变和逆变。如果 (a -> b) 是 (c -> d) 的子类型，则 b 必须是 d 的子类型（协变），但 a 必须是 c 的超类型（逆变）。
{-1-}(a -> b) -> {-2-}(a -> b) <: {-3-}($a -> $a) -> {-4-}($a -> $a)
{-3-}($a -> $a) <: {-1-}(a -> b) -- contravariant (argument)
{-2-}(a -> b) <: {-4-}($a -> $a) -- covariant (result)
编译器生成以下约束：
$a <: a -- contravariant
b <: $a -- covariant
a <: $a -- contravariant
$a <: b -- covariant
并统一求解：
a ~ $a
b ~ $a
a ~ $a
b ~ $a
a ~ b
因此推断类型 (a -> b) -> a -> b 至少与签名 (a -> a) -> a -> a 一样多态。
当你写 xs = [f, g] 时，正常的统一开始：你有两个签名：
forall a. (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
这些是实例化的，带有新的类型变量：
(a1 -> a1) -> a1 -> a1
(a2 -> b2) -> a2 -> b2
然后统一：
(a1 -> a1) -> a1 -> a1 ~ (a2 -> b2) -> a2 -> b2
a1 -> a1 ~ a2 -> b2
a1 -> a1 ~ a2 -> b2
a1 ~ a2
a1 ~ b2
最终解决并推广：
forall a1. (a1 -> a1) -> a1 -> a1
所以 g 的类型变得不太通用，因为它被限制为与 f 具有相同的类型。因此，xs 的推断类型将是 [(a -> a) -> a -> a]，因此您在编写 [f (\x -> [x]) "foo" | f <- xs] 时会遇到与编写 f (\x -> [x]) "foo" 相同的类型错误；即使 g 更通用，您也隐藏了一些通用性。
现在您可能想知道为什么要为函数提供比必要的更严格的签名。答案是——指导类型推断并产生更好的错误信息。
例如($)的类型是(a -> b) -> a -> b；但实际上这是 id :: c -> c 的限制性更强的版本！只需设置 c ~ a -> b。所以实际上你可以写 foo `id` (bar `id` baz quux) 而不是 foo $ bar $ baz quux，但是有了这个专门的恒等式函数，编译器就会清楚你 期望 使用它来应用函数参数，因此它可以更早地退出并在您犯错时为您提供更具描述性的错误消息。
来自 Javascript 我了解到 Haskell 的列表类型强制执行同类列表。现在令我惊讶的是，以下不同的函数类型满足此要求：
f :: (a -> a) -> a -> a
f g x = g x
g :: (a -> b) -> a -> b
g h x = h x
let xs = [f, g] -- type checks
尽管 g 比 f 适用范围更广：
f(\x -> [x]) "foo" -- type error
g(\x -> [x]) "foo" -- type checks
(a -> a) 不应与 (a -> b) 区别对待。在我看来，后者似乎是前者的亚型。但是 Haskell 中没有子类型关系，对吗？那么为什么这样做有效？
Haskell 是静态类型的，但这并不意味着它是 Fortran。每种类型都必须在编译时得到固定，但不一定在单个定义中。 f和g的类型都是polymorphic。对此的一种解释是 f 不仅仅是一个函数，而是一整套重载函数。喜欢（在 C++ 中）
int f (function<int(int)> g, int x) { return g(x); }
char f (function<char(char)> g, char x) { return g(x); }
double f (function<double(double)> g, double x) { return g(x); }
...
当然，实际生成 所有这些函数 是不切实际的，因此在 C++ 中，您可以将其编写为 模板
template <typename T>
T f (function<T(T)> g, T x) { return g(x); }
...意思是，每当编译器找到 f 如果你的项目代码，它会找出 T 在特定情况下是什么，然后创建一个具体的 模板实例化（固定到具体类型的单态函数，就像我上面写的示例一样）并且只在运行时使用具体实例化。
这两个模板函数的具体实例可能具有相同的类型，即使模板看起来有点不同。
现在，Haskell 的参数多态性的解析与 C++ 模板略有不同，但至少在您的示例中它们是相同的：g 是一整套函数，包括实例化 g :: (Int -> Char) -> Int -> Char（与 f 的类型不兼容）以及 g :: (Int -> Int) -> Int -> Int，这是。当您将 f 和 g 放在一个列表中时，编译器会自动意识到只有类型与 f 兼容的 g 的子家族与此处相关。
是的，这确实是一种子类型化形式。当我们说“Haskell 没有子类型”时，我们的意思是任何 具体 (Rank-0) 类型与所有其他 Rank-0 类型不相交，但是 多态类型 可能重叠。
@leftroundabout 的回答很可靠；这里有一个更技术性的补充回答。
是一种在Haskell中起作用的子类型关系：System F“通用实例”关系。这是编译器在根据其签名检查函数的推断类型时使用的内容。基本上，函数的推断类型必须 至少与其签名 一样多态：
f :: (a -> a) -> a -> a
f g x = g x
这里f的推断类型是forall a b. (a -> b) -> a -> b，和你给的g的定义一样。但是签名限制更多：它添加约束a ~ b（a等于b）。
Haskell 通过首先用 Skolem 类型变量 替换签名中的类型变量来检查这一点——这些是新的唯一类型常量，它们只与自身（或类型变量）。我将使用符号 $a 来表示 Skolem 常数。
forall a. (a -> a) -> a -> a
($a -> $a) -> $a -> $a
当您意外地拥有一个“超出其范围”的类型变量时，您可能会看到对“rigid, Skolem”类型变量的引用：它在引入它的 forall 量词之外使用。
接下来，编译器执行包含检查。这本质上与正常的类型统一相同，其中 a -> b ~ Int -> Char 给出 a ~ Int 和 b ~ Char；但因为它是子类型关系，所以它也考虑了函数类型的协变和逆变。如果 (a -> b) 是 (c -> d) 的子类型，则 b 必须是 d 的子类型（协变），但 a 必须是 c 的超类型（逆变）。
{-1-}(a -> b) -> {-2-}(a -> b) <: {-3-}($a -> $a) -> {-4-}($a -> $a)
{-3-}($a -> $a) <: {-1-}(a -> b) -- contravariant (argument)
{-2-}(a -> b) <: {-4-}($a -> $a) -- covariant (result)
编译器生成以下约束：
$a <: a -- contravariant
b <: $a -- covariant
a <: $a -- contravariant
$a <: b -- covariant
并统一求解：
a ~ $a
b ~ $a
a ~ $a
b ~ $a
a ~ b
因此推断类型 (a -> b) -> a -> b 至少与签名 (a -> a) -> a -> a 一样多态。
当你写 xs = [f, g] 时，正常的统一开始：你有两个签名：
forall a. (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
这些是实例化的，带有新的类型变量：
(a1 -> a1) -> a1 -> a1
(a2 -> b2) -> a2 -> b2
然后统一：
(a1 -> a1) -> a1 -> a1 ~ (a2 -> b2) -> a2 -> b2
a1 -> a1 ~ a2 -> b2
a1 -> a1 ~ a2 -> b2
a1 ~ a2
a1 ~ b2
最终解决并推广：
forall a1. (a1 -> a1) -> a1 -> a1
所以 g 的类型变得不太通用，因为它被限制为与 f 具有相同的类型。因此，xs 的推断类型将是 [(a -> a) -> a -> a]，因此您在编写 [f (\x -> [x]) "foo" | f <- xs] 时会遇到与编写 f (\x -> [x]) "foo" 相同的类型错误；即使 g 更通用，您也隐藏了一些通用性。
现在您可能想知道为什么要为函数提供比必要的更严格的签名。答案是——指导类型推断并产生更好的错误信息。
例如($)的类型是(a -> b) -> a -> b；但实际上这是 id :: c -> c 的限制性更强的版本！只需设置 c ~ a -> b。所以实际上你可以写 foo `id` (bar `id` baz quux) 而不是 foo $ bar $ baz quux，但是有了这个专门的恒等式函数，编译器就会清楚你 期望 使用它来应用函数参数，因此它可以更早地退出并在您犯错时为您提供更具描述性的错误消息。