nmap.v 3.81 KB
Newer Older
Robbert Krebbers's avatar
Robbert Krebbers committed
1
(* Copyright (c) 2012-2015, Robbert Krebbers. *)
2 3 4
(* 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]. *)
5 6
From stdpp Require Import pmap mapset.
From stdpp Require Export prelude fin_maps.
Robbert Krebbers's avatar
Robbert Krebbers committed
7 8 9

Local Open Scope N_scope.

Robbert Krebbers's avatar
Robbert Krebbers committed
10
Record Nmap (A : Type) : Type := 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 Nmap_eq_dec `{EqDecision A} : EqDecision (Nmap A).
16
Proof.
17
 refine (λ t1 t2,
18
  match t1, t2 with
19
  | NMap x t1, NMap y t2 => cast_if_and (decide (x = y)) (decide (t1 = t2))
20
  end); abstract congruence.
21
Defined.
22
Instance Nempty {A} : Empty (Nmap A) := NMap None .
23
Global Opaque Nempty.
24
Instance Nlookup {A} : Lookup N A (Nmap A) := λ i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
25 26 27 28
  match i with
  | N0 => Nmap_0 t
  | Npos p => Nmap_pos t !! p
  end.
29
Instance Npartial_alter {A} : PartialAlter N A (Nmap A) := λ f i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
30
  match i, t with
31 32
  | 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
33
  end.
34
Instance Nto_list {A} : FinMapToList N A (Nmap A) := λ t,
Robbert Krebbers's avatar
Robbert Krebbers committed
35
  match t with
36 37
  | NMap o t =>
     default [] o (λ x, [(0,x)]) ++ (prod_map Npos id <$> map_to_list t)
Robbert Krebbers's avatar
Robbert Krebbers committed
38
  end.
39 40
Instance Nomap: OMap Nmap := λ A B f t,
  match t with NMap o t => NMap (o = f) (omap f t) end.
41
Instance Nmerge: Merge Nmap := λ A B C f t1 t2,
Robbert Krebbers's avatar
Robbert Krebbers committed
42
  match t1, t2 with
43
  | NMap o1 t1, NMap o2 t2 => NMap (f o1 o2) (merge f t1 t2)
Robbert Krebbers's avatar
Robbert Krebbers committed
44
  end.
45
Instance Nfmap: FMap Nmap := λ A B f t,
46
  match t with NMap o t => NMap (f <$> o) (f <$> t) end.
Robbert Krebbers's avatar
Robbert Krebbers committed
47

48
Instance: FinMap N Nmap.
Robbert Krebbers's avatar
Robbert Krebbers committed
49 50
Proof.
  split.
51
  - intros ? [??] [??] H. f_equal; [apply (H 0)|].
52
    apply map_eq. intros i. apply (H (Npos i)).
53 54 55
  - by intros ? [|?].
  - intros ? f [? t] [|i]; simpl; [done |]. apply lookup_partial_alter.
  - intros ? f [? t] [|i] [|j]; simpl; try intuition congruence.
56
    intros. apply lookup_partial_alter_ne. congruence.
57 58
  - intros ??? [??] []; simpl. done. apply lookup_fmap.
  - intros ? [[x|] t]; unfold map_to_list; simpl.
Robbert Krebbers's avatar
Robbert Krebbers committed
59
    + constructor.
60 61
      * rewrite elem_of_list_fmap. by intros [[??] [??]].
      * by apply (NoDup_fmap _), NoDup_map_to_list.
62
    + apply (NoDup_fmap _), NoDup_map_to_list.
63
  - intros ? t i x. unfold map_to_list. split.
Robbert Krebbers's avatar
Robbert Krebbers committed
64
    + destruct t as [[y|] t]; simpl.
65
      * rewrite elem_of_cons, elem_of_list_fmap.
66
        intros [? | [[??] [??]]]; simplify_eq/=; [done |].
67
        by apply elem_of_map_to_list.
68
      * rewrite elem_of_list_fmap; intros [[??] [??]]; simplify_eq/=.
69
        by apply elem_of_map_to_list.
Robbert Krebbers's avatar
Robbert Krebbers committed
70
    + destruct t as [[y|] t]; simpl.
71
      * rewrite elem_of_cons, elem_of_list_fmap.
Robbert Krebbers's avatar
Robbert Krebbers committed
72
        destruct i as [|i]; simpl; [intuition congruence |].
73
        intros. right. exists (i, x). by rewrite elem_of_map_to_list.
74
      * rewrite elem_of_list_fmap.
Robbert Krebbers's avatar
Robbert Krebbers committed
75
        destruct i as [|i]; simpl; [done |].
76
        intros. exists (i, x). by rewrite elem_of_map_to_list.
77 78
  - intros ?? f [??] [|?]; simpl; [done|]; apply (lookup_omap f).
  - intros ??? f ? [??] [??] [|?]; simpl; [done|]; apply (lookup_merge f).
Robbert Krebbers's avatar
Robbert Krebbers committed
79
Qed.
80

81 82
(** * Finite sets *)
(** We construct sets of [N]s satisfying extensional equality. *)
Robbert Krebbers's avatar
Robbert Krebbers committed
83
Notation Nset := (mapset Nmap).
84
Instance Nmap_dom {A} : Dom (Nmap A) Nset := mapset_dom.
85
Instance: FinMapDom N Nmap Nset := mapset_dom_spec.
86 87 88 89 90 91 92 93 94 95 96 97

(** * Fresh numbers *)
Definition Nfresh {A} (m : Nmap A) : N :=
  match m with NMap None _ => 0 | NMap _ m => Npos (Pfresh m) end.
Lemma Nfresh_fresh {A} (m : Nmap A) : m !! Nfresh m = None.
Proof. destruct m as [[]]. apply Pfresh_fresh. done. Qed. 

Instance Nset_fresh : Fresh N Nset := λ X,
  let (m) := X in Nfresh m.
Instance Nset_fresh_spec : FreshSpec N Nset.
Proof.
  split.
98 99 100
  - apply _.
  - intros X Y; rewrite <-elem_of_equiv_L. by intros ->.
  - unfold elem_of, mapset_elem_of, fresh; intros [m]; simpl.
101 102
    by rewrite Nfresh_fresh.
Qed.