使用列表相等性简化表达式

Question

我的任务是为 seq 数据类型实现相等类型的实例。为此，我需要创建一个比较函数并证明该函数是正确的：

From mathcomp Require Import ssreflect ssrfun ssrbool eqtype ssrnat div seq.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.

Fixpoint eq_seq {T: eqType} (x y: seq T) : bool :=
  match x, y with
  | [::],[::] => true
  | cons x' xs, [::] => false
  | [::], cons y' ys => false
  | cons x' xs, cons y' ys => (x' == y') && eq_seq xs ys
  end.

Arguments eq_seq T x y : simpl nomatch.

Lemma eq_seq_correct : forall T: eqType, Equality.axiom (@eq_seq T).
Proof.
  move=> T x. elim: x=> [|x' xs].
  - move=> y. case: y=> //=; by constructor.
  - move=> IH y. case: y=> [| y' ys].
    + rewrite /(eq_seq (x' :: xs) [::]). constructor. done.
    + move=> /=. case E: (x' == y').
      * move: E. case: eqP=> E _ //=. rewrite <- E.

结果：

2 subgoals (ID 290)

  T : eqType
  x' : T
  xs : seq T
  IH : forall y : seq T, reflect (xs = y) (eq_seq xs y)
  y' : T
  ys : seq T
  E : x' = y'
  ============================
  reflect (x' :: xs = x' :: ys) (eq_seq xs ys)

subgoal 2 (ID 199) is:
 reflect (x' :: xs = y' :: ys) (false && eq_seq xs ys)

如何去掉等式两边的x'：(x' :: xs = x' :: ys)?

我尝试了 case: (x' :: xs = x' :: ys)，但没有用。

Answer 1

（以防万一你不知道，这个引理已经在 seq 库中得到证明。寻找 eqseqP。）

完成证明的关键步骤是iffP引理：

iffP : forall P Q b, reflect P b -> (P -> Q) -> (Q -> P) -> reflect Q b.

因此，通过调用 apply/(iffP (IH ys))，我们将当前目标降低为证明 xs = ys -> x' :: xs = x' :: ys 和 x' :: xs = x' :: ys -> xs = ys。您可以通过应用 congruence 策略来实现这两个子目标。

使用列表相等性简化表达式

Simplifying expression with lists equality

coq

ssreflect