嵌套通用量词的范围是如何确定的（更高级别的类型）？

Question

最初我假设函数类型的 LHS 上的嵌套通用量词的范围可以纯粹从句法上确定，即 (forall a. a -> b) -> Bool 括号内的所有内容都在同一范围内。然而，这个假设是错误的：

{-# LANGUAGE RankNTypes #-}

fun :: (forall a. [a] -> b) -> Bool
fun _ = undefined

arg :: c -> c
arg _ = undefined

r = fun arg -- type variable a would escape its scope

这是有道理的，因为在 fun 中，b 必须在 a 之前选择，因此是固定的或独立于 a。在统一期间，参数类型 c -> c 将强制 b 实例化为 [a0]。

因此，类型级别的范围界定可能更类似于术语级别的函数范围界定，其中结果值显然不是函数范围的一部分。换句话说，如果 b 不是函数类型的陪域，类型检查器就会通过。不幸的是，我无法提出支持我推理的注释。

一种更严格的方法是在统一期间禁止使用任何灵活的相同注释实例化刚性类型变量。这两种方式对我来说似乎都是合法的，但这在 Haskell?

中实际上是如何工作的？

Answer 1

非量化类型变量在顶层隐式量化。你的类型相当于

fun :: forall b . (forall a. [a] -> b) -> Bool
arg :: forall c . c -> c

因此，b的范围是整个类型。

您可以将每个 forall 编辑的变量视为函数接收的一种隐式附加类型参数。我想你明白，在

这样的签名中

foo :: Int -> (String -> Bool) -> Char

Int 值由 foo 的调用者选择，而 String 值由 foo 在（以及如果）调用传递的函数时选择作为第二个参数。

本着同样的精神，

fun :: forall b. (forall a. [a] -> b) -> Bool

表示b由fun的调用者选择，而a由fun自己选择。

调用者确实可以使用 TypeAnnotations 显式传递 b 类型并写入

fun @Int :: (forall a. [a] -> Int) -> Bool

之后，forall a. [a] -> Int类型的参数必须是apssed，length适合这样的多态类型。

fun @Int length :: Bool

因为这是 fun 的调用站点，我们看不到“类型参数”a 传递到哪里。那确实只能在fun.

的定义中找到

嗯，事实证明，实际上不可能定义一个 fun 类型来对其参数进行有意义的调用（length，上面）。如果我们有一个稍微不同的签名，就像这样：

fun :: forall b. Eq b => (forall a. [a] -> b) -> Bool
fun f = f @Int [1,2,3] /= f @Bool [True, False]

在这里我们可以看到 f（通过调用绑定到 length）在两种不同的类型上被调用了两次。这会产生两个 b 类型的值，然后可以比较它们以产生最终的 Bool.

嵌套通用量词的范围是如何确定的（更高级别的类型）？

How is the scope of a nested universal quantifier determined (higher-rank types)?

haskell

functional-programming

unification

quantifiers

higher-rank-types