diff options
author | Yann Herklotz <git@yannherklotz.com> | 2021-02-16 14:11:32 +0000 |
---|---|---|
committer | Yann Herklotz <git@yannherklotz.com> | 2021-02-16 14:11:32 +0000 |
commit | 6a395495bd35bb7d4d2cc7d3271c9b588d466594 (patch) | |
tree | 0fcc285046352b9f677454eac3224ce5a90ba48e /src/common/Maps.v | |
parent | 5f1e7aa8fbc4a0e04d0b137410c13f3d8da4d987 (diff) | |
parent | b5c79cb4913087a0e4b577b5dff616fc88ee938b (diff) | |
download | vericert-6a395495bd35bb7d4d2cc7d3271c9b588d466594.tar.gz vericert-6a395495bd35bb7d4d2cc7d3271c9b588d466594.zip |
Merge branch 'michalis' of https://github.com/mpardalos/vericert into michalis-merge
Diffstat (limited to 'src/common/Maps.v')
-rw-r--r-- | src/common/Maps.v | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/src/common/Maps.v b/src/common/Maps.v index f0f264d..2db5114 100644 --- a/src/common/Maps.v +++ b/src/common/Maps.v @@ -61,4 +61,31 @@ Definition traverse (A B : Type) (f : positive -> A -> res B) m := xtraverse f m Definition traverse1 (A B : Type) (f : A -> res B) := traverse (fun _ => f). +Definition filter (A: Type) (pred: PTree.elt -> A -> bool) (m: t A) : t A := + PTree.map (fun _ a => snd a) (PTree.filter1 (fun a => pred (fst a) (snd a)) (PTree.map (fun i x => (i, x)) m)). + +Theorem filter_spec: forall (A: Type) (pred: PTree.elt -> A -> bool) (m: PTree.t A) (i: PTree.elt) (x : A), + (filter pred m) ! i = + match m ! i with + | None => None + | Some x => if pred i x then Some x else None + end. +Proof. + intros. + unfold filter. + + rewrite gmap. + unfold option_map. + + rewrite gfilter1. + + rewrite gmap. + unfold option_map. + + destruct (m ! i). + - simpl. + destruct (pred i a); simpl; reflexivity. + - reflexivity. +Qed. + End PTree. |