阐明 Haskell 记录的通用量化

Question

我们知道

forall a. a -- undefined
forall a. [a] -- [] or undefined
forall a. (a,a) --  undefined

不过我注意到

data Record a where -- GADTSyntax eq. to data Record a = Record { idx :: a -> a }
  Record :: forall b. {idx :: b -> b } -> Record b

record :: forall a. Record a
record = Record { idx = \x -> x }  -- Not undefined

也就是record :: forall a. Record a不是上面的undefined。我怀疑这是因为它是函数的记录，但这并不能真正解释为什么相对于类型系统的规则这是可以的。

上面的第一个量化在这里得到了很好的解释：

What is the difference between forall a. [a] and [forall a. a]?
Which is a polymorphic type: a type or a set of types?

因此我想知道是否有人可以提供一些“有点”“正式”（类型系统透视解释）的说明，说明这是怎么可能的，即实际发生了什么？ GHC 实际上是如何处理它的？

Answer 1

一般来说，如果：

data Record a where
    Record :: forall b. { field :: Whatever b } -> Record b

对于任意类型的函数 Whatever，当且仅当 forall a. Whatever a 被居住时，forall a. Record a 才会被居住（通过 non-bottom 值）。

这不足为奇。这个单字段ADT通过函数Record和field:

在Record b和Whatever b之间创建了一个多态同构

Record :: forall b. Whatever b -> Record b
field :: forall b. Record b -> Whatever b

并且 rank-2 类型的规则允许以下同构 - 在 forall a. Record a 和 forall a. Whatever a 的居民之间 - 进行类型检查：

toRecord :: (forall a. Whatever a) -> (forall a. Record a)
toRecord = Record

fromRecord :: (forall a. Record a) -> (forall a. Whatever a)
fromRecord = field

请注意，该字段不必是函数。给定：

data Record1 a where
    Record1 :: forall b. { field1 :: [b] } -> Record1 b

类型 forall a. Record1 a 与 forall a. [a] 同构，并且被 Record1 [] 占据。

也许这有帮助？

Answer 2

We know that

forall a. a -- undefined
forall a. [a] -- [] or undefined
forall a. (a,a) --  undefined

是的，还有这些：

forall a. [a] 包含：
1. undefined
2. []（完全定义）
3. undefined : xs 对于任何 xs:
- undefined : []、a.k.a。 [undefined]
- undefined : undefined : undefined
- undefined : undefined : []、a.k.a。 [undefined, undefined]
- （依此类推。）
forall a. (a, a) 不包含完全定义的术语：
1. undefined
2. (undefined, undefined)

However i have noticed that
data Record a where -- GADTSyntax eq. to data Record a = Record { idx :: a -> a }
  Record :: forall b. {idx :: b -> b } -> Record b

record :: forall a. Record a
record = Record { idx = \x -> x }  -- Not undefined
That is record :: forall a. Record a is not undefined as in the above.

没错。 forall a. Record a 包含条款：

undefined
Record undefined、a.k.a。 Record { idx = undefined }
Record id、a.k.a。 Record { idx = id }，这是一个定义值

I suspect it is because it is a record of functions, but that does not explain really why with respect to the rule of the type system this is ok.

不完全是。 GADTSyntax 明确给出了构造函数的类型，这是理解这一点的一个很好的起点。我们有：

Record :: forall b. { idx :: b -> b } -> Record b

或者，没有记录符号，但有一些额外的括号和 KindSignatures 注释以达到良好的效果：

Record :: forall (b :: Type). ((b -> b) -> Record b)

也就是说，如果您将数据构造函数 Record 应用于您选择的任何 Type 参数，那么它将被分配给类型参数 b 并代入类型 (b -> b) -> Record b。例如，Int:

forall b.    (b   -> b  ) -> Record b
(b ~ Int) => (b   -> b  ) -> Record b
             (Int -> Int) -> Record Int

（注意。~ 是一个等式约束；此语法由 GADTs 或 TypeFamilies 语言选项启用。）

这类似于 lambda/function 表达式如何为其参数接收参数值：

(\  i ->      i + 3)
let i =  2 in i + 3
              2 + 3

