从 GADT 中检索约束以确保在 Coq 中耗尽模式匹配

Question

让我们定义两个助手类型：

Inductive AB : Set := A | B.
Inductive XY : Set := X | Y.

然后是另外两个依赖于XY和AB

的类型

Inductive Wrapped : AB -> XY -> Set :=
| W : forall (ab : AB) (xy : XY), Wrapped ab xy
| WW : forall (ab : AB), Wrapped ab (match ab with A => X | B => Y end)
.

Inductive Wrapper : XY -> Set :=
  WrapW : forall (xy : XY), Wrapped A xy -> Wrapper xy.

注意 WW 构造函数——它只能是类型 Wrapped A X 和 Wrapped B Y 的值。

现在我想在 Wrapper Y:

上进行模式匹配

Definition test (wr : Wrapper Y): nat :=
  match wr with
  | WrapW Y w =>
    match w with
    | W A Y => 27
    end
  end.

但我收到错误

Error: Non exhaustive pattern-matching: no clause found for pattern WW _

为什么会这样？ Wrapper 强制包含 Wrapped 为 A 版本，类型签名强制 Y 和 WW 构造函数禁止 A 和 Y同时。我不明白为什么还要考虑这个案例，而我被迫检查它似乎是不可能的。

如何解决这种情况？

Answer 1

结果证明解决方案简单但棘手：

Definition test (wr : Wrapper Y): nat.
  refine (match wr with
  | WrapW Y w =>
    match w in Wrapped ab xy return ab = A -> xy = Y -> nat with
    | W A Y => fun _ _ => 27
    | _ => fun _ _ => _
    end eq_refl eq_refl
  end);
[ | |destruct a]; congruence.
Defined.

问题是 Coq 没有推断出一些必要的不变量来意识到 WW 情况是荒谬的。我必须明确地给它一个证明。

在这个解决方案中，我将 match 更改为 return 一个函数，该函数接受两个证明并将它们带到我们实际结果的上下文中：

ab 显然是 A
xy 显然是 Y

我已经涵盖了忽略这些假设的真实案例，并且我推迟了 "bad" 个案例，以便稍后证明是错误的，这些案例变得微不足道。我被迫手动传递 eq_refls，但它起作用了而且看起来还不错。

Answer 2

让我们简化一下：

Inductive MyTy : Set -> Type :=
  MkMyTy : forall (A : Set), A -> MyTy A.

Definition extract (m : MyTy nat) : nat :=
  match m with MkMyTy _ x => S x end.

这失败了：

The term "x" has type "S" while it is expected to have type "nat".

wat.

这是因为我说了

Inductive MyTy : Set -> Type

这使得 MyTy 的第一个参数成为 MyTy 的索引，而不是参数。带有参数的归纳类型可能如下所示：

Inductive list (A : Type) : Type :=
  | nil : list A
  | cons : A -> list A -> list A.

参数在:的左边命名，而不是在每个构造函数的定义中forall-d。（它们仍然存在于定义之外的构造函数类型中：cons : forall (A : Type), A -> list A -> list A。）如果我将 Set 作为 MyTy 的参数，则可以定义 extract：

Inductive MyTy (A : Set) : Type :=
  MkMyTy : A -> MyTy A.

Definition extract (m : MyTy nat) : nat :=
  match m with MkMyTy _ x => S x end.

原因是，在内部，match忽略了您从外部了解的有关受检者指数的任何信息。（或者，更确切地说，Gallina 中的底层 match 表达式忽略了索引。当您在源代码中编写 match 时，Coq 会尝试将其转换为原始形式，同时合并来自索引的信息，但是它经常失败。） extract 的第一个版本中的 m : MyTy nat 根本无关紧要。相反，匹配给了我 S : Set（这个名字是由 Coq 自动选择的）和 x : S，根据构造函数 MkMyTy，没有提到 nat。同时，因为 MyTy 在第二个版本中有一个参数，所以我实际上得到 x : nat。这次 _ 真的是一个占位符；必须写成_，因为没有什么可以匹配的，你可以Set Asymmetric Patterns让它消失。

我们区分参数和索引的原因是因为参数有很多限制——最值得注意的是，如果 I 是带参数的归纳类型，那么参数必须作为变量出现在 return 每个构造函数的类型：

Inductive F (A : Set) : Set := MkF : list A -> F (list A).
                                            (* ^--------^ BAD: must appear as F A *)

在你的问题中，我们应该尽可能地制作参数。例如。 match wr with Wrap Y w => _ end 位是错误的，因为 Wrapper 的 XY 参数是一个索引，所以 wr : Wrapper Y 被忽略；您还需要处理 Wrap X w 案例。 Coq 还没来得及告诉你。

Inductive Wrapped (ab : AB) : XY -> Set :=
| W : forall (xy : XY), Wrapped ab xy
| WW : Wrapped ab (match ab with A => X | B => Y end).

Inductive Wrapper (xy : XY) : Set := WrapW : Wrapped A xy -> Wrapper xy.

现在您的 test 编译（几乎）：

Definition test (wr : Wrapper Y): nat :=
  match wr with
  | WrapW _ w => (* mandatory _ *)
    match w with
    | W _ Y => 27 (* mandatory _ *)
    end
  end.

因为拥有这些参数可以为 Coq 提供足够的信息，以便其 match-详细说明使用来自 Wrapped 的索引的信息。如果你发出 Print test.，你可以看到有一点 hoop-jumping 通过原语 match 传递关于索引 Y 的信息，否则会忽略它。 See the reference manual for more information.

从 GADT 中检索约束以确保在 Coq 中耗尽模式匹配

Retrieving constraints from GADT to ensure exhaustion of pattern matching in Coq

coq

dependent-type

gadt