GADT 与 ScopedTypeVariables/PatternSignatures 之间的相互作用

Question

我正在探索长度索引向量的 'hackneyed' 示例，代码改编自 Richard Eisenberg's thesis 第 3.1 节

{-# LANGUAGE  GADTs, TypeFamilies, DataKinds, KindSignatures,
              TypeOperators, ScopedTypeVariables  #-}
                          -- PatternSignatures  -- deprecated

import GHC.Types (Type)

data Nat = Zero | Succ Nat
data Vec :: Type -> Nat -> Type  where
  Nil :: Vec a Zero                       -- E has 'Zero
  (:>) :: a -> Vec a n -> Vec a (Succ n)  -- E has 'Succ
infixr 5 :>

type family (+) (n :: Nat) (m :: Nat) :: Nat  where
  (+) Zero      m = m
  (+) (Succ n') m = Succ (n' + m)

append :: Vec a n -> Vec a m -> Vec a (n + m)
append (Nil     :: Vec aa Zero) (w :: Vec aa mm) = w :: Vec aa (Zero + mm)
append (x :> (v :: Vec a n'))   (w :: Vec a m)   = x :> ((append v w) :: Vec a (n' + m))

append Nil ... 方程被拒绝 (GHC 8.6.5)

* Couldn't match type `m' with `n + m'
  `m' is a rigid type variable bound by
    the type signature for:
      append :: forall a (n :: Nat) (m :: Nat).
                Vec a n -> Vec a m -> Vec a (n + m)
    at ...
  Expected type: Vec a (n + m)
    Actual type: Vec a ('Zero + m)

将结果类型设为 :: Vec aa mm 也被拒绝。

  Expected type: Vec a (n + m)
    Actual type: Vec a m

奇怪，因为这是被接受的（见下文）。

我真正想做的是使用 PatternSignatures 作为 append 的参数。但是该扩展名已弃用，我必须使用 ScopedTypeVariables。这意味着 append 签名中的 tyvars 在方程式的范围内。所以我使用了新的 tyvar 名称。

GADT 给出 Nil :: Vec a Zero，因此我将其作为其模式签名（带有新的 aa）。但似乎 GHC 无法将 append 签名中的 n 与 Zero 统一起来。如果我将该等式更改为其中任何一个，一切都会很高兴：

append (Nil     :: Vec aa nn) (w :: Vec aa mm) = w :: Vec aa (nn + mm)

append (Nil     :: Vec aa nn) (w :: Vec aa mm) = w :: Vec aa (mm)

为了验证这些，GHC 必须从 + 的类型族方程中计算出 Nil :: Vec a Zero 和 Zero + m = m。那么为什么它对带有 Zero 的模式签名感到不满呢？

（我最初试图用 PatternSignatures 给出 append 的等式，看看 GHC 是否可以推断出签名。那没有成功。）

Answer 1

首先要注意的是，您显示的错误并不是您遇到的唯一错误，实际上，它也不是最重要的错误。您应该看到的另一个错误是：

    * Couldn't match type `n' with 'Zero
      `n' is a rigid type variable bound by
        the type signature for:
          append :: forall a (n :: Nat) (m :: Nat).
                    Vec a n -> Vec a m -> Vec a (n + m)
        at ...
      Expected type: Vec a n
        Actual type: Vec a 'Zero
    * When checking that the pattern signature: Vec a 'Zero
        fits the type of its context: Vec a n
      In the pattern: Nil :: Vec a Zero

这里的关键部分是“当检查模式签名是否符合其上下文的类型时”。实际上，模式 Nil 的类型不仅仅是 Vec a Zero；它实际上类似于 () => (n ~ Zero) => Vec a n。此类型表示模式可能匹配 Vec a n 类型的任何内容，并且如果它匹配，则约束 n ~ Zero 被纳入范围。另一方面，类型为 Vec a Zero 的模式受类型限制，仅适用于类型 Vec a Zero。在 append 的定义中，输入的类型为 Vec a n，因此 Vec a Zero 类型的模式将不匹配。

（您可以阅读更多关于模式同义词类型的内容，这可能会有所启发，in the docs。）

使用更简单的示例和模式同义词的使用可能更容易理解这一点。

考虑这种类型和功能：

data Foo a where
  Bar :: Foo Int
  Baz :: Foo Char

doFoo :: Foo a -> a
doFoo Bar = 1
doFoo Baz = 'c'

一切顺利。但是，如果我们将第六行更改为

doFoo (Bar :: Foo Int) = 1

然后我们会得到一个与您在 append 中看到的非常相似的错误。现在让我们来研究一下模式同义词。如果我们在 Bar 周围有一个简单类型 Foo Int:

的模式同义词会怎样

{-# LANGUAGE PatternSynonyms #-}
pattern BarInt :: Foo Int
pattern BarInt = Bar

如果我们在 doFoo 中使用它，我们会得到模式类型不匹配的相同错误。这确实有意义，因为此模式仅针对 Foo Int 类型的输入定义，而不是 Foo a 类型的输入。让我们尝试另一种变体：

pattern BarA :: Foo a
pattern BarA <- Bar

注意这里使用 <- 而不是 =，这使它成为单向模式同义词而不是双向模式。我们必须这样做，因为虽然我们可以“忘记”Int 并从 Foo Int 变为 Foo a，但我们不能反过来。但是，如果我们尝试在 doFoo 中使用 BarA 会发生什么？现在我们得到这样的错误：

    * Couldn't match expected type `a' with actual type `Int'
      `a' is a rigid type variable bound by
        the type signature for:
          dofoo :: forall a. Foo a -> a

这个模式足够松散，可以被接受，但是在模式匹配之后，我们仍然对a一无所知，所以我们不能return一个Int。

要真正重新创建 Bar 模式，我们需要编写：

pattern Bar' :: () => (a ~ Int) => Foo a
pattern Bar' = Bar

这里我们的pattern type表示提前应用pattern没有限制（初始() =>），匹配后我们会知道a ~ Int，这个pattern可以匹配 Foo a.

形式的任何内容

GADT 与 ScopedTypeVariables/PatternSignatures 之间的相互作用

Interaction between GADTs and ScopedTypeVariables/PatternSignatures

haskell

gadt

scoped-type-variables