证明用地图构造的列表相等

Question

我有两个列表，一个直接通过递归构造，另一个使用映射操作构造。我试图证明它们是平等的，但令人惊讶的是我卡住了。

Require Import Coq.Lists.List.
Import ListNotations.

Fixpoint ls_zeroes n :=
  match n with
  | 0 => nil
  | S n' => 0 :: ls_zeroes n'
  end.

Fixpoint ls_ones n := map S (ls_zeroes n).
Fixpoint ls_ones' n :=
  match n with
  | 0 => nil
  | S n' => 1 :: ls_ones' n'
  end.

Goal forall n, ls_ones n = ls_ones' n.
Proof.
  intros.
  induction n.
  - reflexivity.
  - simpl. f_equal. (* ??? *)
Abort.

上下文是这样的：

1 subgoal
n : nat
IHn : ls_ones n = ls_ones' n
______________________________________(1/1)
map S (ls_zeroes n) = ls_ones' n

我认为 fold ls_ones 会 map S (ls_zeroes n) 变成 ls_ones n 因为那是字面上 ls_ones 的定义，但它什么也没做。如果我尝试 unfold ls_ones in IHn 我得到一个讨厌的递归表达式而不是 ls_ones.

的逐字定义

完成这个证明的最简洁的方法是什么？

Answer 1

I thought fold ls_ones would map S (ls_zeroes n) into ls_ones n since that's literally the definition of ls_ones

是吗？你说的是Fixpoint ls_ones，不是Definition。就像任何 Fixpoint 一样，这意味着 ls_ones 的给定定义被转换为 fix。给定的定义中没有递归结构，所以这是没有意义的，但你说要做，Coq 就做。发出 Print ls_ones. 以查看实际定义。真正的解决办法是让 ls_ones 变成 Definition.

如果您不解决这个问题，Coq 只会在递归参数以构造函数开头时减少 Fixpoint。然后，为了完成这个证明，你需要 destruct n 来显示那些构造函数：

Goal forall n, ls_ones n = ls_ones' n.
Proof.
  intros.
  induction n.
  - reflexivity.
  - simpl. f_equal. destruct n; assumption.
Qed.

Answer 2

请注意，当您定义 ls_one 并展开您得到的定义时：

(fix ls_ones (n0 : nat) : list nat := map S (ls_zeroes n0)) n = ls_ones' n

问题是 ls_one 不是一个固定点。实际上，它不会进行递归。一旦 coq 自动定义点 {struct n0}（在这种情况下为 n 参数），您的证明就会卡住，因为 n 永远不会在 P k -> P (k + 1) 中被破坏，因为 k 没有被破坏。使用 :

Definition ls_ones n := map S (ls_zeroes n).

证明变得微不足道：

Goal forall n, ls_ones n = ls_ones' n.
Proof.
  intros.
  induction n.
  trivial.
  unfold ls_ones in *.
  simpl.
  rewrite IHn.
  trivial.
Qed.

Answer 3

不幸的是，由于您的定义中的值是固定的，您必须使用归纳法来进行证明：

From mathcomp Require Import all_ssreflect.

Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.

Fixpoint seq0 n :=
  match n with
  | 0 => nil
  | S n' => 0 :: seq0 n'
  end.

Fixpoint seq1 n :=
  match n with
  | 0 => nil
  | S n' => 1 :: seq1 n'
  end.

Lemma eq_F n : seq1 n = [seq n.+1 | n <- seq0 n].
Proof. by elim: n => //= n ->. Qed.

虽然没有太多证据可以证明。我建议使用更通用的 nseq count elem 函数而不是定义您自己的重复结构，然后从关于 map:

的一般引理中可以很快得到证明

Lemma eq_G n : nseq n 1 = [seq n.+1 | n <- nseq n 0].
Proof. by rewrite map_nseq. Qed.

证明用地图构造的列表相等

Prove equality on list constructed with a map

coq

coq-tactic