如何仅扩展 `fix` 函数一步?

huangapple go评论58阅读模式
英文:

How does one expand a `fix` function just one step?

问题

I have defined a recursive function with fix, and now I want to prove a rewriting equation about it.

The function in question is a bit big, but here is another function that has the same problem. (Here is an interactive Coq proof with it: Link)

I want to prove the following goal:

Goal forall n, test (S n) = S n + test n.

Proof. 
   induction n. 
   reflexivity.
   unfold test.

but when I start working on it, I get a proof term with fix test. Now I just want to unfold this once, but cbv delta evaluates too much.

How can I reduce the fix function definition just once?

Here is the proof obligation:

n: nat
IHn: test (S n) = test n + S n
1/1
(fix test (n0 : nat) (H : Acc lt n0) {struct H} : nat :=
   match Nat.eq_dec 0 n0 with
   | left _ => n0
   | right H0 =>
       n0 +
       test (n0 - 1)
         (match H with
          | Acc_intro _ H1 => H1
          end (n0 - 1)
            (Nat.sub_lt n0 1
               (Arith_prebase.gt_le_S_stt 0 n0
                  (Arith_prebase.neq_0_lt_stt n0 H0))
               (le_n 1)))
   end) (S (S n)) (lt_wf (S (S n))) =
(fix test (n0 : nat) (H : Acc lt n0) {struct H} : nat :=
   match Nat.eq_dec 0 n0 with
   | left _ => n0
   | right H0 =>
       n0 +
       test (n0 - 1)
         (match H with
          | Acc_intro _ H1 => H1
          end (n0 - 1)
            (Nat.sub_lt n0 1
               (Arith_prebase.gt_le_S_stt 0 n0
                  (Arith_prebase.neq_0_lt_stt n0 H0))
               (le_n 1)))
   end) (S n) (lt_wf (S n)) + S (S n)
英文:

I have defined a recursive function with fix, and now I want to prove a rewriting equation about it.
The function in question is a bit big, but here is another function that has the same problem.
(Here is an interactive collacoq with it: https://x80.org/collacoq/aweboxoxuy.coq)

Require Import Wf_nat PeanoNat.

Definition test (n: nat): nat. 
refine (
  let test := 
    fix test n (H: Acc lt n) {struct H} := 
      if Nat.eq_dec 0 n 
      then n 
      else n + test (n-1) _ 
  in 
    test n (Wf_nat.lt_wf n)).

  apply H; auto with arith.
Defined.

(* a unit test to see it works as intended. *)
Check eq_refl (test 4 = 4 + test 3).  

I want to prove the following goal

Goal forall n, test (S n) = S n + test n.

Proof. 
   induction n. 
   reflexivity.
   unfold test.

but when I start working on it, I get a proof term with fix test
Now I just want to unfold this once, but cbv delta evaluates too much.

How can I reduce the fix function definition just once?

Here is the proof obligation

n: nat
IHn: test (S n) = test n + S n
1/1
(fix test (n0 : nat) (H : Acc lt n0) {struct H} : nat :=
   match Nat.eq_dec 0 n0 with
   | left _ => n0
   | right H0 =>
       n0 +
       test (n0 - 1)
         (match H with
          | Acc_intro _ H1 => H1
          end (n0 - 1)
            (Nat.sub_lt n0 1
               (Arith_prebase.gt_le_S_stt 0 n0
                  (Arith_prebase.neq_0_lt_stt n0 H0)) 
               (le_n 1)))
   end) (S (S n)) (lt_wf (S (S n))) =
(fix test (n0 : nat) (H : Acc lt n0) {struct H} : nat :=
   match Nat.eq_dec 0 n0 with
   | left _ => n0
   | right H0 =>
       n0 +
       test (n0 - 1)
         (match H with
          | Acc_intro _ H1 => H1
          end (n0 - 1)
            (Nat.sub_lt n0 1
               (Arith_prebase.gt_le_S_stt 0 n0
                  (Arith_prebase.neq_0_lt_stt n0 H0)) 
               (le_n 1)))
   end) (S n) (lt_wf (S n)) + S (S n)

答案1

得分: 2

使用由良好性定义的函数总是棘手的。其中一个原因是你经常会被复杂的术语淹没。

你证明的主要问题是(由于你的归纳),你正在创建(S (S n)),因此你的函数通过简化而减小得太多!

事实上,你不需要通过归纳来证明你的引理。

让我们试着传达一些直觉。你的定义看起来像这样。

test n = f n (lt_wf n)

所以你的函数是由证明(lt_wf n)的可访问性定义的。你实际上需要证明的是f不依赖于实际的证明。

Lemma f_eq: forall n H1 H2, f n H1 = f n H2.

然后你就可以执行简化。

这是你引理的证明。

Goal forall n, test (S n) = S n + test n.
Proof.
intros n.
apply f_equal2 with (f := Nat.add); [trivial |].
set (f := ((fix test (k : _) (H : Acc lt k) {struct H} : _ := _))).
set (H := (_ : Acc _ (S n - 1))).
assert (f_eq: forall n H1 H2, f n H1 = f n H2).
- intros n1.
  induction n1.
  + intros H1 H2.
    dependent inversion H1; dependent inversion H2; simpl; auto.
  + intros H1 H2.
    dependent inversion H1; dependent inversion H2.
    apply f_equal2 with (f := Nat.add).
    * trivial.
    * destruct n1; apply IHn1.
- destruct n; apply f_eq.
Qed.
英文:

Working with function defined by well-foundness is always tricky. One reason is that you are often drown under big terms.
The main problem of your proof is (because of your induction) you are creating (S (S n)) so your function reduces too much by simplification!
As a matter of fact you don't need to prove your lemma by induction.
Let us try to convey some intuition. Your definition looks like.

test n = f n (lt_wf n)

so your function is defined by accessibility with the proof (lt_wf n). What you actually need to prove is that f does not depend on the actual proof.

Lemma f_eq : forall n H1 H2, f n H1 = f n H2.

and you will be able to perform simplification.

Here is a proof of your Lemma

Goal forall n, test (S n) = S n + test n.
Proof.
intros n.
apply f_equal2 with (f := Nat.add); [trivial |].
set (f := ((fix test (k : _) (H : Acc lt k) {struct H} : _ := _))).
set (H := (_ : Acc _ (S n - 1))).
assert (f_eq : forall n H1 H2, f n H1 = f n H2).
- intros n1.
  induction n1.
  + intros H1 H2.
    dependent inversion H1; dependent inversion H2; simpl; auto.
  + intros H1 H2.
    dependent inversion H1; dependent inversion H2.
    apply f_equal2 with (f := Nat.add).
    * trivial.
    * destruct n1; apply IHn1.
- destruct n; apply f_eq.
Qed.

huangapple
  • 本文由 发表于 2023年2月9日 01:38:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/75389706.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定