为什么 Haskell 中没有 "Exist" 关键字用于存在量化？

Question

根据 GHC 文档，给出以下声明：

data Foo = forall a. MkFoo a (a -> Bool)
           | Nil

然后

MkFoo :: forall a. a -> (a -> Bool) -> Foo

（几乎）同构于以下伪Haskell声明

MkFoo :: (exists a . (a, a -> Bool)) -> Foo

因此，不需要单独的 "Exist" 关键字。因为：

Haskell programmers can safely think of the ordinary universally quantified type given above.

但我不确定那是什么意思。谁能解释一下为什么我们可以用全称量词来表达存在量词？

Answer 1

如果您查看数据构造函数的类型，您会注意到我们同样使用 -> 以某种方式表示乘积。例如

(:) :: a -> [a] -> [a]

实际上意味着我们正在使用 (:) 将 a 与类型 [a] 的列表一起打包并传递一个列表输入 [a].

在您的示例中，forall 的使用仅意味着 MkFoo 作为构造函数愿意打包任何类型 a。当您阅读 GHC 文档中的 (exists a . (a, a -> Bool)) -> Foo 时，您应该将其视为原始类型 MkFoo 的未柯里化版本。 (:) 的相应未柯里化版本将是 (a, [a]) -> [a].

Answer 2

首先要注意的是forall量词出现在等号的右边，所以它关联了一个数据构造函数（不输入）：MkFoo。因此，类型 Foo 没有说明 a.

当我们尝试对 Foo 类型的值进行模式匹配时，我们再次遇到 a。那时你对 MkFoo 的组件几乎一无所知，除了它们存在（必须存在用于调用 MkFoo 的类型）和第一个组件可以用作第二个组件的参数，第二个组件是一个函数：

f :: Foo -> Bool
f (MkFoo val fn) = fn val

Answer 3

在逻辑（经典的或直觉的）中，公式

(exists x. p x) -> q
forall x. (p x -> q)

是等价的（注意q不依赖于上面的x）。这可以用来根据全称量化来表达存在量化，前提是存在位于蕴涵的左侧。（这里是经典proof。）

在函数式编程中，您可以实现相同的目的。而不是写

-- Pseudo-Haskell follows
f :: (exists a. (a, a->Int)) -> Int
f (x,h) = h x

我们可以使用

-- Actual Haskell
f :: forall a. (a, a->Int) -> Int
f (x,h) = h x

所以我们可以不用存在量化，至少在上述情况下是这样。

当它不在箭头左侧时，仍然需要存在量化。例如，

g :: exists a. (a, a->Int)
g = (2 :: Int, \x -> x+3)

唉，Haskell 选择不包括这些类型。做出此选择可能是为了防止本已复杂的类型系统变得过于复杂。

仍然，Haskell 获得了存在数据类型，这只需要 wrap/unwrap 一个围绕存在数据类型的构造函数。例如，使用 GADT 语法，我们可以这样写：

data Ex where
  E :: forall a. (a, a->Int) -> Ex
g :: Ex
g = E (2 :: Int, \x -> x+3)

最后，让我补充一点，存在性也可以通过 rank-2 类型和 continuation-passing 来模拟：

g :: forall r. (forall a. (a, a->Int) -> r) -> r
g k = k (2 :: Int, \x -> x+3)

为什么 Haskell 中没有 "Exist" 关键字用于存在量化？

Why there is no an "Exist" keyword in Haskell for Existential Quantification?

haskell