zmap.v 4.13 KB
Newer Older
1
(* Copyright (c) 2012-2019, Coq-std++ developers. *)
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 [Z]. *)
5 6
From stdpp Require Import pmap mapset.
From stdpp Require Export prelude fin_maps.
7
Set Default Proof Using "Type".
8 9
Local Open Scope Z_scope.

10
Record Zmap (A : Type) : Type :=
11
  ZMap { Zmap_0 : option A; Zmap_pos : Pmap A; Zmap_neg : Pmap A }.
12 13 14 15
Arguments Zmap_0 {_} _ : assert.
Arguments Zmap_pos {_} _ : assert.
Arguments Zmap_neg {_} _ : assert.
Arguments ZMap {_} _ _ _ : assert.
16

17
Instance Zmap_eq_dec `{EqDecision A} : EqDecision (Zmap A).
18
Proof.
19
 refine (λ t1 t2,
20 21 22
  match t1, t2 with
  | ZMap x t1 t1', ZMap y t2 t2' =>
     cast_if_and3 (decide (x = y)) (decide (t1 = t2)) (decide (t1' = t2'))
23
  end); abstract congruence.
24 25
Defined.
Instance Zempty {A} : Empty (Zmap A) := ZMap None  .
26
Instance Zlookup {A} : Lookup Z A (Zmap A) := λ i t,
27 28 29
  match i with
  | Z0 => Zmap_0 t | Zpos p => Zmap_pos t !! p | Zneg p => Zmap_neg t !! p
  end.
30
Instance Zpartial_alter {A} : PartialAlter Z A (Zmap A) := λ f i t,
31 32 33 34 35
  match i, t with
  | Z0, ZMap o t t' => ZMap (f o) t t'
  | Zpos p, ZMap o t t' => ZMap o (partial_alter f p t) t'
  | Zneg p, ZMap o t t' => ZMap o t (partial_alter f p t')
  end.
36
Instance Zto_list {A} : FinMapToList Z A (Zmap A) := λ t,
37
  match t with
38
  | ZMap o t t' => from_option (λ x, [(0,x)]) [] o ++
39 40 41 42 43 44 45
     (prod_map Zpos id <$> map_to_list t) ++
     (prod_map Zneg id <$> map_to_list t')
  end.
Instance Zomap: OMap Zmap := λ A B f t,
  match t with ZMap o t t' => ZMap (o = f) (omap f t) (omap f t') end.
Instance Zmerge: Merge Zmap := λ A B C f t1 t2,
  match t1, t2 with
46 47
  | ZMap o1 t1 t1', ZMap o2 t2 t2' =>
     ZMap (f o1 o2) (merge f t1 t2) (merge f t1' t2')
48 49 50 51 52 53 54
  end.
Instance Nfmap: FMap Zmap := λ A B f t,
  match t with ZMap o t t' => ZMap (f <$> o) (f <$> t) (f <$> t') end.

Instance: FinMap Z Zmap.
Proof.
  split.
55
  - intros ? [??] [??] H. f_equal.
56 57 58
    + apply (H 0).
    + apply map_eq. intros i. apply (H (Zpos i)).
    + apply map_eq. intros i. apply (H (Zneg i)).
59 60 61
  - by intros ? [].
  - intros ? f [] [|?|?]; simpl; [done| |]; apply lookup_partial_alter.
  - intros ? f [] [|?|?] [|?|?]; simpl; intuition congruence ||
62
      intros; apply lookup_partial_alter_ne; congruence.
63 64
  - intros ??? [??] []; simpl; [done| |]; apply lookup_fmap.
  - intros ? [o t t']; unfold map_to_list; simpl.
65
    assert (NoDup ((prod_map Z.pos id <$> map_to_list t) ++
66
      (prod_map Z.neg id <$> map_to_list t'))).
67
    { apply NoDup_app; split_and?.
68
      - apply (NoDup_fmap_2 _), NoDup_map_to_list.
69
      - intro. rewrite !elem_of_list_fmap. naive_solver.
70
      - apply (NoDup_fmap_2 _), NoDup_map_to_list. }
71 72
    destruct o; simpl; auto. constructor; auto.
    rewrite elem_of_app, !elem_of_list_fmap. naive_solver.
73
  - intros ? t i x. unfold map_to_list. split.
74
    + destruct t as [[y|] t t']; simpl.
75
      * rewrite elem_of_cons, elem_of_app, !elem_of_list_fmap.
76
        intros [?|[[[??][??]]|[[??][??]]]]; simplify_eq/=; [done| |];
77
          by apply elem_of_map_to_list.
78
      * rewrite elem_of_app, !elem_of_list_fmap. intros [[[??][??]]|[[??][??]]];
79
          simplify_eq/=; by apply elem_of_map_to_list.
80
    + destruct t as [[y|] t t']; simpl.
81
      * rewrite elem_of_cons, elem_of_app, !elem_of_list_fmap.
82 83 84
        destruct i as [|i|i]; simpl; [intuition congruence| |].
        { right; left. exists (i, x). by rewrite elem_of_map_to_list. }
        right; right. exists (i, x). by rewrite elem_of_map_to_list.
85
      * rewrite elem_of_app, !elem_of_list_fmap.
86 87 88
        destruct i as [|i|i]; simpl; [done| |].
        { left; exists (i, x). by rewrite elem_of_map_to_list. }
        right; exists (i, x). by rewrite elem_of_map_to_list.
89 90
  - intros ?? f [??] [|?|?]; simpl; [done| |]; apply (lookup_omap f).
  - intros ??? f ? [??] [??] [|?|?]; simpl; [done| |]; apply (lookup_merge f).
91 92 93 94
Qed.

(** * Finite sets *)
(** We construct sets of [Z]s satisfying extensional equality. *)
95
Notation Zset := (mapset Zmap).
96
Instance Zmap_dom {A} : Dom (Zmap A) Zset := mapset_dom.
97
Instance: FinMapDom Z Zmap Zset := mapset_dom_spec.