枚举类型的 COQ 相等

Question

我在 COQ 中有一个有限枚举类型（比如 T），我想检查元素是否相等。这意味着，我需要一个函数

bool beq_T(x:T,y:T)

我设法定义这样一个函数的唯一方法是逐案分析。这会导致很多匹配语句，看起来很麻烦。因此，不知有没有更简单的方法来实现。

Answer 1

坏消息是实现 beq_T 的程序必须在其两个参数上包含一个大型匹配语句。好消息是您可以使用 Coq 的 策略语言 自动 generate/synthesize 这个程序。例如，给定类型：

Inductive T := t0 | t1 | t2 | t3.

您可以按如下方式定义beq_T。前两个 destruct 策略综合了在 x 和 y 上进行匹配所必需的代码。 match 策略检查它所在的匹配分支，并且根据是否 x = y，该策略合成 returns true 或 [=23= 的程序].

Definition beq_T (x y:T) : bool.
  destruct x eqn:?;
  destruct y eqn:?;
  match goal with 
  | _:x = ?T, _:y = ?T |- _ => exact true
  | _ => exact false
  end.
Defined.

如果想看合成的程序，运行:

Print beq_T.

值得庆幸的是，Coq 已经提供了一种几乎可以满足您要求的策略。它被称为decide equality。它会自动合成一个程序，该程序决定类型 T 的两个元素是否相等。但是，合成程序不只是返回一个布尔值，而是 returns 两个元素（不）相等的证明。

Definition eqDec_T (x y:T) : {x = y} + {x <> y}.
  decide equality.
Defined.

综合了那个程序，很容易实现beq_T。

Definition beq_T' {x y:T} : bool := if eqDec_T x y then true else false.

Answer 2

更简单：Scheme Equality for ... 生成两个函数，分别返回一个布尔值和一个 sumbool。

枚举类型的 COQ 相等

Equality in COQ for enumerated types

coq