如何推导应用于恒等函数的应用程序的类型
How to derive the type of an applicator applied to the identity function
我想导出应用于身份函数的以下人为应用程序的类型。为此，我可能必须将第一个参数 (a -> [b]) 的类型部分与 id:
的类型统一起来
ap :: (a -> [b]) -> a -> [b]
id :: a -> a
a -> [b]
a0 -> a0 -- fresh type vars
a ~ a0 -- mappings
[b] ~ a0
a0 -> a0 -- substitution
这显然是错误的，因为预期的类型是 [b] -> [b]。统一中存在歧义，因为 a0 不能等同于 a 和 [b]，除了 a ~ [b]。但是告诉我用 [b] 代替 a 而不是相反的规则是什么，例如我必须用 ap :: ([a] -> b) -> [a] -> b 来代替。
我知道这是一个非常具体的问题，抱歉。希望它不会太混乱！
好的，新答案，因为我现在明白了所问的问题！重述问题：
给定
ap :: (a -> [b]) -> a -> [b]
id :: a -> a
解释表达式 ap id 的类型是如何导出的。
答案：
重命名变量：
ap :: (a -> [b]) -> a -> [b]
id :: a0 -> a0
统一：
(a -> [b]) ~ (a0 -> a0)
多次应用生成性，从 (->) 类型构造函数中提取参数：
a ~ a0
[b] ~ a0
应用 commutativity/transitivity 类型相等：
[b] ~ a
将已知的最具体的类型替换为ap和id
的类型
ap :: ([b] -> [b]) -> [b] -> [b]
id :: [b] -> [b]
[b] 是已知的最具体的类型，因为它提供了一些限制。该值必须是某物的列表。其他两个等效类型表达式只是表示任何类型。您可以将统一视为约束解决过程。您找到满足所提供约束的最大类型，在这种情况下等于 "it's a list of something"。
既然统一了类型，函数应用的类型就是函数结果的类型：
ap id :: [b] -> [b]
我明白为什么在这种情况下选择 [b] 看起来有点奇怪，因为三种类型表达式中只有一种有助于统一。不过，还有更多涉及约束来自多个地方的案例。
让我们考虑一个更高级的案例。这可能涉及一些你以前没有见过的东西。如果是这样，我很抱歉直接跳到最深处。
给定：
f1 :: (a -> b) -> f a -> f b
f2 :: p c d -> (e, c) -> (e, d)
统一f1和f2的类型。
让我们非常小心这个。首先，根据前缀应用重写所有类型。甚至 (->) 类型。这会很丑陋：
f1 :: (->) ((->) a b) ((->) (f a) (f b))
f2 :: (->) (p c d) ((->) ((,) e c) ((,) e d))
将生成性统一并应用到顶级 (->) 类型构造函数两次：
((->) a b) ~ (p c d)
((->) (f a) (f b)) ~ ((->) ((,) e c) ((,) e d))
并且，继续统一并应用生成性：
(->) ~ p
a ~ c
b ~ d
f a ~ (,) e c
f b ~ (,) e d
f ~ (,) e
好的，我们现在已经建立了一大堆约束。在 a 和 c 或 b 和 d 之间进行选择并不重要，因为它们受到等效约束。如果无关紧要，让我们选择更接近字母表开头的字母。 (->)比p更受约束，所以它赢在那里，(,) e比f更受约束。也称它为赢家。
然后改回中缀类型的构造函数，美化一下，统一类型为：
(a -> b) -> (e, a) -> (e, b)
注意两个起始类型中的每一个如何为最终的统一类型贡献一个约束。 f1 要求 f2 中的 p 类型更具体，f2 要求 f1 中的 f 类型更具体。
总的来说，这是一个超级机械的过程。它也很繁琐，需要精确跟踪您所知道的内容。我们主要将其留给编译器来处理是有原因的。不过，在出现问题并且您想自己仔细检查过程以了解编译器报告错误的原因时，它绝对有用。
我想导出应用于身份函数的以下人为应用程序的类型。为此，我可能必须将第一个参数 (a -> [b]) 的类型部分与 id:
ap :: (a -> [b]) -> a -> [b]
id :: a -> a
a -> [b]
a0 -> a0 -- fresh type vars
a ~ a0 -- mappings
[b] ~ a0
a0 -> a0 -- substitution
这显然是错误的，因为预期的类型是 [b] -> [b]。统一中存在歧义，因为 a0 不能等同于 a 和 [b]，除了 a ~ [b]。但是告诉我用 [b] 代替 a 而不是相反的规则是什么，例如我必须用 ap :: ([a] -> b) -> [a] -> b 来代替。
我知道这是一个非常具体的问题，抱歉。希望它不会太混乱！
好的，新答案，因为我现在明白了所问的问题！重述问题：
给定
ap :: (a -> [b]) -> a -> [b]
id :: a -> a
解释表达式 ap id 的类型是如何导出的。
答案：
重命名变量：
ap :: (a -> [b]) -> a -> [b]
id :: a0 -> a0
统一：
(a -> [b]) ~ (a0 -> a0)
多次应用生成性，从 (->) 类型构造函数中提取参数：
a ~ a0
[b] ~ a0
应用 commutativity/transitivity 类型相等：
[b] ~ a
将已知的最具体的类型替换为ap和id
ap :: ([b] -> [b]) -> [b] -> [b]
id :: [b] -> [b]
[b] 是已知的最具体的类型，因为它提供了一些限制。该值必须是某物的列表。其他两个等效类型表达式只是表示任何类型。您可以将统一视为约束解决过程。您找到满足所提供约束的最大类型，在这种情况下等于 "it's a list of something"。
既然统一了类型，函数应用的类型就是函数结果的类型：
ap id :: [b] -> [b]
我明白为什么在这种情况下选择 [b] 看起来有点奇怪，因为三种类型表达式中只有一种有助于统一。不过，还有更多涉及约束来自多个地方的案例。
让我们考虑一个更高级的案例。这可能涉及一些你以前没有见过的东西。如果是这样，我很抱歉直接跳到最深处。
给定：
f1 :: (a -> b) -> f a -> f b
f2 :: p c d -> (e, c) -> (e, d)
统一f1和f2的类型。
让我们非常小心这个。首先，根据前缀应用重写所有类型。甚至 (->) 类型。这会很丑陋：
f1 :: (->) ((->) a b) ((->) (f a) (f b))
f2 :: (->) (p c d) ((->) ((,) e c) ((,) e d))
将生成性统一并应用到顶级 (->) 类型构造函数两次：
((->) a b) ~ (p c d)
((->) (f a) (f b)) ~ ((->) ((,) e c) ((,) e d))
并且，继续统一并应用生成性：
(->) ~ p
a ~ c
b ~ d
f a ~ (,) e c
f b ~ (,) e d
f ~ (,) e
好的，我们现在已经建立了一大堆约束。在 a 和 c 或 b 和 d 之间进行选择并不重要，因为它们受到等效约束。如果无关紧要，让我们选择更接近字母表开头的字母。 (->)比p更受约束，所以它赢在那里，(,) e比f更受约束。也称它为赢家。
然后改回中缀类型的构造函数，美化一下，统一类型为：
(a -> b) -> (e, a) -> (e, b)
注意两个起始类型中的每一个如何为最终的统一类型贡献一个约束。 f1 要求 f2 中的 p 类型更具体，f2 要求 f1 中的 f 类型更具体。
总的来说，这是一个超级机械的过程。它也很繁琐，需要精确跟踪您所知道的内容。我们主要将其留给编译器来处理是有原因的。不过，在出现问题并且您想自己仔细检查过程以了解编译器报告错误的原因时，它绝对有用。