nmap.v 3.12 KB
Newer Older
1
(* Copyright (c) 2012-2013, 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
Require Import pmap mapset.
Robbert Krebbers's avatar
Robbert Krebbers committed
6 7 8 9
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 16 17 18 19
Instance Nmap_eq_dec `{ x y : A, Decision (x = y)} (t1 t2 : Nmap A) :
  Decision (t1 = t2).
Proof.
 refine
  match t1, t2 with
20
  | NMap x t1, NMap y t2 => cast_if_and (decide (x = y)) (decide (t1 = t2))
21 22
  end; abstract congruence.
Defined.
23

24
Instance Nempty {A} : Empty (Nmap A) := NMap None .
Robbert Krebbers's avatar
Robbert Krebbers committed
25
Instance Nlookup {A} : Lookup N A (Nmap A) := λ i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
26 27 28 29
  match i with
  | N0 => Nmap_0 t
  | Npos p => Nmap_pos t !! p
  end.
Robbert Krebbers's avatar
Robbert Krebbers committed
30
Instance Npartial_alter {A} : PartialAlter N A (Nmap A) := λ f i t,
Robbert Krebbers's avatar
Robbert Krebbers committed
31
  match i, t with
32 33
  | 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
34
  end.
Robbert Krebbers's avatar
Robbert Krebbers committed
35
Instance Nto_list {A} : FinMapToList N A (Nmap A) := λ t,
Robbert Krebbers's avatar
Robbert Krebbers committed
36
  match t with
37
  | NMap o t => default [] o (λ x, [(0,x)]) ++ (fst_map Npos <$> map_to_list t)
Robbert Krebbers's avatar
Robbert Krebbers committed
38
  end.
39
Instance Nmerge: Merge Nmap := λ A B C f t1 t2,
Robbert Krebbers's avatar
Robbert Krebbers committed
40
  match t1, t2 with
41
  | NMap o1 t1, NMap o2 t2 => NMap (f o1 o2) (merge f t1 t2)
Robbert Krebbers's avatar
Robbert Krebbers committed
42
  end.
43
Instance Nfmap: FMap Nmap := λ A B f t,
44
  match t with NMap o t => NMap (fmap f o) (fmap f t) end.
Robbert Krebbers's avatar
Robbert Krebbers committed
45

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

82 83
(** * Finite sets *)
(** We construct sets of [N]s satisfying extensional equality. *)
84 85 86
Notation Nset := (mapset Nmap).
Instance Nmap_dom {A} : Dom (Nmap A) Nset := mapset_dom.
Instance: FinMapDom N Nmap Nset := mapset_dom_spec.