cmra_big_op.v 2.86 KB
 Robbert Krebbers committed Feb 13, 2016 1 ``````From algebra Require Export cmra. `````` Robbert Krebbers committed Feb 17, 2016 2 ``````From prelude Require Import gmap. `````` Robbert Krebbers committed Feb 01, 2016 3 4 5 6 7 `````` 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. `````` Robbert Krebbers committed Feb 17, 2016 8 ``````Definition big_opM `{Countable K} {A : cmraT} `{Empty A} (m : gmap K A) : A := `````` Robbert Krebbers committed Feb 01, 2016 9 10 11 12 13 `````` big_op (snd <\$> map_to_list m). Instance: Params (@big_opM) 5. (** * Properties about big ops *) Section big_op. `````` Ralf Jung committed Mar 08, 2016 14 ``````Context `{CMRAUnit A}. `````` Robbert Krebbers committed Feb 01, 2016 15 16 17 18 19 20 21 22 23 `````` (** * 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. `````` Robbert Krebbers committed Feb 17, 2016 24 25 `````` - by rewrite IH. - by rewrite !assoc (comm _ x). `````` Ralf Jung committed Feb 20, 2016 26 `````` - by trans (big_op xs2). `````` Robbert Krebbers committed Feb 01, 2016 27 28 29 30 31 ``````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 ``````Qed. Lemma big_op_contains xs ys : xs `contains` ys → big_op xs ≼ big_op ys. Proof. `````` Robbert Krebbers committed Feb 17, 2016 37 38 `````` intros [xs' ->]%contains_Permutation. rewrite big_op_app; apply cmra_included_l. `````` Robbert Krebbers committed Feb 01, 2016 39 40 41 42 43 ``````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. `````` Robbert Krebbers committed Feb 17, 2016 44 45 46 ``````Context `{Countable K}. Implicit Types m : gmap K A. Lemma big_opM_empty : big_opM (∅ : gmap K A) ≡ ∅. `````` Robbert Krebbers committed Feb 01, 2016 47 ``````Proof. unfold big_opM. by rewrite map_to_list_empty. Qed. `````` Robbert Krebbers committed Feb 17, 2016 48 ``````Lemma big_opM_insert m i x : `````` Robbert Krebbers committed Feb 01, 2016 49 50 `````` m !! i = None → big_opM (<[i:=x]> m) ≡ x ⋅ big_opM m. Proof. intros ?; by rewrite /big_opM map_to_list_insert. Qed. `````` Robbert Krebbers committed Feb 17, 2016 51 ``````Lemma big_opM_delete m i x : `````` Robbert Krebbers committed Feb 01, 2016 52 53 54 55 `````` 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. `````` Robbert Krebbers committed Feb 17, 2016 56 ``````Lemma big_opM_singleton i x : big_opM ({[i := x]} : gmap K A) ≡ x. `````` Robbert Krebbers committed Feb 01, 2016 57 58 ``````Proof. rewrite -insert_empty big_opM_insert /=; last auto using lookup_empty. `````` Robbert Krebbers committed Feb 11, 2016 59 `````` by rewrite big_opM_empty right_id. `````` Robbert Krebbers committed Feb 01, 2016 60 ``````Qed. `````` Robbert Krebbers committed Feb 17, 2016 61 ``````Global Instance big_opM_proper : Proper ((≡) ==> (≡)) (big_opM : gmap K A → _). `````` Robbert Krebbers committed Feb 01, 2016 62 63 64 65 66 67 68 69 70 71 ``````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 72 ``````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 73 74 75 76 77 ``````Proof. intros Hm ?; revert Hm; rewrite -(big_opM_delete _ i x) //. apply cmra_validN_op_l. Qed. End big_op.``````