在归纳的递归步骤中使用 Fixpoint 的 'unfold'

Question

我试图在 coq 中证明一些东西，但同样的问题不断出现；我想在归纳的递归（非零）步骤中展开 Fixpoint 的定义。展开按预期工作，这是一个示例：

展开列表前反向（rev）定义：

  n : nat
  l' : natlist
  IHl' : rev (rev l') = l'
  ============================
  rev (rev (n :: l')) = n :: l'

之后：

  n : nat
  l' : natlist
  IHl' : rev (rev l') = l'
  ============================
  (fix rev (l : natlist) : natlist := match l with
                                      | [ ] => [ ]
                                      | h :: t => rev t ++ [h]
                                      end)
    ((fix rev (l : natlist) : natlist := match l with
                                         | [ ] => [ ]
                                         | h :: t => rev t ++ [h]
                                         end) l' ++ [n]) = n :: l'

到目前为止一切顺利。现在我希望 simpl 弄清楚我在归纳的非零情况下，因为 n :: l' 永远不会为零，并简化匹配的 nil 情况 ([ ] => [ ])，仅保留定义的非 nil 部分。

不幸的是，它并没有隐含地这样做。如何使递归 Fixpoint 定义的 unfold 与归纳相得益彰？我如何获得：

  n : nat
  l' : natlist
  IHl' : rev (rev l') = l'
  ============================
  rev (rev l' ++ [n]) = n :: l'

根据内部 rev 的 rev 定义。

注意：此处与列表的使用无关，相同的技术可用于任何归纳定义的类型。

编辑： 导致 After 状态的 rev 和证明的定义。

Fixpoint rev (l:natlist) : natlist :=
  match l with
  | nil    => nil
  | h :: t => rev t ++ [h]
  end.

Theorem rev_involutive : forall l : natlist,
  rev (rev l) = l.
Proof.
  intros l. induction l as [| n l'].
  - reflexivity.
  - unfold rev.

Answer 1

您的 After: 基本上是 rev (rev l' ++ [n])（rev 展开），这意味着您希望看到的减少已经发生。现在你可能想证明一个类似于 rev (xs ++ ys) = rev ys ++ rev xs.

的辅助引理

在归纳的递归步骤中使用 Fixpoint 的 'unfold'

Using 'unfold' of a Fixpoint inside the recursive step of the induction

coq

coq-tactic