nmap.v 2.11 KB
 Robbert Krebbers committed Aug 29, 2012 1 2 3 4 ``````(* Copyright (c) 2012, Robbert Krebbers. *) (* This file is distributed under the terms of the BSD license. *) (** This files extends the implementation of finite over [positive] to finite maps whose keys range over Coq's data type of binary naturals [N]. *) `````` Robbert Krebbers committed Jun 11, 2012 5 6 7 8 9 10 11 12 13 14 ``````Require Import pmap. Require Export prelude fin_maps. Local Open Scope N_scope. Record Nmap A := { Nmap_0 : option A; Nmap_pos : Pmap A }. Arguments Nmap_0 {_} _. Arguments Nmap_pos {_} _. Arguments Build_Nmap {_} _ _. `````` Robbert Krebbers committed Aug 29, 2012 15 16 ``````Global Instance Pmap_dec `{∀ x y : A, Decision (x = y)} : ∀ x y : Nmap A, Decision (x = y). `````` Robbert Krebbers committed Jun 11, 2012 17 ``````Proof. solve_decision. Defined. `````` Robbert Krebbers committed Aug 29, 2012 18 `````` `````` Robbert Krebbers committed Jun 11, 2012 19 20 21 22 23 24 25 26 27 28 29 ``````Global Instance Nempty {A} : Empty (Nmap A) := Build_Nmap None ∅. Global Instance Nlookup: Lookup N Nmap := λ A i t, match i with | N0 => Nmap_0 t | Npos p => Nmap_pos t !! p end. Global Instance Npartial_alter: PartialAlter N Nmap := λ A f i t, match i, t with | N0, Build_Nmap o t => Build_Nmap (f o) t | Npos p, Build_Nmap o t => Build_Nmap o (partial_alter f p t) end. `````` 30 ``````Global Instance Ndom: Dom N Nmap := λ C _ _ _ _ t, `````` Robbert Krebbers committed Jun 11, 2012 31 `````` match t with `````` Robbert Krebbers committed Aug 21, 2012 32 `````` | Build_Nmap o t => option_case (λ _, {[ 0 ]}) ∅ o ∪ (Pdom_raw Npos (`t)) `````` Robbert Krebbers committed Jun 11, 2012 33 34 35 36 37 38 39 40 41 42 43 44 45 `````` end. Global Instance Nmerge: Merge Nmap := λ A f t1 t2, match t1, t2 with | Build_Nmap o1 t1, Build_Nmap o2 t2 => Build_Nmap (f o1 o2) (merge f t1 t2) end. Global Instance Nfmap: FMap Nmap := λ A B f t, match t with | Build_Nmap o t => Build_Nmap (fmap f o) (fmap f t) end. Global Instance: FinMap N Nmap. Proof. split. `````` Robbert Krebbers committed Aug 21, 2012 46 47 48 49 50 51 52 53 54 55 56 57 `````` * intros ? [??] [??] H. f_equal. + now apply (H 0). + apply finmap_eq. intros i. now apply (H (Npos i)). * now intros ? [|?]. * intros ? f [? t] [|i]. + easy. + now apply (lookup_partial_alter f t i). * intros ? f [? t] [|i] [|j]; try intuition congruence. intros. apply (lookup_partial_alter_ne f t i j). congruence. * intros ??? [??] []. easy. apply lookup_fmap. * intros ?? ???????? [o t] n; unfold dom, lookup, Ndom, Nlookup; simpl. rewrite elem_of_union, Plookup_raw_dom. `````` Robbert Krebbers committed Aug 29, 2012 58 `````` destruct o, n; esolve_elem_of (simplify_is_Some; eauto). `````` Robbert Krebbers committed Aug 21, 2012 59 60 61 `````` * intros ? f ? [o1 t1] [o2 t2] [|?]. + easy. + apply (merge_spec f t1 t2). `````` Robbert Krebbers committed Jun 11, 2012 62 ``Qed.``