重写策略无法在模式匹配中找到术语出现

Question

在 Coq 中，我在以下情况下应用 rewrite 策略时遇到问题：

Section Test.

Hypothesis s t        : nat -> nat.
Hypothesis s_ext_eq_t : forall (x : nat), s x = t x.

Definition dummy_s : nat -> nat :=
  fun n => match n with
         | O => 42
         | S np => s np
       end.

Definition dummy_t : nat -> nat :=
  fun n => match n with
         | O => 42
         | S np => t np
       end.

Goal forall (n : nat), dummy_s n = dummy_t n.
Proof.
  intro n. unfold dummy_s. unfold dummy_t.

在那个阶段，当地情况和当前目标如下：

1 subgoals, subgoal 1 (ID 6)

s : nat -> nat
t : nat -> nat
s_ext_eq_t : forall x : nat, s x = t x
n : nat
============================
match n with
| 0 => 42
| S np => s np
end = match n with
      | 0 => 42
      | S np => t np
      end

现在应该可以应用rewrite策略将目标中出现的s np替换为t np，从而可以使用[=解决目标23=]。然而，

rewrite s_ext_eq_t.

给予

Toplevel input, characters 0-18:
Error: Found no subterm matching "s ?190" in the current goal.

我做错了什么？一个可以进入 rewrite 适用的情况

 destruct n. 
   (* n = 0 *)
   reflexivity.
   (* n > 0 *)
   rewrite s_ext_eq_t.
   reflexivity.
 Qed.

但在我面临的实际情况下，几个这样的破坏是必要的，我想知道 rewrite 或它的变体是否能够自动执行此操作。

附录当证明通过有根据的递归定义的函数具有所需的固定点时，上述情况自然会发生属性：

假设 A: Type 并且 R: A -> A -> Prop 是一个有根据的关系，即我们有 Rwf: well_founded R。然后，给定一个类型族 P: A -> Type 我们可以构造一个部分

Fix : forall (x : A), P a

通过 R 的递归，递归步骤作为函数给出

 F : forall x:A, (forall y:A, R y x -> P y) -> P x

见https://coq.inria.fr/library/Coq.Init.Wf.html 不过要证明Fix确实有不动点属性

  forall (x : A), Fix x = F (fun (y:A) _ => Fix y)`

我们需要提供证人

  F_ext : forall (x:A) (f g:forall y:A, R y x -> P y),
             (forall (y:A) (p:R y x), f y p = g y p) -> F f = F g.

即我们必须证明 F 没有使用给定 f: forall y:A, R y x -> P y 中的任何其他内容，而是它的值。当然，在任何具体情况下，这应该是微不足道的验证，但是当你试图证明它时，你会遇到一种情况，我在上面给出了一个最小的例子：一个人面临着两份代码的巨大平等对于递归步骤，一次使用 f，另一次使用 g。您的假设表明 f 和 g 在外延上是相等的，因此应该能够重写它们。然而，在递归步骤的代码中，可能有大量的模式匹配和在本地上下文中没有意义的新变量，因此它（不必要？）对 destruct 几十个来说非常乏味在被允许申请之前的次数 rewrite.

Answer 1

如上面的评论所述，不可能直接在match语句的分支上执行重写，因为np是不在顶级环境的范围内。就 Coq 的理论而言，你的陈述 的证明将 必须在某个时候破坏 n。

虽然我不知道有什么策略可以自动解决这类问题，但想出一些自定义的 ltac 代码来轻松解决您的问题并不难：

Ltac solve_eq :=
  try reflexivity;
  match goal with
  | |- match ?x with _ => _ end
       = match ?x with _ => _ end =>
    destruct x; auto
  end.

Goal forall (n : nat), dummy_s n = dummy_t n.
Proof.
  intro n. unfold dummy_s. unfold dummy_t.
  solve_eq.
Qed.

如果你的外延等式结果是出现在你上下文中的假设，那么solve_eq应该可以解决很多这种形状的目标；如果没有，您可能需要向提示数据库中添加额外的引理。

重写策略无法在模式匹配中找到术语出现

Rewrite tactic fails to find term occurrence within pattern matching

coq