diff options
Diffstat (limited to 'theories')
| -rw-r--r-- | theories/FSets/FMapAVL.v | 8 | ||||
| -rw-r--r-- | theories/Init/Notations.v | 35 | ||||
| -rw-r--r-- | theories/Init/Specif.v | 29 | ||||
| -rw-r--r-- | theories/Logic/WKL.v | 2 | ||||
| -rw-r--r-- | theories/Numbers/Cyclic/Int63/Int63.v | 2 | ||||
| -rw-r--r-- | theories/PArith/BinPos.v | 2 | ||||
| -rw-r--r-- | theories/Structures/OrderedTypeEx.v | 200 | ||||
| -rw-r--r-- | theories/Vectors/VectorSpec.v | 202 | ||||
| -rw-r--r-- | theories/dune | 38 | ||||
| -rw-r--r-- | theories/micromega/Lia.v | 2 | ||||
| -rw-r--r-- | theories/micromega/Lqa.v | 2 | ||||
| -rw-r--r-- | theories/micromega/Lra.v | 2 | ||||
| -rw-r--r-- | theories/micromega/ZArith_hints.v | 43 | ||||
| -rw-r--r-- | theories/omega/Omega.v | 34 | ||||
| -rw-r--r-- | theories/setoid_ring/Field_tac.v | 4 | ||||
| -rw-r--r-- | theories/setoid_ring/Rings_Z.v | 1 |
16 files changed, 507 insertions, 99 deletions
diff --git a/theories/FSets/FMapAVL.v b/theories/FSets/FMapAVL.v index 82055c4752..f78c0ecc1e 100644 --- a/theories/FSets/FMapAVL.v +++ b/theories/FSets/FMapAVL.v @@ -550,14 +550,14 @@ Ltac intuition_in := repeat (intuition; inv In; inv MapsTo). Let's do its job by hand: *) Ltac join_tac := - intros l; induction l as [| ll _ lx ld lr Hlr lh]; - [ | intros x d r; induction r as [| rl Hrl rx rd rr _ rh]; unfold join; - [ | destruct (gt_le_dec lh (rh+2)) as [GT|LE]; + intros ?l; induction l as [| ?ll _ ?lx ?ld ?lr ?Hlr ?lh]; + [ | intros ?x ?d ?r; induction r as [| ?rl ?Hrl ?rx ?rd ?rr _ ?rh]; unfold join; + [ | destruct (gt_le_dec lh (rh+2)) as [?GT|?LE]; [ match goal with |- context [ bal ?u ?v ?w ?z ] => replace (bal u v w z) with (bal ll lx ld (join lr x d (Node rl rx rd rr rh))); [ | auto] end - | destruct (gt_le_dec rh (lh+2)) as [GT'|LE']; + | destruct (gt_le_dec rh (lh+2)) as [?GT'|?LE']; [ match goal with |- context [ bal ?u ?v ?w ?z ] => replace (bal u v w z) with (bal (join (Node ll lx ld lr lh) x d rl) rx rd rr); [ | auto] diff --git a/theories/Init/Notations.v b/theories/Init/Notations.v index fdb88a0c82..a5e4178b93 100644 --- a/theories/Init/Notations.v +++ b/theories/Init/Notations.v @@ -68,33 +68,40 @@ Reserved Notation "{ x }" (at level 0, x at level 99). (** Notations for sigma-types or subsets *) -Reserved Notation "{ A } + { B }" (at level 50, left associativity). -Reserved Notation "A + { B }" (at level 50, left associativity). +Reserved Notation "{ A } + { B }" (at level 50, left associativity). +Reserved Notation "A + { B }" (at level 50, left associativity). -Reserved Notation "{ x | P }" (at level 0, x at level 99). -Reserved Notation "{ x | P & Q }" (at level 0, x at level 99). +Reserved Notation "{ x | P }" (at level 0, x at level 99). +Reserved Notation "{ x | P & Q }" (at level 0, x at level 99). -Reserved Notation "{ x : A | P }" (at level 0, x at level 99). -Reserved Notation "{ x : A | P & Q }" (at level 0, x at level 99). +Reserved Notation "{ x : A | P }" (at level 0, x at level 99). +Reserved Notation "{ x : A | P & Q }" (at level 0, x at level 99). -Reserved Notation "{ x & P }" (at level 0, x at level 99). -Reserved Notation "{ x : A & P }" (at level 0, x at level 99). -Reserved Notation "{ x : A & P & Q }" (at level 0, x at level 99). +Reserved Notation "{ x & P }" (at level 0, x at level 99). +Reserved Notation "{ x & P & Q }" (at level 0, x at level 99). + +Reserved Notation "{ x : A & P }" (at level 0, x at level 99). +Reserved Notation "{ x : A & P & Q }" (at level 0, x at level 99). Reserved Notation "{ ' pat | P }" - (at level 0, pat strict pattern, format "{ ' pat | P }"). + (at level 0, pat strict pattern, format "{ ' pat | P }"). Reserved Notation "{ ' pat | P & Q }" - (at level 0, pat strict pattern, format "{ ' pat | P & Q }"). + (at level 0, pat strict pattern, format "{ ' pat | P & Q }"). Reserved Notation "{ ' pat : A | P }" (at level 0, pat strict pattern, format "{ ' pat : A | P }"). Reserved Notation "{ ' pat : A | P & Q }" - (at level 0, pat strict pattern, format "{ ' pat : A | P & Q }"). + (at level 0, pat strict pattern, format "{ ' pat : A | P & Q }"). + +Reserved Notation "{ ' pat & P }" + (at level 0, pat strict pattern, format "{ ' pat & P }"). +Reserved Notation "{ ' pat & P & Q }" + (at level 0, pat strict pattern, format "{ ' pat & P & Q }"). Reserved Notation "{ ' pat : A & P }" - (at level 0, pat strict pattern, format "{ ' pat : A & P }"). + (at level 0, pat strict pattern, format "{ ' pat : A & P }"). Reserved Notation "{ ' pat : A & P & Q }" - (at level 0, pat strict pattern, format "{ ' pat : A & P & Q }"). + (at level 0, pat strict pattern, format "{ ' pat : A & P & Q }"). (** Support for Gonthier-Ssreflect's "if c is pat then u else v" *) diff --git a/theories/Init/Specif.v b/theories/Init/Specif.v index 692fe3d8d0..59ee252d35 100644 --- a/theories/Init/Specif.v +++ b/theories/Init/Specif.v @@ -58,23 +58,26 @@ Arguments sig2 (A P Q)%type. Arguments sigT (A P)%type. Arguments sigT2 (A P Q)%type. -Notation "{ x | P }" := (sig (fun x => P)) : type_scope. -Notation "{ x | P & Q }" := (sig2 (fun x => P) (fun x => Q)) : type_scope. -Notation "{ x : A | P }" := (sig (A:=A) (fun x => P)) : type_scope. -Notation "{ x : A | P & Q }" := (sig2 (A:=A) (fun x => P) (fun x => Q)) : +Notation "{ x | P }" := (sig (fun x => P)) : type_scope. +Notation "{ x | P & Q }" := (sig2 (fun x => P) (fun x => Q)) : type_scope. +Notation "{ x : A | P }" := (sig (A:=A) (fun x => P)) : type_scope. +Notation "{ x : A | P & Q }" := (sig2 (A:=A) (fun x => P) (fun x => Q)) : type_scope. -Notation "{ x & P }" := (sigT (fun x => P)) : type_scope. -Notation "{ x : A & P }" := (sigT (A:=A) (fun x => P)) : type_scope. -Notation "{ x : A & P & Q }" := (sigT2 (A:=A) (fun x => P) (fun x => Q)) : +Notation "{ x & P }" := (sigT (fun x => P)) : type_scope. +Notation "{ x & P & Q }" := (sigT2 (fun x => P) (fun x => Q)) : type_scope. +Notation "{ x : A & P }" := (sigT (A:=A) (fun x => P)) : type_scope. +Notation "{ x : A & P & Q }" := (sigT2 (A:=A) (fun x => P) (fun x => Q)) : type_scope. -Notation "{ ' pat | P }" := (sig (fun pat => P)) : type_scope. -Notation "{ ' pat | P & Q }" := (sig2 (fun pat => P) (fun pat => Q)) : type_scope. -Notation "{ ' pat : A | P }" := (sig (A:=A) (fun pat => P)) : type_scope. -Notation "{ ' pat : A | P & Q }" := (sig2 (A:=A) (fun pat => P) (fun pat => Q)) : +Notation "{ ' pat | P }" := (sig (fun pat => P)) : type_scope. +Notation "{ ' pat | P & Q }" := (sig2 (fun pat => P) (fun pat => Q)) : type_scope. +Notation "{ ' pat : A | P }" := (sig (A:=A) (fun pat => P)) : type_scope. +Notation "{ ' pat : A | P & Q }" := (sig2 (A:=A) (fun pat => P) (fun pat => Q)) : type_scope. -Notation "{ ' pat : A & P }" := (sigT (A:=A) (fun pat => P)) : type_scope. -Notation "{ ' pat : A & P & Q }" := (sigT2 (A:=A) (fun pat => P) (fun pat => Q)) : +Notation "{ ' pat & P }" := (sigT (fun pat => P)) : type_scope. +Notation "{ ' pat & P & Q }" := (sigT2 (fun pat => P) (fun pat => Q)) : type_scope. +Notation "{ ' pat : A & P }" := (sigT (A:=A) (fun pat => P)) : type_scope. +Notation "{ ' pat : A & P & Q }" := (sigT2 (A:=A) (fun pat => P) (fun pat => Q)) : type_scope. Add Printing Let sig. diff --git a/theories/Logic/WKL.v b/theories/Logic/WKL.v index 478bc434ad..d9eea2f89d 100644 --- a/theories/Logic/WKL.v +++ b/theories/Logic/WKL.v @@ -25,7 +25,7 @@ Require Import WeakFan List. Import ListNotations. -Require Import Omega. +Require Import Arith. (** [is_path_from P n l] means that there exists a path of length [n] from [l] on which [P] does not hold *) diff --git a/theories/Numbers/Cyclic/Int63/Int63.v b/theories/Numbers/Cyclic/Int63/Int63.v index c4f738ac39..bacc4a7650 100644 --- a/theories/Numbers/Cyclic/Int63/Int63.v +++ b/theories/Numbers/Cyclic/Int63/Int63.v @@ -690,7 +690,7 @@ Proof. now intros h; rewrite (to_Z_inj _ 0 h). Qed. Lemma tail00_spec x : φ x = 0 -> φ (tail0 x) = φ digits. Proof. now intros h; rewrite (to_Z_inj _ 0 h). Qed. -Infix "≡" := (eqm wB) (at level 80) : int63_scope. +Infix "≡" := (eqm wB) (at level 70, no associativity) : int63_scope. Lemma eqm_mod x y : x mod wB ≡ y mod wB → x ≡ y. Proof. diff --git a/theories/PArith/BinPos.v b/theories/PArith/BinPos.v index 387ab75362..4179765dca 100644 --- a/theories/PArith/BinPos.v +++ b/theories/PArith/BinPos.v @@ -1753,7 +1753,7 @@ Qed. Ltac destr_pggcdn IHn := match goal with |- context [ ggcdn _ ?x ?y ] => - generalize (IHn x y); destruct ggcdn as (g,(u,v)); simpl + generalize (IHn x y); destruct ggcdn as (?g,(?u,?v)); simpl end. Lemma ggcdn_correct_divisors : forall n a b, diff --git a/theories/Structures/OrderedTypeEx.v b/theories/Structures/OrderedTypeEx.v index 288aa0c789..83c690ab71 100644 --- a/theories/Structures/OrderedTypeEx.v +++ b/theories/Structures/OrderedTypeEx.v @@ -317,6 +317,82 @@ Module PositiveOrderedTypeBits <: UsualOrderedType. End PositiveOrderedTypeBits. +Module Ascii_as_OT <: UsualOrderedType. + Definition t := ascii. + + Definition eq := @eq ascii. + Definition eq_refl := @eq_refl t. + Definition eq_sym := @eq_sym t. + Definition eq_trans := @eq_trans t. + + Definition cmp (a b : ascii) : comparison := + N.compare (N_of_ascii a) (N_of_ascii b). + + Lemma cmp_eq (a b : ascii): + cmp a b = Eq <-> a = b. + Proof. + unfold cmp. + rewrite N.compare_eq_iff. + split. 2:{ intro. now subst. } + intro H. + rewrite<- (ascii_N_embedding a). + rewrite<- (ascii_N_embedding b). + now rewrite H. + Qed. + + Lemma cmp_lt_nat (a b : ascii): + cmp a b = Lt <-> (nat_of_ascii a < nat_of_ascii b)%nat. + Proof. + unfold cmp. unfold nat_of_ascii. + rewrite N2Nat.inj_compare. + rewrite Nat.compare_lt_iff. + reflexivity. + Qed. + + Lemma cmp_antisym (a b : ascii): + cmp a b = CompOpp (cmp b a). + Proof. + unfold cmp. + apply N.compare_antisym. + Qed. + + Definition lt (x y : ascii) := (N_of_ascii x < N_of_ascii y)%N. + + Lemma lt_trans (x y z : ascii): + lt x y -> lt y z -> lt x z. + Proof. + apply N.lt_trans. + Qed. + + Lemma lt_not_eq (x y : ascii): + lt x y -> x <> y. + Proof. + intros L H. subst. + exact (N.lt_irrefl _ L). + Qed. + + Local Lemma compare_helper_eq {a b : ascii} (E : cmp a b = Eq): + a = b. + Proof. + now apply cmp_eq. + Qed. + + Local Lemma compare_helper_gt {a b : ascii} (G : cmp a b = Gt): + lt b a. + Proof. + now apply N.compare_gt_iff. + Qed. + + Definition compare (a b : ascii) : Compare lt eq a b := + match cmp a b as z return _ = z -> _ with + | Lt => fun E => LT E + | Gt => fun E => GT (compare_helper_gt E) + | Eq => fun E => EQ (compare_helper_eq E) + end Logic.eq_refl. + + Definition eq_dec (x y : ascii): {x = y} + { ~ (x = y)} := ascii_dec x y. +End Ascii_as_OT. + (** [String] is an ordered type with respect to the usual lexical order. *) Module String_as_OT <: UsualOrderedType. @@ -378,32 +454,106 @@ Module String_as_OT <: UsualOrderedType. apply Nat.lt_irrefl in H2; auto. Qed. - Definition compare x y : Compare lt eq x y. + Fixpoint cmp (a b : string) : comparison := + match a, b with + | EmptyString, EmptyString => Eq + | EmptyString, _ => Lt + | String _ _, EmptyString => Gt + | String a_head a_tail, String b_head b_tail => + match Ascii_as_OT.cmp a_head b_head with + | Lt => Lt + | Gt => Gt + | Eq => cmp a_tail b_tail + end + end. + + Lemma cmp_eq (a b : string): + cmp a b = Eq <-> a = b. Proof. - generalize dependent y. - induction x as [ | a s1]; destruct y as [ | b s2]. - - apply EQ; constructor. - - apply LT; constructor. - - apply GT; constructor. - - destruct ((nat_of_ascii a) ?= (nat_of_ascii b))%nat eqn:ltb. - + assert (a = b). - { - apply Nat.compare_eq in ltb. - assert (ascii_of_nat (nat_of_ascii a) - = ascii_of_nat (nat_of_ascii b)) by auto. - repeat rewrite ascii_nat_embedding in H. - auto. - } - subst. - destruct (IHs1 s2). - * apply LT; constructor; auto. - * apply EQ. unfold eq in e. subst. constructor; auto. - * apply GT; constructor; auto. - + apply nat_compare_lt in ltb. - apply LT; constructor; auto. - + apply nat_compare_gt in ltb. - apply GT; constructor; auto. - Defined. + revert b. + induction a, b; try easy. + cbn. + remember (Ascii_as_OT.cmp _ _) as c eqn:Heqc. symmetry in Heqc. + destruct c; split; try discriminate; + try rewrite Ascii_as_OT.cmp_eq in Heqc; try subst; + try rewrite IHa; intro H. + { now subst. } + { now inversion H. } + { inversion H; subst. rewrite<- Heqc. now rewrite Ascii_as_OT.cmp_eq. } + { inversion H; subst. rewrite<- Heqc. now rewrite Ascii_as_OT.cmp_eq. } + Qed. + + Lemma cmp_antisym (a b : string): + cmp a b = CompOpp (cmp b a). + Proof. + revert b. + induction a, b; try easy. + cbn. rewrite IHa. clear IHa. + remember (Ascii_as_OT.cmp _ _) as c eqn:Heqc. symmetry in Heqc. + destruct c; rewrite Ascii_as_OT.cmp_antisym in Heqc; + destruct Ascii_as_OT.cmp; cbn in *; easy. + Qed. + + Lemma cmp_lt (a b : string): + cmp a b = Lt <-> lt a b. + Proof. + revert b. + induction a as [ | a_head a_tail ], b; try easy; cbn. + { split; trivial. intro. apply lts_empty. } + remember (Ascii_as_OT.cmp _ _) as c eqn:Heqc. symmetry in Heqc. + destruct c; split; intro H; try discriminate; trivial. + { + rewrite Ascii_as_OT.cmp_eq in Heqc. subst. + apply String_as_OT.lts_tail. + apply IHa_tail. + assumption. + } + { + rewrite Ascii_as_OT.cmp_eq in Heqc. subst. + inversion H; subst. { rewrite IHa_tail. assumption. } + exfalso. apply (Nat.lt_irrefl (nat_of_ascii a)). assumption. + } + { + apply String_as_OT.lts_head. + rewrite<- Ascii_as_OT.cmp_lt_nat. + assumption. + } + { + exfalso. inversion H; subst. + { + assert(X: Ascii_as_OT.cmp a a = Eq). { apply Ascii_as_OT.cmp_eq. trivial. } + rewrite Heqc in X. discriminate. + } + rewrite<- Ascii_as_OT.cmp_lt_nat in *. rewrite Heqc in *. discriminate. + } + Qed. + + Local Lemma compare_helper_lt {a b : string} (L : cmp a b = Lt): + lt a b. + Proof. + now apply cmp_lt. + Qed. + + Local Lemma compare_helper_gt {a b : string} (G : cmp a b = Gt): + lt b a. + Proof. + rewrite cmp_antisym in G. + rewrite CompOpp_iff in G. + now apply cmp_lt. + Qed. + + Local Lemma compare_helper_eq {a b : string} (E : cmp a b = Eq): + a = b. + Proof. + now apply cmp_eq. + Qed. + + Definition compare (a b : string) : Compare lt eq a b := + match cmp a b as z return _ = z -> _ with + | Lt => fun E => LT (compare_helper_lt E) + | Gt => fun E => GT (compare_helper_gt E) + | Eq => fun E => EQ (compare_helper_eq E) + end Logic.eq_refl. Definition eq_dec (x y : string): {x = y} + { ~ (x = y)} := string_dec x y. End String_as_OT. diff --git a/theories/Vectors/VectorSpec.v b/theories/Vectors/VectorSpec.v index 466e2bf994..443931e5bb 100644 --- a/theories/Vectors/VectorSpec.v +++ b/theories/Vectors/VectorSpec.v @@ -15,7 +15,7 @@ *) Require Fin. -Require Import VectorDef. +Require Import VectorDef PeanoNat Eqdep_dec. Import VectorNotations. Definition cons_inj {A} {a1 a2} {n} {v1 v2 : t A n} @@ -32,6 +32,8 @@ Defined. (** Lemmas are done for functions that use [Fin.t] but thanks to [Peano_dec.le_unique], all is true for the one that use [lt] *) +(** ** Properties of [nth] and [nth_order] *) + Lemma eq_nth_iff A n (v1 v2: t A n): (forall p1 p2, p1 = p2 -> v1 [@ p1 ] = v2 [@ p2 ]) <-> v1 = v2. Proof. @@ -44,12 +46,35 @@ split. - intros; now f_equal. Qed. +Lemma nth_order_hd A: forall n (v : t A (S n)) (H : 0 < S n), + nth_order v H = hd v. +Proof. intros; now rewrite (eta v). Qed. + +Lemma nth_order_tl A: forall n k (v : t A (S n)) (H : k < n) (HS : S k < S n), + nth_order (tl v) H = nth_order v HS. +Proof. +induction n; intros. +- inversion H. +- rewrite (eta v). + unfold nth_order; simpl. + now rewrite (Fin.of_nat_ext H (Lt.lt_S_n _ _ HS)). +Qed. + Lemma nth_order_last A: forall n (v: t A (S n)) (H: n < S n), nth_order v H = last v. Proof. unfold nth_order; refine (@rectS _ _ _ _); now simpl. Qed. +Lemma nth_order_ext A: forall n k (v : t A n) (H1 H2 : k < n), + nth_order v H1 = nth_order v H2. +Proof. +intros; unfold nth_order. +now rewrite (Fin.of_nat_ext H1 H2). +Qed. + +(** ** Properties of [shiftin] and [shiftrepeat] *) + Lemma shiftin_nth A a n (v: t A n) k1 k2 (eq: k1 = k2): nth (shiftin a v) (Fin.L_R 1 k1) = nth v k2. Proof. @@ -82,11 +107,99 @@ Proof. refine (@rectS _ _ _ _); now simpl. Qed. +(** ** Properties of [replace] *) + +Lemma nth_order_replace_eq A: forall n k (v : t A n) a (H1 : k < n) (H2 : k < n), + nth_order (replace v (Fin.of_nat_lt H2) a) H1 = a. +Proof. +intros n k; revert n; induction k; intros; + (destruct n; [ inversion H1 | subst ]). +- now rewrite nth_order_hd, (eta v). +- rewrite <- (nth_order_tl _ _ _ _ (proj2 (Nat.succ_lt_mono _ _) H1)), (eta v). + apply IHk. +Qed. + +Lemma nth_order_replace_neq A: forall n k1 k2, k1 <> k2 -> + forall (v : t A n) a (H1 : k1 < n) (H2 : k2 < n), + nth_order (replace v (Fin.of_nat_lt H2) a) H1 = nth_order v H1. +Proof. +intros n k1; revert n; induction k1; intros; + (destruct n ; [ inversion H1 | subst ]). +- rewrite 2 nth_order_hd. + destruct k2; intuition. + now rewrite 2 (eta v). +- rewrite <- 2 (nth_order_tl _ _ _ _ (proj2 (Nat.succ_lt_mono _ _) H1)), (eta v). + destruct k2; auto. + apply IHk1. + intros Hk; apply H; now subst. +Qed. + +Lemma replace_id A: forall n p (v : t A n), + replace v p (nth v p) = v. +Proof. +induction p; intros; rewrite 2 (eta v); simpl; auto. +now rewrite IHp. +Qed. + +Lemma replace_replace_eq A: forall n p (v : t A n) a b, + replace (replace v p a) p b = replace v p b. +Proof. +intros. +induction p; rewrite 2 (eta v); simpl; auto. +now rewrite IHp. +Qed. + +Lemma replace_replace_neq A: forall n p1 p2 (v : t A n) a b, p1 <> p2 -> + replace (replace v p1 a) p2 b = replace (replace v p2 b) p1 a. +Proof. +apply (Fin.rect2 (fun n p1 p2 => forall v a b, + p1 <> p2 -> replace (replace v p1 a) p2 b = replace (replace v p2 b) p1 a)). +- intros n v a b Hneq. + now contradiction Hneq. +- intros n p2 v; revert n v p2. + refine (@rectS _ _ _ _); auto. +- intros n p1 v; revert n v p1. + refine (@rectS _ _ _ _); auto. +- intros n p1 p2 IH v; revert n v p1 p2 IH. + refine (@rectS _ _ _ _); simpl; do 6 intro; [ | do 3 intro ]; intro Hneq; + f_equal; apply IH; intros Heq; apply Hneq; now subst. +Qed. + +(** ** Properties of [const] *) + Lemma const_nth A (a: A) n (p: Fin.t n): (const a n)[@ p] = a. Proof. now induction p. Qed. +(** ** Properties of [map] *) + +Lemma map_id A: forall n (v : t A n), + map (fun x => x) v = v. +Proof. +induction v; simpl; [ | rewrite IHv ]; auto. +Qed. + +Lemma map_map A B C: forall (f:A->B) (g:B->C) n (v : t A n), + map g (map f v) = map (fun x => g (f x)) v. +Proof. +induction v; simpl; [ | rewrite IHv ]; auto. +Qed. + +Lemma map_ext_in A B: forall (f g:A->B) n (v : t A n), + (forall a, In a v -> f a = g a) -> map f v = map g v. +Proof. +induction v; simpl; auto. +intros; rewrite H by constructor; rewrite IHv; intuition. +apply H; now constructor. +Qed. + +Lemma map_ext A B: forall (f g:A->B), (forall a, f a = g a) -> + forall n (v : t A n), map f v = map g v. +Proof. +intros; apply map_ext_in; auto. +Qed. + Lemma nth_map {A B} (f: A -> B) {n} v (p1 p2: Fin.t n) (eq: p1 = p2): (map f v) [@ p1] = f (v [@ p2]). Proof. @@ -105,6 +218,8 @@ refine (@rect2 _ _ _ _ _); simpl. now simpl. Qed. +(** ** Properties of [fold_left] *) + Lemma fold_left_right_assoc_eq {A B} {f: A -> B -> A} (assoc: forall a b c, f (f a b) c = f (f a c) b) {n} (v: t B n): forall a, fold_left f a v = fold_right (fun x y => f y x) v a. @@ -118,6 +233,8 @@ assert (forall n h (v: t B n) a, fold_left f (f a h) v = f (fold_left f a v) h). + simpl. intros; now rewrite<- (IHv). Qed. +(** ** Properties of [to_list] *) + Lemma to_list_of_list_opp {A} (l: list A): to_list (of_list l) = l. Proof. induction l. @@ -125,6 +242,8 @@ induction l. - unfold to_list; simpl. now f_equal. Qed. +(** ** Properties of [take] *) + Lemma take_O : forall {A} {n} le (v:t A n), take 0 le v = []. Proof. reflexivity. @@ -153,10 +272,14 @@ Proof. - destruct v. inversion le. simpl. apply f_equal. apply IHp. Qed. +(** ** Properties of [uncons] and [splitat] *) + Lemma uncons_cons {A} : forall {n : nat} (a : A) (v : t A n), uncons (a::v) = (a,v). Proof. reflexivity. Qed. +(* [append] *) + Lemma append_comm_cons {A} : forall {n m : nat} (v : t A n) (w : t A m) (a : A), a :: (v ++ w) = (a :: v) ++ w. Proof. reflexivity. Qed. @@ -187,3 +310,80 @@ Proof with auto. f_equal... apply IHv... Qed. + +(** ** Properties of [Forall] and [Forall2] *) + +Lemma Forall_impl A: forall (P Q : A -> Prop), (forall a, P a -> Q a) -> + forall n (v : t A n), Forall P v -> Forall Q v. +Proof. +induction v; intros HP; constructor; inversion HP as [| ? ? ? ? ? Heq1 [Heq2 He]]; + apply (inj_pair2_eq_dec _ Nat.eq_dec) in He; subst; intuition. +Qed. + +Lemma Forall_forall A: forall P n (v : t A n), + Forall P v <-> forall a, In a v -> P a. +Proof. +intros P n v; split. +- intros HP a Hin. + revert HP; induction Hin; intros HP; + inversion HP as [| ? ? ? ? ? Heq1 [Heq2 He]]; subst; auto. + apply (inj_pair2_eq_dec _ Nat.eq_dec) in He; subst; auto. +- induction v; intros Hin; constructor. + + apply Hin; constructor. + + apply IHv; intros a Ha. + apply Hin; now constructor. +Qed. + +Lemma Forall_nth_order A: forall P n (v : t A n), + Forall P v <-> forall i (Hi : i < n), P (nth_order v Hi). +Proof. +split; induction n. +- intros HF i Hi; inversion Hi. +- intros HF i Hi. + rewrite (eta v). + rewrite (eta v) in HF. + inversion HF as [| ? ? ? ? ? Heq1 [Heq2 He]]; subst. + apply (inj_pair2_eq_dec _ Nat.eq_dec) in He ; subst. + destruct i. + + now rewrite nth_order_hd. + + rewrite <- (nth_order_tl _ _ _ _ (proj2 (Nat.succ_lt_mono _ _) Hi) Hi). + now apply IHn. +- intros HP; apply case0; constructor. +- intros HP. + rewrite (eta v) in HP. + rewrite (eta v); constructor. + + specialize HP with 0 (Nat.lt_0_succ n). + now rewrite nth_order_hd in HP. + + apply IHn; intros. + specialize HP with (S i) (proj1 (Nat.succ_lt_mono _ _) Hi). + now rewrite <- (nth_order_tl _ _ _ _ Hi) in HP. +Qed. + +Lemma Forall2_nth_order A: forall P n (v1 v2 : t A n), + Forall2 P v1 v2 + <-> forall i (Hi1 : i < n) (Hi2 : i < n), P (nth_order v1 Hi1) (nth_order v2 Hi2). +Proof. +split; induction n. +- intros HF i Hi1 Hi2; inversion Hi1. +- intros HF i Hi1 Hi2. + rewrite (eta v1), (eta v2). + rewrite (eta v1), (eta v2) in HF. + inversion HF as [| ? ? ? ? ? ? ? Heq [Heq1 He1] [Heq2 He2]]. + apply (inj_pair2_eq_dec _ Nat.eq_dec) in He1. + apply (inj_pair2_eq_dec _ Nat.eq_dec) in He2; subst. + destruct i. + + now rewrite nth_order_hd. + + rewrite <- (nth_order_tl _ _ _ _ (proj2 (Nat.succ_lt_mono _ _) Hi1) Hi1). + rewrite <- (nth_order_tl _ _ _ _ (proj2 (Nat.succ_lt_mono _ _) Hi2) Hi2). + now apply IHn. +- intros _; revert v1; apply case0; revert v2; apply case0; constructor. +- intros HP. + rewrite (eta v1), (eta v2) in HP. + rewrite (eta v1), (eta v2); constructor. + + specialize HP with 0 (Nat.lt_0_succ _) (Nat.lt_0_succ _). + now rewrite nth_order_hd in HP. + + apply IHn; intros. + specialize HP with (S i) (proj1 (Nat.succ_lt_mono _ _) Hi1) + (proj1 (Nat.succ_lt_mono _ _) Hi2). + now rewrite <- (nth_order_tl _ _ _ _ Hi1), <- (nth_order_tl _ _ _ _ Hi2) in HP. +Qed. diff --git a/theories/dune b/theories/dune new file mode 100644 index 0000000000..b9af76d699 --- /dev/null +++ b/theories/dune @@ -0,0 +1,38 @@ +(coq.theory + (name Coq) + (package coq) + (synopsis "Coq's Standard Library") + (flags -q) + ; (mode native) + (boot) + ; (per_file + ; (Init/*.v -> -boot)) + (libraries + coq.plugins.ltac + coq.plugins.tauto + + coq.plugins.cc + coq.plugins.firstorder + + coq.plugins.numeral_notation + coq.plugins.string_notation + coq.plugins.int63_syntax + coq.plugins.r_syntax + coq.plugins.float_syntax + + coq.plugins.btauto + coq.plugins.rtauto + + coq.plugins.setoid_ring + coq.plugins.nsatz + coq.plugins.omega + + coq.plugins.zify + coq.plugins.micromega + + coq.plugins.funind + + coq.plugins.ssreflect + coq.plugins.derive)) + +(include_subdirs qualified) diff --git a/theories/micromega/Lia.v b/theories/micromega/Lia.v index f3b70f61d2..3d955fec4f 100644 --- a/theories/micromega/Lia.v +++ b/theories/micromega/Lia.v @@ -21,7 +21,7 @@ Declare ML Module "micromega_plugin". Ltac zchecker := - intros __wit __varmap __ff ; + intros ?__wit ?__varmap ?__ff ; exact (ZTautoChecker_sound __ff __wit (@eq_refl bool true <: @eq bool (ZTautoChecker __ff __wit) true) (@find Z Z0 __varmap)). diff --git a/theories/micromega/Lqa.v b/theories/micromega/Lqa.v index 786c9275f0..8a4d59b1bd 100644 --- a/theories/micromega/Lqa.v +++ b/theories/micromega/Lqa.v @@ -23,7 +23,7 @@ Require Coq.micromega.Tauto. Declare ML Module "micromega_plugin". Ltac rchange := - intros __wit __varmap __ff ; + intros ?__wit ?__varmap ?__ff ; change (Tauto.eval_bf (Qeval_formula (@find Q 0%Q __varmap)) __ff) ; apply (QTautoChecker_sound __ff __wit). diff --git a/theories/micromega/Lra.v b/theories/micromega/Lra.v index 3ac4772ba4..22cef50e0d 100644 --- a/theories/micromega/Lra.v +++ b/theories/micromega/Lra.v @@ -23,7 +23,7 @@ Require Coq.micromega.Tauto. Declare ML Module "micromega_plugin". Ltac rchange := - intros __wit __varmap __ff ; + intros ?__wit ?__varmap ?__ff ; change (Tauto.eval_bf (Reval_formula (@find R 0%R __varmap)) __ff) ; apply (RTautoChecker_sound __ff __wit). diff --git a/theories/micromega/ZArith_hints.v b/theories/micromega/ZArith_hints.v new file mode 100644 index 0000000000..a6d3d92a99 --- /dev/null +++ b/theories/micromega/ZArith_hints.v @@ -0,0 +1,43 @@ +(************************************************************************) +(* * The Coq Proof Assistant / The Coq Development Team *) +(* v * Copyright INRIA, CNRS and contributors *) +(* <O___,, * (see version control and CREDITS file for authors & dates) *) +(* \VV/ **************************************************************) +(* // * This file is distributed under the terms of the *) +(* * GNU Lesser General Public License Version 2.1 *) +(* * (see LICENSE file for the text of the license) *) +(************************************************************************) +Require Import Lia. +Import ZArith_base. + +Hint Resolve Z.le_refl Z.add_comm Z.add_assoc Z.mul_comm Z.mul_assoc Z.add_0_l + Z.add_0_r Z.mul_1_l Z.add_opp_diag_l Z.add_opp_diag_r Z.mul_add_distr_r + Z.mul_add_distr_l: zarith. + +Require Export Zhints. + +Hint Extern 10 (_ = _ :>nat) => abstract lia: zarith. +Hint Extern 10 (_ <= _) => abstract lia: zarith. +Hint Extern 10 (_ < _) => abstract lia: zarith. +Hint Extern 10 (_ >= _) => abstract lia: zarith. +Hint Extern 10 (_ > _) => abstract lia: zarith. + +Hint Extern 10 (_ <> _ :>nat) => abstract lia: zarith. +Hint Extern 10 (~ _ <= _) => abstract lia: zarith. +Hint Extern 10 (~ _ < _) => abstract lia: zarith. +Hint Extern 10 (~ _ >= _) => abstract lia: zarith. +Hint Extern 10 (~ _ > _) => abstract lia: zarith. + +Hint Extern 10 (_ = _ :>Z) => abstract lia: zarith. +Hint Extern 10 (_ <= _)%Z => abstract lia: zarith. +Hint Extern 10 (_ < _)%Z => abstract lia: zarith. +Hint Extern 10 (_ >= _)%Z => abstract lia: zarith. +Hint Extern 10 (_ > _)%Z => abstract lia: zarith. + +Hint Extern 10 (_ <> _ :>Z) => abstract lia: zarith. +Hint Extern 10 (~ (_ <= _)%Z) => abstract lia: zarith. +Hint Extern 10 (~ (_ < _)%Z) => abstract lia: zarith. +Hint Extern 10 (~ (_ >= _)%Z) => abstract lia: zarith. +Hint Extern 10 (~ (_ > _)%Z) => abstract lia: zarith. + +Hint Extern 10 False => abstract lia: zarith. diff --git a/theories/omega/Omega.v b/theories/omega/Omega.v index 10a5aa47b3..5c52284621 100644 --- a/theories/omega/Omega.v +++ b/theories/omega/Omega.v @@ -19,38 +19,6 @@ Require Export ZArith_base. Require Export OmegaLemmas. Require Export PreOmega. -Require Import Lia. +Require Export ZArith_hints. Declare ML Module "omega_plugin". - -Hint Resolve Z.le_refl Z.add_comm Z.add_assoc Z.mul_comm Z.mul_assoc Z.add_0_l - Z.add_0_r Z.mul_1_l Z.add_opp_diag_l Z.add_opp_diag_r Z.mul_add_distr_r - Z.mul_add_distr_l: zarith. - -Require Export Zhints. - -Hint Extern 10 (_ = _ :>nat) => abstract lia: zarith. -Hint Extern 10 (_ <= _) => abstract lia: zarith. -Hint Extern 10 (_ < _) => abstract lia: zarith. -Hint Extern 10 (_ >= _) => abstract lia: zarith. -Hint Extern 10 (_ > _) => abstract lia: zarith. - -Hint Extern 10 (_ <> _ :>nat) => abstract lia: zarith. -Hint Extern 10 (~ _ <= _) => abstract lia: zarith. -Hint Extern 10 (~ _ < _) => abstract lia: zarith. -Hint Extern 10 (~ _ >= _) => abstract lia: zarith. -Hint Extern 10 (~ _ > _) => abstract lia: zarith. - -Hint Extern 10 (_ = _ :>Z) => abstract lia: zarith. -Hint Extern 10 (_ <= _)%Z => abstract lia: zarith. -Hint Extern 10 (_ < _)%Z => abstract lia: zarith. -Hint Extern 10 (_ >= _)%Z => abstract lia: zarith. -Hint Extern 10 (_ > _)%Z => abstract lia: zarith. - -Hint Extern 10 (_ <> _ :>Z) => abstract lia: zarith. -Hint Extern 10 (~ (_ <= _)%Z) => abstract lia: zarith. -Hint Extern 10 (~ (_ < _)%Z) => abstract lia: zarith. -Hint Extern 10 (~ (_ >= _)%Z) => abstract lia: zarith. -Hint Extern 10 (~ (_ > _)%Z) => abstract lia: zarith. - -Hint Extern 10 False => abstract lia: zarith. diff --git a/theories/setoid_ring/Field_tac.v b/theories/setoid_ring/Field_tac.v index 89a5ca6740..15b2618e47 100644 --- a/theories/setoid_ring/Field_tac.v +++ b/theories/setoid_ring/Field_tac.v @@ -215,7 +215,7 @@ Ltac fold_field_cond req := Ltac simpl_PCond FLD := let req := get_FldEq FLD in let lemma := get_CondLemma FLD in - try (apply lemma; intros lock lock_def; vm_compute; rewrite lock_def; clear lock_def lock); + try (apply lemma; intros ?lock ?lock_def; vm_compute; rewrite lock_def; clear lock_def lock); protect_fv "field_cond"; fold_field_cond req; try exact I. @@ -223,7 +223,7 @@ Ltac simpl_PCond FLD := Ltac simpl_PCond_BEURK FLD := let req := get_FldEq FLD in let lemma := get_CondLemma FLD in - (apply lemma; intros lock lock_def; vm_compute; rewrite lock_def; clear lock_def lock); + (apply lemma; intros ?lock ?lock_def; vm_compute; rewrite lock_def; clear lock_def lock); protect_fv "field_cond"; fold_field_cond req. diff --git a/theories/setoid_ring/Rings_Z.v b/theories/setoid_ring/Rings_Z.v index f489b00145..372bba7926 100644 --- a/theories/setoid_ring/Rings_Z.v +++ b/theories/setoid_ring/Rings_Z.v @@ -11,7 +11,6 @@ Require Export Cring. Require Export Integral_domain. Require Export Ncring_initial. -Require Export Omega. Instance Zcri: (Cring (Rr:=Zr)). red. exact Z.mul_comm. Defined. |