How to prove StronglySorted list consing in coq?

Question

I am trying to make a tower of Hanoi proof in Coq as a learning exercise. I am stuck with a last goal on my first proof after many hours of fruitless attempts.

Could you please explain why my program is failing, and how to correct it?

Edit: looking back at the code, it seems that I need to prove StronglySorted le (l:list nat) before I can prove ordered_stacking, isn'it?

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.

Output:

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)

Arthur Azevedo De Amorim Arthur Azevedo De Amorim · Accepted Answer · 2018-06-20T12:24:04

The problem is that you didn't record the fact that n <= hl after destructing that boolean. Here is a solution:

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.

How to prove StronglySorted list consing in coq?

1 Answers