Library CompOptCert.Wfsimpl
Defining recursive functions by Noetherian induction. This is a simplified
interface to the Wf module of Coq's standard library, where the functions
to be defined have non-dependent types, and function extensionality is assumed.
Require Import Axioms.
Require Import Init.Wf.
Require Import Wf_nat.
Set Implicit Arguments.
Section FIX.
Variables A B: Type.
Variable R: A → A → Prop.
Hypothesis Rwf: well_founded R.
Variable F: ∀ (x: A), (∀ (y: A), R y x → B) → B.
Definition Fix (x: A) : B := Wf.Fix Rwf (fun (x: A) ⇒ B) F x.
Theorem unroll_Fix:
∀ x, Fix x = F (fun (y: A) (P: R y x) ⇒ Fix y).
Proof.
unfold Fix; intros. apply Wf.Fix_eq with (P := fun (x: A) ⇒ B).
intros. assert (f = g). apply functional_extensionality_dep; intros.
apply functional_extensionality; intros. auto.
subst g; auto.
Qed.
End FIX.
Same, with a nonnegative measure instead of a well-founded ordering
Section FIXM.
Variables A B: Type.
Variable measure: A → nat.
Variable F: ∀ (x: A), (∀ (y: A), measure y < measure x → B) → B.
Definition Fixm (x: A) : B := Wf.Fix (well_founded_ltof A measure) (fun (x: A) ⇒ B) F x.
Theorem unroll_Fixm:
∀ x, Fixm x = F (fun (y: A) (P: measure y < measure x) ⇒ Fixm y).
Proof.
unfold Fixm; intros. apply Wf.Fix_eq with (P := fun (x: A) ⇒ B).
intros. assert (f = g). apply functional_extensionality_dep; intros.
apply functional_extensionality; intros. auto.
subst g; auto.
Qed.
End FIXM.