Haskell：组合存在量词和通用量词意外失败

Question

我正在尝试使用 GHC 8.6.5 版在 Haskell 中对以下逻辑含义进行建模：

(∀ a. ¬ Φ(a)) → ¬ (∃ a: Φ(a))

我使用的定义如下：

{-# LANGUAGE RankNTypes, GADTs #-}

import Data.Void

-- Existential quantification via GADT
data Ex phi where
  Ex :: forall a phi. phi a -> Ex phi

-- Universal quantification, wrapped into a newtype
newtype All phi = All (forall a. phi a)

-- Negation, as a function to Void
type Not a = a -> Void

-- Negation of a predicate, wrapped into a newtype
newtype NotPred phi a = NP (phi a -> Void)

-- The following definition does not work:
theorem :: All (NotPred phi) -> Not (Ex phi)
theorem (All (NP f)) (Ex a) = f a

此处，GHC 拒绝执行 theorem 并显示以下错误消息：

* Couldn't match type `a' with `a0'
  `a' is a rigid type variable bound by
    a pattern with constructor:
      Ex :: forall a (phi :: * -> *). phi a -> Ex phi,
    in an equation for `theorem'
    at question.hs:20:23-26
* In the first argument of `f', namely `a'
  In the expression: f a
  In an equation for `theorem': theorem (All (NP f)) (Ex a) = f a
* Relevant bindings include
    a :: phi a (bound at question.hs:20:26)
    f :: phi a0 -> Void (bound at question.hs:20:18)

我不太明白为什么GHC不能匹配这两种类型。以下解决方法编译：

theorem = flip theorem' where
    theorem' (Ex a) (All (NP f)) = f a

对我来说，theorem 的两个实现是等价的。为什么 GHC 只接受第二个？

Answer 1

当您将模式 All prf 与类型 All phi 的值匹配时，prf 被提取为类型 forall a. phi a 的多态实体。在这种情况下，您会得到 no :: forall a. NotPred phi a。但是，您不能对这种类型的对象执行模式匹配。毕竟，它是一个从类型到值的函数。你需要将它应用到一个特定的类型（称之为_a），你会得到no @_a :: NotPred phi _a，现在可以匹配它来提取一个f :: phi _a -> Void。如果你扩展你的定义...

{-# LANGUAGE ScopedTypeVariables #-}
-- type signature with forall needed to bind the variable phi
theorem :: forall phi. All (NotPred phi) -> Not (Ex phi)
theorem prf wit = case prf of
    All no -> case no @_a of -- no :: forall a. NotPred phi a
        NP f -> case wit of -- f :: phi _a -> Void
            Ex (x :: phi b) -> f x -- matching against Ex extracts a type variable, call it b, and then x :: phi b

那么问题来了，_a应该用什么类型呢？好吧，我们正在将 f :: phi _a -> Void 应用于 x :: b（其中 b 是存储在 wit 中的类型变量），因此我们应该设置 _a := b。但这是范围界定违规。 b 仅通过与 Ex 匹配来提取，这发生在我们专门化 no 并提取 f 之后，因此 f 的类型不能依赖于 b。因此，没有选择 _a 可以在不让存在变量脱离其范围的情况下完成这项工作。错误。

正如您发现的那样，解决方案是在将该类型应用到 no.

之前匹配 Ex（从而提取其中的类型）

theorem :: forall phi. All (NotPred phi) -> Not (Ex phi)
theorem prf wit = case wit of
    Ex (x :: phi b) -> case prf of
        All no -> case no @b of
            NP f -> f x
-- or
theorem :: forall phi. All (NotPred phi) -> Not (Ex phi)
theorem (All no) (Ex x) | NP f <- no = f x

Haskell：组合存在量词和通用量词意外失败

Haskell: Combining existential and universal quantifiers fails unexpectedly

haskell

ghc

existential-type

functional-logic-progr