Library Deduxit.Linear.TermsCheck
Terms for the checkers
From Stdlib Require Import Bool List.
From Deduxit.Linear Require Export Terms.
Import ListNotations.
Section Equality.
Context {symbol : Type} (symbol_eqb : symbol → symbol → bool).
Local Notation term := (term symbol).
Structural equality of terms, comparing symbols with
symbol_eqb.
Fixpoint term_eqb (t u : term) : bool :=
match t, u with
| bound n, bound m ⇒ Nat.eqb n m
| eigen a, eigen b ⇒ Nat.eqb a b
| tapp f l, tapp g k ⇒
symbol_eqb f g &&
(fix terms_eqb (l k : list term) : bool :=
match l, k with
| [], [] ⇒ true
| t :: l, u :: k ⇒ term_eqb t u && terms_eqb l k
| _, _ ⇒ false
end) l k
| _, _ ⇒ false
end.
match t, u with
| bound n, bound m ⇒ Nat.eqb n m
| eigen a, eigen b ⇒ Nat.eqb a b
| tapp f l, tapp g k ⇒
symbol_eqb f g &&
(fix terms_eqb (l k : list term) : bool :=
match l, k with
| [], [] ⇒ true
| t :: l, u :: k ⇒ term_eqb t u && terms_eqb l k
| _, _ ⇒ false
end) l k
| _, _ ⇒ false
end.
Equality of lists of terms.
Fixpoint terms_eqb (l k : list term) : bool :=
match l, k with
| [], [] ⇒ true
| t :: l, u :: k ⇒ term_eqb t u && terms_eqb l k
| _, _ ⇒ false
end.
match l, k with
| [], [] ⇒ true
| t :: l, u :: k ⇒ term_eqb t u && terms_eqb l k
| _, _ ⇒ false
end.
Induction on terms, with an induction hypothesis for every
argument of an application.
Lemma term_ind' (P : term → Prop) :
(∀ n, P (bound n)) → (∀ a, P (eigen a)) →
(∀ f l, List.Forall P l → P (tapp f l)) → ∀ t, P t.
Proof.
intros Hb He Ha. fix IH 1. intros [n | a | f l]; [apply Hb | apply He | apply Ha].
induction l as [| t l IHl]; constructor; [apply IH | exact IHl].
Qed.
(∀ n, P (bound n)) → (∀ a, P (eigen a)) →
(∀ f l, List.Forall P l → P (tapp f l)) → ∀ t, P t.
Proof.
intros Hb He Ha. fix IH 1. intros [n | a | f l]; [apply Hb | apply He | apply Ha].
induction l as [| t l IHl]; constructor; [apply IH | exact IHl].
Qed.
symbol_eqb decides equality.
Hypothesis symbol_eqb_spec : ∀ f g, reflect (f = g) (symbol_eqb f g).
Lemma term_eqb_iff : ∀ t u, term_eqb t u = true ↔ t = u.
Proof.
induction t as [n | a | f l IH] using term_ind'; destruct u as [m | b | g k]; cbn;
try (split; [discriminate | congruence]).
- rewrite PeanoNat.Nat.eqb_eq. split; congruence.
- rewrite PeanoNat.Nat.eqb_eq. split; congruence.
- destruct (symbol_eqb_spec f g) as [<- | ne]; cbn;
[| split; [discriminate | congruence]].
revert k; induction IH as [| t l Ht _ IHl]; intros [| u k]; cbn;
try (split; [discriminate | congruence]); [split; reflexivity |].
rewrite andb_true_iff, Ht, IHl. split.
+ intros [-> E]. injection E as →. reflexivity.
+ intros E. injection E as → →. split; reflexivity.
Qed.
Lemma term_eqb_spec : ∀ t u, reflect (t = u) (term_eqb t u).
Proof. intros t u. apply iff_reflect. symmetry. apply term_eqb_iff. Qed.
Lemma terms_eqb_spec : ∀ l k, reflect (l = k) (terms_eqb l k).
Proof.
induction l as [| t l IH]; intros [| u k]; cbn; try (constructor; congruence).
destruct (term_eqb_spec t u) as [<- | ne]; cbn; [| constructor; congruence].
destruct (IH k); constructor; congruence.
Qed.
End Equality.
Section Eigenvariables.
Context {symbol : Type}.
Local Notation term := (term symbol).
Lemma term_eqb_iff : ∀ t u, term_eqb t u = true ↔ t = u.
Proof.
induction t as [n | a | f l IH] using term_ind'; destruct u as [m | b | g k]; cbn;
try (split; [discriminate | congruence]).
- rewrite PeanoNat.Nat.eqb_eq. split; congruence.
- rewrite PeanoNat.Nat.eqb_eq. split; congruence.
- destruct (symbol_eqb_spec f g) as [<- | ne]; cbn;
[| split; [discriminate | congruence]].
revert k; induction IH as [| t l Ht _ IHl]; intros [| u k]; cbn;
try (split; [discriminate | congruence]); [split; reflexivity |].
rewrite andb_true_iff, Ht, IHl. split.
+ intros [-> E]. injection E as →. reflexivity.
+ intros E. injection E as → →. split; reflexivity.
Qed.
Lemma term_eqb_spec : ∀ t u, reflect (t = u) (term_eqb t u).
Proof. intros t u. apply iff_reflect. symmetry. apply term_eqb_iff. Qed.
Lemma terms_eqb_spec : ∀ l k, reflect (l = k) (terms_eqb l k).
Proof.
induction l as [| t l IH]; intros [| u k]; cbn; try (constructor; congruence).
destruct (term_eqb_spec t u) as [<- | ne]; cbn; [| constructor; congruence].
destruct (IH k); constructor; congruence.
Qed.
End Equality.
Section Eigenvariables.
Context {symbol : Type}.
Local Notation term := (term symbol).
The eigenvariables of a term, with repetitions.
Fixpoint teigens (t : term) : list nat :=
match t with
| bound _ ⇒ []
| eigen a ⇒ [a]
| tapp _ l ⇒ flat_map teigens l
end.
Lemma teigens_occurs : ∀ a (t : term), In a (teigens t) ↔ toccurs a t = true.
Proof.
intros a t. induction t as [n | b | f l IH] using term_ind'; cbn.
- split; [contradiction | discriminate].
- rewrite PeanoNat.Nat.eqb_eq. split; [intros [-> | []]; reflexivity | intros ->; left; reflexivity].
- rewrite in_flat_map, existsb_exists, Forall_forall in ×.
split; intros [t [Hin Ht]]; ∃ t; split; try exact Hin; apply IH; assumption.
Qed.
Lemma toccurs_tsubst : ∀ b k (u t : term),
toccurs b (tsubst k u t) = true → toccurs b t = true ∨ toccurs b u = true.
Proof.
intros b k u t. induction t as [n | a | f l IH] using term_ind'; cbn.
- destruct (Nat.eqb n k); cbn; auto.
- auto.
- rewrite !existsb_exists, Forall_forall in ×. intros [t' [Hin Ht]].
apply in_map_iff in Hin as [t [<- Hin]].
destruct (IH t Hin Ht) as [H | H]; [left; ∃ t; auto | right; exact H].
Qed.
End Eigenvariables.
match t with
| bound _ ⇒ []
| eigen a ⇒ [a]
| tapp _ l ⇒ flat_map teigens l
end.
Lemma teigens_occurs : ∀ a (t : term), In a (teigens t) ↔ toccurs a t = true.
Proof.
intros a t. induction t as [n | b | f l IH] using term_ind'; cbn.
- split; [contradiction | discriminate].
- rewrite PeanoNat.Nat.eqb_eq. split; [intros [-> | []]; reflexivity | intros ->; left; reflexivity].
- rewrite in_flat_map, existsb_exists, Forall_forall in ×.
split; intros [t [Hin Ht]]; ∃ t; split; try exact Hin; apply IH; assumption.
Qed.
Lemma toccurs_tsubst : ∀ b k (u t : term),
toccurs b (tsubst k u t) = true → toccurs b t = true ∨ toccurs b u = true.
Proof.
intros b k u t. induction t as [n | a | f l IH] using term_ind'; cbn.
- destruct (Nat.eqb n k); cbn; auto.
- auto.
- rewrite !existsb_exists, Forall_forall in ×. intros [t' [Hin Ht]].
apply in_map_iff in Hin as [t [<- Hin]].
destruct (IH t Hin Ht) as [H | H]; [left; ∃ t; auto | right; exact H].
Qed.
End Eigenvariables.