Coq：在假设或目标中用 'forall' 重写

Question

我已经在 Coq 中证明了 'correctness' 多态 Lists 的逆函数。下面的证明工作得很好，但我有几个关于 rewrite 策略如何工作的问题。

代码如下：

Require Export Coq.Lists.List.
Import ListNotations.

Fixpoint rev {T:Type} (l:list T) : list T :=
  match l with
  | nil    => nil
  | h :: t => rev t ++ [h]
  end.

(* Prove rev_acc equal to above naive implementation. *)
Fixpoint rev_acc {T:Type} (l acc:list T) : list T :=
  match l with
  | nil => acc
  | h :: t => rev_acc t (h::acc)
  end.

Theorem app_assoc : forall  (T:Type) (l1 l2 l3 : list T),
  (l1 ++ l2) ++ l3 = l1 ++ (l2 ++ l3).
Proof.
Admitted.

Theorem rev_acc_correct : forall (T:Type) (l k :list T),
  rev l ++ k = rev_acc l k.
Proof.
  intros T l.
  induction l as [ | h l' IHl' ].
  - reflexivity.
  - simpl. 
    intro k.
    (* Why is "intro k" required for "rewrite -> app_assoc" *)
    (* But "rewrite -> IHl'" works regardless of "intro k".  *)
    (* generalize (rev l'), [h], k. *)
    rewrite -> app_assoc.
    simpl.
    rewrite -> IHl'.
    reflexivity.
Qed.

在 rev_acc_correct 证明的归纳步骤中，如果我跳过 intro k，然后用 [=25 重写=]app_assoc 抱怨找不到匹配的子项。

Found no subterm matching "(?M1058 ++ ?M1059) ++ ?M1060" in the current goal.

在这里，我假设占位符名称前的 ? 表示术语是受约束的，在这种情况下是类型 List T 对于某些类型 T；由于目标中的 rev l' 和 [h] 是 List T 的实例，因此人们会期待进球。

另一方面，用归纳假设重写（rewrite -> IHl'）而不是app_assoc之前不需要 intro k。

我发现 rewrite 的这种行为有点令人困惑，Coq 手册没有提供任何细节。我不想通读整个实现，但我需要对重写策略的作用有很好的操作理解，尤其是关于术语匹配的工作原理。在这方面的任何 answers/references 都非常感谢。

Answer 1

此重写的复杂之处在于有一个 binder（forall k），这会使事情变得复杂。如果您只是想让事情正常运行，请使用 setoid_rewrite 而不是 rewrite，它将在活页夹下重写。

rewrite IHl' 看起来像是发生在活页夹下，但重写的模式实际上并不涉及绑定变量，因此活页夹实际上并不重要。这就是我的意思：目标是
```
forall k : list T, (rev l' ++ [h]) ++ k = rev_acc l' (h :: k)
```
与（即等于）相同：
```
 (fun l : list T => forall k : list T, l ++ k = rev_acc l' (h :: k)) (rev l' ++ [h])
```
这是我在 Ltac 中使用 pattern (rev l' ++ [h]) 得到的。现在很明显，您可以只重写应用的部分而忽略活页夹。当您执行 rewrite IHl' 时，Coq 很容易发现 IHl 应该专用于 [h] 并且重写会继续进行。
rewrite app_assoc 需要专门针对三个列表，特别是 rev l'、[h] 和 k。它不能在当前上下文中专门化，因为变量 k 仅绑定在 forall 下。这就是模式 (?x ++ ?y) ++ ?z 没有出现在目标中的原因。

那么你实际上是做什么的？你当然可以引入 k 所以没有活页夹，但是有一个更简单和更通用的技术：Coq 有通用的重写，可以在活页夹下重写，你可以通过调用 setoid_rewrite 来使用它（见 Rewriting under binders 在 Coq 参考手册中）。手册告诉你需要声明态射，但在这种情况下，forall 已经为你实现了相关的态射，所以 setoid_rewrite app_assoc 就可以了。

请注意，虽然您始终可以引入 forall 来摆脱活页夹，但当您的目标是 exists 时，setoid_rewrite 会非常方便。而不是使用 eexists 你可以在活页夹下重写。

Coq：在假设或目标中用 'forall' 重写

Coq: Rewriting with 'forall' in hypothesis or goal

coq

coq-tactic