事实上，forall 是 lambda 的 type-level 类似物，它只获取并生成类型而不是值。

因此，在将 Record 应用于类型 b 之后，如果将结果应用于函数 f :: b -> b，该函数接受 returns 值 那个特定类型 b，那么你可以构造一个类型Record b的值（这里是类型构造函数Record）。通常，类型参数的应用是隐式的，但您可以使用 TypeApplications 语言选项使其显式：

Record            :: forall b. (b   -> b  ) -> Record b

Record       not  ::                           Record Bool

Record @Int       ::           (Int -> Int) -> Record Int

Record @Int (* 2) ::                           Record Int

现在，在多态的情况下，record :: forall a. Record a，你是说任何人都可以自由地向 record 提供他们选择的任何类型 a（例如 record @Char) 并且他们将取回 Record a 类型的值（如果 a = Char 则为 Record Char）。除了额外的 Record 包装器外，这与承诺为每个可能的类型 T 构造 T -> T 相同，在一般情况下，对于 all T，这是有前途的 T -> T，因为 record 不需要任何进一步的信息来限制其类型参数，例如 Num a 或Ord a.

使用 ScopedTypeVariables 语言选项，您可以注释这样一个事实，即在 record 的主体内，有一个名为 a 的特定类型变量，其值为未知，但仍然不变。

{-# Language ScopedTypeVariables #-}

-- ‘forall’ defines the scope of ‘a’.
record :: forall a. Record a

-- ‘a’ refers to the above ‘a’, not a new one.
record = Record { idx = \ (x :: a) -> x }

或：

{-# Language ScopedTypeVariables #-}

record :: forall a. Record a
record = Record { idx = f }
  where
    -- Again this would normally mean a fresh ‘a’,
    -- but here it refers to the scoped ‘a’.
    f :: a -> a
    f x = x

Hence I wonder if anyone can provide some "somewhat" "formal" (type system perspective explanation) clarification of how is that possible i.e. what is actually happening ?

另一种思考方式是，如果一个类型只包含可以完全评估为值的术语，那么将该类型解释为逻辑公式（通过 Curry–Howard correspondence）将产生“真” ，即这将是一个重言式；如果它是“false”，那么该类型的术语必须在一些情况下崩溃或循环，例如 head []，但不一定所有个案，例如 head [1]。你可以很机械地看这个：

Void 没有值，因为它没有构造函数。这对应于“假”。它只包含一项，undefined.
() 为其一个构造函数定义了一个居民，对应于“true”。它还包含术语 undefined.

A

B

Either A B 有 Left (x :: A) 和 Right (y :: B) 居住。它还包含 undefined、Left undefined 和 Right undefined。

A

B

(A, B) 会被 (x :: A, y :: B) 居住。它也包含 undefined、(x, undefined)、(undefined, y) 和 (undefined, undefined)。
A -> B如果可以为每个值x :: A.
构造一个值y :: B，则有人居住
forall (x :: A). B可以为每个类型x :: A构造一个值y :: B，则x :: A是有人居住的，其中A 是一种，比如 Type, Type -> Type, &c.
其他类型可以表示为这些原始类型的（可能是递归的）组合。

所以例如forall a. a是假的，因为如果你将它解释为一个逻辑表达式（“对于所有A（真或假），A是真”）那么它显然有一个反例（“假是真的”是胡说八道）。

forall a. Record a（或者只是 forall a. a -> a，没有包装）有人居住，因为你总是可以生产 Record id（resp. id）。从逻辑上讲，这就是说“对于所有 A，A 蕴涵 A”，情况是这样的：真蕴涵真理，而谬误蕴涵任何事物 (a.k.a.ex falso quodlibet).

同样，forall a. [a]有人居住，因为你总能生产[]。详细来说，这是逻辑公式“L(A) = for all A, true or A and L(A)”，它始终为真，[a]和Either () (a, [a])展开得到，()对应[] :: [a]，(a, [a])对应(:) :: a -> [a] -> [a]).

阐明 Haskell 记录的通用量化

Clarifying Universal quantification over Haskell Record

haskell

record