cmra_big_op.v 2.97 KB
 Robbert Krebbers committed Feb 04, 2016 1 ``````Require Export algebra.cmra. `````` Robbert Krebbers committed Feb 01, 2016 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ``````Require Import prelude.fin_maps. Fixpoint big_op {A : cmraT} `{Empty A} (xs : list A) : A := match xs with [] => ∅ | x :: xs => x ⋅ big_op xs end. Arguments big_op _ _ !_ /. Instance: Params (@big_op) 2. Definition big_opM {A : cmraT} `{FinMapToList K A M, Empty A} (m : M) : A := big_op (snd <\$> map_to_list m). Instance: Params (@big_opM) 5. (** * Properties about big ops *) Section big_op. Context `{CMRAIdentity A}. (** * Big ops *) Lemma big_op_nil : big_op (@nil A) = ∅. Proof. done. Qed. Lemma big_op_cons x xs : big_op (x :: xs) = x ⋅ big_op xs. Proof. done. Qed. Global Instance big_op_permutation : Proper ((≡ₚ) ==> (≡)) big_op. Proof. induction 1 as [|x xs1 xs2 ? IH|x y xs|xs1 xs2 xs3]; simpl; auto. * by rewrite IH. `````` Robbert Krebbers committed Feb 11, 2016 25 `````` * by rewrite !assoc (comm _ x). `````` Robbert Krebbers committed Feb 01, 2016 26 27 28 29 30 31 `````` * by transitivity (big_op xs2). Qed. Global Instance big_op_proper : Proper ((≡) ==> (≡)) big_op. Proof. by induction 1; simpl; repeat apply (_ : Proper (_ ==> _ ==> _) op). Qed. Lemma big_op_app xs ys : big_op (xs ++ ys) ≡ big_op xs ⋅ big_op ys. Proof. `````` Robbert Krebbers committed Feb 11, 2016 32 33 `````` induction xs as [|x xs IH]; simpl; first by rewrite ?left_id. by rewrite IH assoc. `````` Robbert Krebbers committed Feb 01, 2016 34 35 36 37 38 ``````Qed. Lemma big_op_contains xs ys : xs `contains` ys → big_op xs ≼ big_op ys. Proof. induction 1 as [|x xs ys|x y xs|x xs ys|xs ys zs]; rewrite //=. * by apply cmra_preserving_l. `````` Robbert Krebbers committed Feb 11, 2016 39 `````` * by rewrite !assoc (comm _ y). `````` Robbert Krebbers committed Feb 01, 2016 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 `````` * by transitivity (big_op ys); last apply cmra_included_r. * by transitivity (big_op ys). Qed. Lemma big_op_delete xs i x : xs !! i = Some x → x ⋅ big_op (delete i xs) ≡ big_op xs. Proof. by intros; rewrite {2}(delete_Permutation xs i x). Qed. Context `{FinMap K M}. Lemma big_opM_empty : big_opM (∅ : M A) ≡ ∅. Proof. unfold big_opM. by rewrite map_to_list_empty. Qed. Lemma big_opM_insert (m : M A) i x : m !! i = None → big_opM (<[i:=x]> m) ≡ x ⋅ big_opM m. Proof. intros ?; by rewrite /big_opM map_to_list_insert. Qed. Lemma big_opM_delete (m : M A) i x : m !! i = Some x → x ⋅ big_opM (delete i m) ≡ big_opM m. Proof. intros. by rewrite -{2}(insert_delete m i x) // big_opM_insert ?lookup_delete. Qed. Lemma big_opM_singleton i x : big_opM ({[i ↦ x]} : M A) ≡ x. Proof. rewrite -insert_empty big_opM_insert /=; last auto using lookup_empty. `````` Robbert Krebbers committed Feb 11, 2016 61 `````` by rewrite big_opM_empty right_id. `````` Robbert Krebbers committed Feb 01, 2016 62 63 64 65 66 67 68 69 70 71 72 73 ``````Qed. Global Instance big_opM_proper : Proper ((≡) ==> (≡)) (big_opM : M A → _). Proof. intros m1; induction m1 as [|i x m1 ? IH] using map_ind. { by intros m2; rewrite (symmetry_iff (≡)) map_equiv_empty; intros ->. } intros m2 Hm2; rewrite big_opM_insert //. rewrite (IH (delete i m2)); last by rewrite -Hm2 delete_insert. destruct (map_equiv_lookup (<[i:=x]> m1) m2 i x) as (y&?&Hxy); auto using lookup_insert. rewrite Hxy -big_opM_insert; last auto using lookup_delete. by rewrite insert_delete. Qed. `````` Robbert Krebbers committed Feb 11, 2016 74 ``````Lemma big_opM_lookup_valid n m i x : ✓{n} big_opM m → m !! i = Some x → ✓{n} x. `````` Robbert Krebbers committed Feb 01, 2016 75 76 77 78 79 ``````Proof. intros Hm ?; revert Hm; rewrite -(big_opM_delete _ i x) //. apply cmra_validN_op_l. Qed. End big_op.``````