nmap.v 1.97 KB
Newer Older
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's avatar
Robbert Krebbers committed
5 6 7 8 9
Require Import pmap.
Require Export prelude fin_maps.

Local Open Scope N_scope.

10
Record Nmap A := NMap { Nmap_0 : option A; Nmap_pos : Pmap A }.
Robbert Krebbers's avatar
Robbert Krebbers committed
11 12
Arguments Nmap_0 {_} _.
Arguments Nmap_pos {_} _.
13
Arguments NMap {_} _ _.
Robbert Krebbers's avatar
Robbert Krebbers committed
14

15
Instance Pmap_dec `{ x y : A, Decision (x = y)} :
16
   x y : Nmap A, Decision (x = y).
Robbert Krebbers's avatar
Robbert Krebbers committed
17
Proof. solve_decision. Defined.
18

19 20
Instance Nempty {A} : Empty (Nmap A) := NMap None .
Instance Nlookup {A} : Lookup N (Nmap A) A := λ i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
21 22 23 24
  match i with
  | N0 => Nmap_0 t
  | Npos p => Nmap_pos t !! p
  end.
25
Instance Npartial_alter {A} : PartialAlter N (Nmap A) A := λ f i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
26
  match i, t with
27 28
  | N0, NMap o t => NMap (f o) t
  | Npos p, NMap o t => NMap o (partial_alter f p t)
Robbert Krebbers's avatar
Robbert Krebbers committed
29
  end.
30
Instance Ndom {A} : Dom N (Nmap A) := λ C _ _ _ t,
Robbert Krebbers's avatar
Robbert Krebbers committed
31
  match t with
32
  | NMap o t => option_case (λ _, {[ 0 ]})  o  (Pdom_raw Npos (`t))
Robbert Krebbers's avatar
Robbert Krebbers committed
33
  end.
34
Instance Nmerge: Merge Nmap := λ A f t1 t2,
Robbert Krebbers's avatar
Robbert Krebbers committed
35
  match t1, t2 with
36
  | NMap o1 t1, NMap o2 t2 => NMap (f o1 o2) (merge f t1 t2)
Robbert Krebbers's avatar
Robbert Krebbers committed
37
  end.
38
Instance Nfmap: FMap Nmap := λ A B f t,
Robbert Krebbers's avatar
Robbert Krebbers committed
39
  match t with
40
  | NMap o t => NMap (fmap f o) (fmap f t)
Robbert Krebbers's avatar
Robbert Krebbers committed
41 42
  end.

43
Instance: FinMap N Nmap.
Robbert Krebbers's avatar
Robbert Krebbers committed
44 45
Proof.
  split.
46
  * intros ? [??] [??] H. f_equal.
47 48 49 50 51 52 53 54 55
    + apply (H 0).
    + apply finmap_eq. intros i. apply (H (Npos i)).
  * by intros ? [|?].
  * intros ? f [? t] [|i]; simpl.
    + done.
    + apply lookup_partial_alter.
  * intros ? f [? t] [|i] [|j]; simpl; try intuition congruence.
    intros. apply lookup_partial_alter_ne. congruence.
  * intros ??? [??] []; simpl. done. apply lookup_fmap.
56
  * intros ?? ??????? [o t] n; simpl.
57
    rewrite elem_of_union, Plookup_raw_dom.
58
    destruct o, n; esolve_elem_of (inv_is_Some; eauto).
59 60
  * intros ? f ? [o1 t1] [o2 t2] [|?]; simpl.
    + done.
61
    + apply (merge_spec f t1 t2).
Robbert Krebbers's avatar
Robbert Krebbers committed
62
Qed.