如何在 coq 中证明 StronglySorted 列表 consing？

Question

我正在尝试在 Coq 中制作一个 Hanoi 塔作为学习练习。经过数小时无果而终的尝试后，我在第一个证明中坚持了最后一个目标。

能否解释一下我的程序失败的原因，以及如何更正它？

编辑：回头看代码，好像要先证明StronglySorted le (l:list nat)才能证明ordered_stacking，不是吗？

Require Import List.
Require Import Arith.
Require Import Coq.Sorting.Sorting.

Definition stack_disk :=
  fun (n:nat) (l:list nat) =>
    match l with
      | nil => n::nil
      | n'::l' =>
          if n' <? n
          then n::l
          else l
    end.

Eval compute in (stack_disk 2 (1::0::nil)).
Eval compute in (stack_disk 2 (2::1::0::nil)).

Lemma ordered_stacking: forall (n:nat) (l:list nat),
  StronglySorted le l -> StronglySorted le (stack_disk n l) -> StronglySorted le (n::l).
  Proof.
    intros n l H.
    induction l as [|hl tl];simpl;auto.
    destruct (hl <? n).
    auto.
    constructor.
    apply H.

输出：

1 subgoal
n, hl : nat
tl : list nat
H : StronglySorted le (hl :: tl)
IHtl : StronglySorted le tl ->
       StronglySorted le (stack_disk n tl) -> StronglySorted le (n :: tl)
H0 : StronglySorted le (hl :: tl)
______________________________________(1/1)
Forall (le n) (hl :: tl)

Answer 1

问题是你没有记录 n <= hl 在破坏那个布尔值之后的事实。这是一个解决方案：

Require Import List.
Require Import Arith.
Require Import Coq.Sorting.Sorting.

Definition stack_disk :=
  fun (n:nat) (l:list nat) =>
    match l with
      | nil => n::nil
      | n'::l' =>
          if n' <? n
          then n::l
          else l
    end.

Lemma ordered_stacking: forall (n:nat) (l:list nat),
  StronglySorted le l -> StronglySorted le (stack_disk n l) -> StronglySorted le (n::l).
Proof.
  intros n [|m l].
  - intros _ _; repeat constructor.
  - simpl. intros H1 H2.
    destruct (Nat.ltb_spec m n); trivial.
    constructor; trivial.
    apply StronglySorted_inv in H1.
    destruct H1 as [_ H1].
    constructor; trivial.
    revert H1; apply Forall_impl.
    now intros p; apply Nat.le_trans.
Qed.

如何在 coq 中证明 StronglySorted 列表 consing？

How to prove StronglySorted list consing in coq?

coq

proof

formal-verification