collections.v 27.9 KB
Newer Older
Robbert Krebbers's avatar
Robbert Krebbers committed
1
2
3
4
5
(* Copyright (c) 2012-2015, Robbert Krebbers. *)
(* This file is distributed under the terms of the BSD license. *)
(** This file collects definitions and theorems on collections. Most
importantly, it implements some tactics to automatically solve goals involving
collections. *)
6
From prelude Require Export base tactics orders.
Robbert Krebbers's avatar
Robbert Krebbers committed
7
8
9
10
11
12
13

Instance collection_subseteq `{ElemOf A C} : SubsetEq C := λ X Y,
   x, x  X  x  Y.

(** * Basic theorems *)
Section simple_collection.
  Context `{SimpleCollection A C}.
14
15
  Implicit Types x y : A.
  Implicit Types X Y : C.
Robbert Krebbers's avatar
Robbert Krebbers committed
16
17
18
19
20
21
22
23
24
25
26

  Lemma elem_of_empty x : x    False.
  Proof. split. apply not_elem_of_empty. done. Qed.
  Lemma elem_of_union_l x X Y : x  X  x  X  Y.
  Proof. intros. apply elem_of_union. auto. Qed.
  Lemma elem_of_union_r x X Y : x  Y  x  X  Y.
  Proof. intros. apply elem_of_union. auto. Qed.
  Global Instance: EmptySpec C.
  Proof. firstorder auto. Qed.
  Global Instance: JoinSemiLattice C.
  Proof. firstorder auto. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
27
28
  Global Instance: AntiSymm () (@collection_subseteq A C _).
  Proof. done. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
  Lemma elem_of_subseteq X Y : X  Y   x, x  X  x  Y.
  Proof. done. Qed.
  Lemma elem_of_equiv X Y : X  Y   x, x  X  x  Y.
  Proof. firstorder. Qed.
  Lemma elem_of_equiv_alt X Y :
    X  Y  ( x, x  X  x  Y)  ( x, x  Y  x  X).
  Proof. firstorder. Qed.
  Lemma elem_of_equiv_empty X : X     x, x  X.
  Proof. firstorder. Qed.
  Lemma collection_positive_l X Y : X  Y    X  .
  Proof.
    rewrite !elem_of_equiv_empty. setoid_rewrite elem_of_union. naive_solver.
  Qed.
  Lemma collection_positive_l_alt X Y : X    X  Y  .
  Proof. eauto using collection_positive_l. Qed.
  Lemma elem_of_singleton_1 x y : x  {[y]}  x = y.
  Proof. by rewrite elem_of_singleton. Qed.
  Lemma elem_of_singleton_2 x y : x = y  x  {[y]}.
  Proof. by rewrite elem_of_singleton. Qed.
  Lemma elem_of_subseteq_singleton x X : x  X  {[ x ]}  X.
  Proof.
    split.
51
52
    - intros ??. rewrite elem_of_singleton. by intros ->.
    - intros Ex. by apply (Ex x), elem_of_singleton.
Robbert Krebbers's avatar
Robbert Krebbers committed
53
  Qed.
54
  Global Instance singleton_proper : Proper ((=) ==> ()) (singleton (B:=C)).
Robbert Krebbers's avatar
Robbert Krebbers committed
55
  Proof. by repeat intro; subst. Qed.
56
57
  Global Instance elem_of_proper :
    Proper ((=) ==> () ==> iff) (() : A  C  Prop) | 5.
Robbert Krebbers's avatar
Robbert Krebbers committed
58
59
60
61
  Proof. intros ???; subst. firstorder. Qed.
  Lemma elem_of_union_list Xs x : x   Xs   X, X  Xs  x  X.
  Proof.
    split.
62
    - induction Xs; simpl; intros HXs; [by apply elem_of_empty in HXs|].
Robbert Krebbers's avatar
Robbert Krebbers committed
63
      setoid_rewrite elem_of_cons. apply elem_of_union in HXs. naive_solver.
64
    - intros [X []]. induction 1; simpl; [by apply elem_of_union_l |].
Robbert Krebbers's avatar
Robbert Krebbers committed
65
66
      intros. apply elem_of_union_r; auto.
  Qed.
67
  Lemma non_empty_singleton x : ({[ x ]} : C)  .
Robbert Krebbers's avatar
Robbert Krebbers committed
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
  Proof. intros [E _]. by apply (elem_of_empty x), E, elem_of_singleton. Qed.
  Lemma not_elem_of_singleton x y : x  {[ y ]}  x  y.
  Proof. by rewrite elem_of_singleton. Qed.
  Lemma not_elem_of_union x X Y : x  X  Y  x  X  x  Y.
  Proof. rewrite elem_of_union. tauto. Qed.

  Section leibniz.
    Context `{!LeibnizEquiv C}.
    Lemma elem_of_equiv_L X Y : X = Y   x, x  X  x  Y.
    Proof. unfold_leibniz. apply elem_of_equiv. Qed.
    Lemma elem_of_equiv_alt_L X Y :
      X = Y  ( x, x  X  x  Y)  ( x, x  Y  x  X).
    Proof. unfold_leibniz. apply elem_of_equiv_alt. Qed.
    Lemma elem_of_equiv_empty_L X : X =    x, x  X.
    Proof. unfold_leibniz. apply elem_of_equiv_empty. Qed.
    Lemma collection_positive_l_L X Y : X  Y =   X = .
    Proof. unfold_leibniz. apply collection_positive_l. Qed.
    Lemma collection_positive_l_alt_L X Y : X    X  Y  .
    Proof. unfold_leibniz. apply collection_positive_l_alt. Qed.
    Lemma non_empty_singleton_L x : {[ x ]}  .
    Proof. unfold_leibniz. apply non_empty_singleton. Qed.
  End leibniz.

  Section dec.
    Context `{ X Y : C, Decision (X  Y)}.
    Global Instance elem_of_dec_slow (x : A) (X : C) : Decision (x  X) | 100.
    Proof.
      refine (cast_if (decide_rel () {[ x ]} X));
        by rewrite elem_of_subseteq_singleton.
    Defined.
  End dec.
End simple_collection.

Definition of_option `{Singleton A C, Empty C} (x : option A) : C :=
  match x with None =>  | Some a => {[ a ]} end.
Fixpoint of_list `{Singleton A C, Empty C, Union C} (l : list A) : C :=
  match l with [] =>  | x :: l => {[ x ]}  of_list l end.

Section of_option_list.
  Context `{SimpleCollection A C}.
  Lemma elem_of_of_option (x : A) o : x  of_option o  o = Some x.
  Proof.
    destruct o; simpl;
      rewrite ?elem_of_empty, ?elem_of_singleton; naive_solver.
  Qed.
  Lemma elem_of_of_list (x : A) l : x  of_list l  x  l.
  Proof.
    split.
116
    - induction l; simpl; [by rewrite elem_of_empty|].
Robbert Krebbers's avatar
Robbert Krebbers committed
117
      rewrite elem_of_union,elem_of_singleton; intros [->|?]; constructor; auto.
118
    - induction 1; simpl; rewrite elem_of_union, elem_of_singleton; auto.
Robbert Krebbers's avatar
Robbert Krebbers committed
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
  Qed.
End of_option_list.

Global Instance collection_guard `{CollectionMonad M} : MGuard M :=
  λ P dec A x, match dec with left H => x H | _ =>  end.

Section collection_monad_base.
  Context `{CollectionMonad M}.
  Lemma elem_of_guard `{Decision P} {A} (x : A) (X : M A) :
    x  guard P; X  P  x  X.
  Proof.
    unfold mguard, collection_guard; simpl; case_match;
      rewrite ?elem_of_empty; naive_solver.
  Qed.
  Lemma elem_of_guard_2 `{Decision P} {A} (x : A) (X : M A) :
    P  x  X  x  guard P; X.
  Proof. by rewrite elem_of_guard. Qed.
  Lemma guard_empty `{Decision P} {A} (X : M A) : guard P; X    ¬P  X  .
  Proof.
    rewrite !elem_of_equiv_empty; setoid_rewrite elem_of_guard.
    destruct (decide P); naive_solver.
  Qed.
  Lemma bind_empty {A B} (f : A  M B) X :
    X = f    X     x, x  X  f x  .
  Proof.
    setoid_rewrite elem_of_equiv_empty; setoid_rewrite elem_of_bind.
    naive_solver.
  Qed.
End collection_monad_base.

(** * Tactics *)
(** Given a hypothesis [H : _ ∈ _], the tactic [destruct_elem_of H] will
recursively split [H] for [(∪)], [(∩)], [(∖)], [map], [∅], [{[_]}]. *)
Tactic Notation "decompose_elem_of" hyp(H) :=
  let rec go H :=
  lazymatch type of H with
  | _   => apply elem_of_empty in H; destruct H
  | ?x  {[ ?y ]} =>
    apply elem_of_singleton in H; try first [subst y | subst x]
  | ?x  {[ ?y ]} =>
    apply not_elem_of_singleton in H
  | _  _  _ =>
    apply elem_of_union in H; destruct H as [H|H]; [go H|go H]
  | _  _  _ =>
    let H1 := fresh H in let H2 := fresh H in apply not_elem_of_union in H;
    destruct H as [H1 H2]; go H1; go H2
  | _  _  _ =>
    let H1 := fresh H in let H2 := fresh H in apply elem_of_intersection in H;
    destruct H as [H1 H2]; go H1; go H2
  | _  _  _ =>
    let H1 := fresh H in let H2 := fresh H in apply elem_of_difference in H;
    destruct H as [H1 H2]; go H1; go H2
  | ?x  _ <$> _ =>
    apply elem_of_fmap in H; destruct H as [? [? H]]; try (subst x); go H
  | _  _ = _ =>
    let H1 := fresh H in let H2 := fresh H in apply elem_of_bind in H;
    destruct H as [? [H1 H2]]; go H1; go H2
  | ?x  mret ?y =>
    apply elem_of_ret in H; try first [subst y | subst x]
  | _  mjoin _ = _ =>
    let H1 := fresh H in let H2 := fresh H in apply elem_of_join in H;
    destruct H as [? [H1 H2]]; go H1; go H2
  | _  guard _; _ =>
    let H1 := fresh H in let H2 := fresh H in apply elem_of_guard in H;
    destruct H as [H1 H2]; go H2
  | _  of_option _ => apply elem_of_of_option in H
  | _  of_list _ => apply elem_of_of_list in H
  | _ => idtac
  end in go H.
Tactic Notation "decompose_elem_of" :=
  repeat_on_hyps (fun H => decompose_elem_of H).

Ltac decompose_empty := repeat
  match goal with
  | H :    |- _ => clear H
  | H :  =  |- _ => clear H
  | H :   _ |- _ => symmetry in H
  | H :  = _ |- _ => symmetry in H
  | H : _  _   |- _ => apply empty_union in H; destruct H
  | H : _  _   |- _ => apply non_empty_union in H; destruct H
  | H : {[ _ ]}   |- _ => destruct (non_empty_singleton _ H)
  | H : _  _ =  |- _ => apply empty_union_L in H; destruct H
  | H : _  _   |- _ => apply non_empty_union_L in H; destruct H
  | H : {[ _ ]} =  |- _ => destruct (non_empty_singleton_L _ H)
  | H : guard _ ; _   |- _ => apply guard_empty in H; destruct H
  end.

(** The first pass of our collection tactic consists of eliminating all
occurrences of [(∪)], [(∩)], [(∖)], [(<$>)], [∅], [{[_]}], [(≡)], and [(⊆)],
by rewriting these into logically equivalent propositions. For example we
rewrite [A → x ∈ X ∪ ∅] into [A → x ∈ X ∨ False]. *)
210
Ltac set_unfold :=
Robbert Krebbers's avatar
Robbert Krebbers committed
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
  repeat_on_hyps (fun H =>
    repeat match type of H with
    | context [ _  _ ] => setoid_rewrite elem_of_subseteq in H
    | context [ _  _ ] => setoid_rewrite subset_spec in H
    | context [ _   ] => setoid_rewrite elem_of_equiv_empty in H
    | context [ _  _ ] => setoid_rewrite elem_of_equiv_alt in H
    | context [ _ =  ] => setoid_rewrite elem_of_equiv_empty_L in H
    | context [ _ = _ ] => setoid_rewrite elem_of_equiv_alt_L in H
    | context [ _   ] => setoid_rewrite elem_of_empty in H
    | context [ _  {[ _ ]} ] => setoid_rewrite elem_of_singleton in H
    | context [ _  _  _ ] => setoid_rewrite elem_of_union in H
    | context [ _  _  _ ] => setoid_rewrite elem_of_intersection in H
    | context [ _  _  _ ] => setoid_rewrite elem_of_difference in H
    | context [ _  _ <$> _ ] => setoid_rewrite elem_of_fmap in H
    | context [ _  mret _ ] => setoid_rewrite elem_of_ret in H
    | context [ _  _ = _ ] => setoid_rewrite elem_of_bind in H
    | context [ _  mjoin _ ] => setoid_rewrite elem_of_join in H
    | context [ _  guard _; _ ] => setoid_rewrite elem_of_guard in H
    | context [ _  of_option _ ] => setoid_rewrite elem_of_of_option in H
    | context [ _  of_list _ ] => setoid_rewrite elem_of_of_list in H
    end);
  repeat match goal with
  | |- context [ _  _ ] => setoid_rewrite elem_of_subseteq
  | |- context [ _  _ ] => setoid_rewrite subset_spec
  | |- context [ _   ] => setoid_rewrite elem_of_equiv_empty
  | |- context [ _  _ ] => setoid_rewrite elem_of_equiv_alt
  | |- context [ _ =  ] => setoid_rewrite elem_of_equiv_empty_L
  | |- context [ _ = _ ] => setoid_rewrite elem_of_equiv_alt_L
  | |- context [ _   ] => setoid_rewrite elem_of_empty
  | |- context [ _  {[ _ ]} ] => setoid_rewrite elem_of_singleton
  | |- context [ _  _  _ ] => setoid_rewrite elem_of_union
  | |- context [ _  _  _ ] => setoid_rewrite elem_of_intersection
  | |- context [ _  _  _ ] => setoid_rewrite elem_of_difference
  | |- context [ _  _ <$> _ ] => setoid_rewrite elem_of_fmap
  | |- context [ _  mret _ ] => setoid_rewrite elem_of_ret
  | |- context [ _  _ = _ ] => setoid_rewrite elem_of_bind
  | |- context [ _  mjoin _ ] => setoid_rewrite elem_of_join
  | |- context [ _  guard _; _ ] => setoid_rewrite elem_of_guard
  | |- context [ _  of_option _ ] => setoid_rewrite elem_of_of_option
  | |- context [ _  of_list _ ] => setoid_rewrite elem_of_of_list
  end.

253
(** Since [firstorder] fails or loops on very small goals generated by
254
[set_solver] already. We use the [naive_solver] tactic as a substitute.
255
This tactic either fails or proves the goal. *)
256
Tactic Notation "set_solver" "by" tactic3(tac) :=
Robbert Krebbers's avatar
Robbert Krebbers committed
257
258
  setoid_subst;
  decompose_empty;
259
  set_unfold;
Robbert Krebbers's avatar
Robbert Krebbers committed
260
  naive_solver tac.
261
262
263
264
265
Tactic Notation "set_solver" "-" hyp_list(Hs) "by" tactic3(tac) :=
  clear Hs; set_solver by tac.
Tactic Notation "set_solver" "+" hyp_list(Hs) "by" tactic3(tac) :=
  clear -Hs; set_solver by tac.
Tactic Notation "set_solver" := set_solver by idtac.
266
Tactic Notation "set_solver" "-" hyp_list(Hs) := clear Hs; set_solver.
267
Tactic Notation "set_solver" "+" hyp_list(Hs) := clear -Hs; set_solver.
268

Robbert Krebbers's avatar
Robbert Krebbers committed
269
270
271
(** * More theorems *)
Section collection.
  Context `{Collection A C}.
272
  Implicit Types X Y : C.
Robbert Krebbers's avatar
Robbert Krebbers committed
273
274

  Global Instance: Lattice C.
275
  Proof. split. apply _. firstorder auto. set_solver. Qed.
276
277
  Global Instance difference_proper :
     Proper (() ==> () ==> ()) (@difference C _).
Robbert Krebbers's avatar
Robbert Krebbers committed
278
279
280
281
  Proof.
    intros X1 X2 HX Y1 Y2 HY; apply elem_of_equiv; intros x.
    by rewrite !elem_of_difference, HX, HY.
  Qed.
282
  Lemma non_empty_inhabited x X : x  X  X  .
283
  Proof. set_solver. Qed.
284
  Lemma intersection_singletons x : ({[x]} : C)  {[x]}  {[x]}.
285
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
286
  Lemma difference_twice X Y : (X  Y)  Y  X  Y.
287
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
288
  Lemma subseteq_empty_difference X Y : X  Y  X  Y  .
289
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
290
  Lemma difference_diag X : X  X  .
291
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
292
  Lemma difference_union_distr_l X Y Z : (X  Y)  Z  X  Z  Y  Z.
293
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
294
  Lemma difference_union_distr_r X Y Z : Z  (X  Y)  (Z  X)  (Z  Y).
295
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
296
  Lemma difference_intersection_distr_l X Y Z : (X  Y)  Z  X  Z  Y  Z.
297
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
298
  Lemma disjoint_union_difference X Y : X  Y    (X  Y)  X  Y.
299
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317

  Section leibniz.
    Context `{!LeibnizEquiv C}.
    Lemma intersection_singletons_L x : {[x]}  {[x]} = {[x]}.
    Proof. unfold_leibniz. apply intersection_singletons. Qed.
    Lemma difference_twice_L X Y : (X  Y)  Y = X  Y.
    Proof. unfold_leibniz. apply difference_twice. Qed.
    Lemma subseteq_empty_difference_L X Y : X  Y  X  Y = .
    Proof. unfold_leibniz. apply subseteq_empty_difference. Qed.
    Lemma difference_diag_L X : X  X = .
    Proof. unfold_leibniz. apply difference_diag. Qed.
    Lemma difference_union_distr_l_L X Y Z : (X  Y)  Z = X  Z  Y  Z.
    Proof. unfold_leibniz. apply difference_union_distr_l. Qed.
    Lemma difference_union_distr_r_L X Y Z : Z  (X  Y) = (Z  X)  (Z  Y).
    Proof. unfold_leibniz. apply difference_union_distr_r. Qed.
    Lemma difference_intersection_distr_l_L X Y Z :
      (X  Y)  Z = X  Z  Y  Z.
    Proof. unfold_leibniz. apply difference_intersection_distr_l. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
318
319
    Lemma disjoint_union_difference_L X Y : X  Y =   (X  Y)  X = Y.
    Proof. unfold_leibniz. apply disjoint_union_difference. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
320
321
322
  End leibniz.

  Section dec.
Robbert Krebbers's avatar
Robbert Krebbers committed
323
    Context `{ (x : A) (X : C), Decision (x  X)}.
Robbert Krebbers's avatar
Robbert Krebbers committed
324
325
326
327
328
329
330
331
332
333
334
335
    Lemma not_elem_of_intersection x X Y : x  X  Y  x  X  x  Y.
    Proof. rewrite elem_of_intersection. destruct (decide (x  X)); tauto. Qed.
    Lemma not_elem_of_difference x X Y : x  X  Y  x  X  x  Y.
    Proof. rewrite elem_of_difference. destruct (decide (x  Y)); tauto. Qed.
    Lemma union_difference X Y : X  Y  Y  X  Y  X.
    Proof.
      split; intros x; rewrite !elem_of_union, elem_of_difference; [|intuition].
      destruct (decide (x  X)); intuition.
    Qed.
    Lemma non_empty_difference X Y : X  Y  Y  X  .
    Proof.
      intros [HXY1 HXY2] Hdiff. destruct HXY2. intros x.
336
      destruct (decide (x  X)); set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
337
338
    Qed.
    Lemma empty_difference_subseteq X Y : X  Y    X  Y.
339
    Proof. intros ? x ?; apply dec_stable; set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
    Context `{!LeibnizEquiv C}.
    Lemma union_difference_L X Y : X  Y  Y = X  Y  X.
    Proof. unfold_leibniz. apply union_difference. Qed.
    Lemma non_empty_difference_L X Y : X  Y  Y  X  .
    Proof. unfold_leibniz. apply non_empty_difference. Qed.
    Lemma empty_difference_subseteq_L X Y : X  Y =   X  Y.
    Proof. unfold_leibniz. apply empty_difference_subseteq. Qed.
  End dec.
End collection.

Section collection_ops.
  Context `{CollectionOps A C}.

  Lemma elem_of_intersection_with_list (f : A  A  option A) Xs Y x :
    x  intersection_with_list f Y Xs   xs y,
      Forall2 () xs Xs  y  Y  foldr (λ x, (= f x)) (Some y) xs = Some x.
  Proof.
    split.
358
    - revert x. induction Xs; simpl; intros x HXs; [eexists [], x; intuition|].
Robbert Krebbers's avatar
Robbert Krebbers committed
359
360
      rewrite elem_of_intersection_with in HXs; destruct HXs as (x1&x2&?&?&?).
      destruct (IHXs x2) as (xs & y & hy & ? & ?); trivial.
361
      eexists (x1 :: xs), y. intuition (simplify_option_eq; auto).
362
    - intros (xs & y & Hxs & ? & Hx). revert x Hx.
363
      induction Hxs; intros; simplify_option_eq; [done |].
Robbert Krebbers's avatar
Robbert Krebbers committed
364
365
366
367
368
369
370
371
372
      rewrite elem_of_intersection_with. naive_solver.
  Qed.

  Lemma intersection_with_list_ind (P Q : A  Prop) f Xs Y :
    ( y, y  Y  P y) 
    Forall (λ X,  x, x  X  Q x) Xs 
    ( x y z, Q x  P y  f x y = Some z  P z) 
     x, x  intersection_with_list f Y Xs  P x.
  Proof.
373
    intros HY HXs Hf. induction Xs; simplify_option_eq; [done |].
Robbert Krebbers's avatar
Robbert Krebbers committed
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
    intros x Hx. rewrite elem_of_intersection_with in Hx.
    decompose_Forall. destruct Hx as (? & ? & ? & ? & ?). eauto.
  Qed.
End collection_ops.

(** * Sets without duplicates up to an equivalence *)
Section NoDup.
  Context `{SimpleCollection A B} (R : relation A) `{!Equivalence R}.

  Definition elem_of_upto (x : A) (X : B) :=  y, y  X  R x y.
  Definition set_NoDup (X : B) :=  x y, x  X  y  X  R x y  x = y.

  Global Instance: Proper (() ==> iff) (elem_of_upto x).
  Proof. intros ??? E. unfold elem_of_upto. by setoid_rewrite E. Qed.
  Global Instance: Proper (R ==> () ==> iff) elem_of_upto.
  Proof.
    intros ?? E1 ?? E2. split; intros [z [??]]; exists z.
391
392
    - rewrite <-E1, <-E2; intuition.
    - rewrite E1, E2; intuition.
Robbert Krebbers's avatar
Robbert Krebbers committed
393
394
395
396
397
  Qed.
  Global Instance: Proper (() ==> iff) set_NoDup.
  Proof. firstorder. Qed.

  Lemma elem_of_upto_elem_of x X : x  X  elem_of_upto x X.
398
  Proof. unfold elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
399
  Lemma elem_of_upto_empty x : ¬elem_of_upto x .
400
  Proof. unfold elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
401
  Lemma elem_of_upto_singleton x y : elem_of_upto x {[ y ]}  R x y.
402
  Proof. unfold elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
403
404
405

  Lemma elem_of_upto_union X Y x :
    elem_of_upto x (X  Y)  elem_of_upto x X  elem_of_upto x Y.
406
  Proof. unfold elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
407
  Lemma not_elem_of_upto x X : ¬elem_of_upto x X   y, y  X  ¬R x y.
408
  Proof. unfold elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
409
410

  Lemma set_NoDup_empty: set_NoDup .
411
  Proof. unfold set_NoDup. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
412
413
  Lemma set_NoDup_add x X :
    ¬elem_of_upto x X  set_NoDup X  set_NoDup ({[ x ]}  X).
414
  Proof. unfold set_NoDup, elem_of_upto. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
415
416
417
418
  Lemma set_NoDup_inv_add x X :
    x  X  set_NoDup ({[ x ]}  X)  ¬elem_of_upto x X.
  Proof.
    intros Hin Hnodup [y [??]].
419
    rewrite (Hnodup x y) in Hin; set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
420
421
  Qed.
  Lemma set_NoDup_inv_union_l X Y : set_NoDup (X  Y)  set_NoDup X.
422
  Proof. unfold set_NoDup. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
423
  Lemma set_NoDup_inv_union_r X Y : set_NoDup (X  Y)  set_NoDup Y.
424
  Proof. unfold set_NoDup. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
425
426
427
428
429
430
431
432
433
434
End NoDup.

(** * Quantifiers *)
Section quantifiers.
  Context `{SimpleCollection A B} (P : A  Prop).

  Definition set_Forall X :=  x, x  X  P x.
  Definition set_Exists X :=  x, x  X  P x.

  Lemma set_Forall_empty : set_Forall .
435
  Proof. unfold set_Forall. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
436
  Lemma set_Forall_singleton x : set_Forall {[ x ]}  P x.
437
  Proof. unfold set_Forall. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
438
  Lemma set_Forall_union X Y : set_Forall X  set_Forall Y  set_Forall (X  Y).
439
  Proof. unfold set_Forall. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
440
  Lemma set_Forall_union_inv_1 X Y : set_Forall (X  Y)  set_Forall X.
441
  Proof. unfold set_Forall. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
442
  Lemma set_Forall_union_inv_2 X Y : set_Forall (X  Y)  set_Forall Y.
443
  Proof. unfold set_Forall. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
444
445

  Lemma set_Exists_empty : ¬set_Exists .
446
  Proof. unfold set_Exists. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
447
  Lemma set_Exists_singleton x : set_Exists {[ x ]}  P x.
448
  Proof. unfold set_Exists. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
449
  Lemma set_Exists_union_1 X Y : set_Exists X  set_Exists (X  Y).
450
  Proof. unfold set_Exists. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
451
  Lemma set_Exists_union_2 X Y : set_Exists Y  set_Exists (X  Y).
452
  Proof. unfold set_Exists. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
453
454
  Lemma set_Exists_union_inv X Y :
    set_Exists (X  Y)  set_Exists X  set_Exists Y.
455
  Proof. unfold set_Exists. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
End quantifiers.

Section more_quantifiers.
  Context `{SimpleCollection A B}.

  Lemma set_Forall_weaken (P Q : A  Prop) (Hweaken :  x, P x  Q x) X :
    set_Forall P X  set_Forall Q X.
  Proof. unfold set_Forall. naive_solver. Qed.
  Lemma set_Exists_weaken (P Q : A  Prop) (Hweaken :  x, P x  Q x) X :
    set_Exists P X  set_Exists Q X.
  Proof. unfold set_Exists. naive_solver. Qed.
End more_quantifiers.

(** * Fresh elements *)
(** We collect some properties on the [fresh] operation. In particular we
generalize [fresh] to generate lists of fresh elements. *)
Fixpoint fresh_list `{Fresh A C, Union C, Singleton A C}
    (n : nat) (X : C) : list A :=
  match n with
  | 0 => []
  | S n => let x := fresh X in x :: fresh_list n ({[ x ]}  X)
  end.
Inductive Forall_fresh `{ElemOf A C} (X : C) : list A  Prop :=
  | Forall_fresh_nil : Forall_fresh X []
  | Forall_fresh_cons x xs :
     x  xs  x  X  Forall_fresh X xs  Forall_fresh X (x :: xs).

Section fresh.
  Context `{FreshSpec A C}.
485
  Implicit Types X Y : C.
Robbert Krebbers's avatar
Robbert Krebbers committed
486

487
  Global Instance fresh_proper: Proper (() ==> (=)) (fresh (C:=C)).
Robbert Krebbers's avatar
Robbert Krebbers committed
488
  Proof. intros ???. by apply fresh_proper_alt, elem_of_equiv. Qed.
489
490
  Global Instance fresh_list_proper:
    Proper ((=) ==> () ==> (=)) (fresh_list (C:=C)).
Robbert Krebbers's avatar
Robbert Krebbers committed
491
  Proof.
492
    intros ? n ->. induction n as [|n IH]; intros ?? E; f_equal/=; [by rewrite E|].
Robbert Krebbers's avatar
Robbert Krebbers committed
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
    apply IH. by rewrite E.
  Qed.

  Lemma Forall_fresh_NoDup X xs : Forall_fresh X xs  NoDup xs.
  Proof. induction 1; by constructor. Qed.
  Lemma Forall_fresh_elem_of X xs x : Forall_fresh X xs  x  xs  x  X.
  Proof.
    intros HX; revert x; rewrite <-Forall_forall.
    by induction HX; constructor.
  Qed.
  Lemma Forall_fresh_alt X xs :
    Forall_fresh X xs  NoDup xs   x, x  xs  x  X.
  Proof.
    split; eauto using Forall_fresh_NoDup, Forall_fresh_elem_of.
    rewrite <-Forall_forall.
    intros [Hxs Hxs']. induction Hxs; decompose_Forall_hyps; constructor; auto.
  Qed.
  Lemma Forall_fresh_subseteq X Y xs :
    Forall_fresh X xs  Y  X  Forall_fresh Y xs.
512
  Proof. rewrite !Forall_fresh_alt; set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
513
514
515
516
517
518
519

  Lemma fresh_list_length n X : length (fresh_list n X) = n.
  Proof. revert X. induction n; simpl; auto. Qed.
  Lemma fresh_list_is_fresh n X x : x  fresh_list n X  x  X.
  Proof.
    revert X. induction n as [|n IH]; intros X; simpl;[by rewrite elem_of_nil|].
    rewrite elem_of_cons; intros [->| Hin]; [apply is_fresh|].
520
    apply IH in Hin; set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
521
522
523
524
  Qed.
  Lemma NoDup_fresh_list n X : NoDup (fresh_list n X).
  Proof.
    revert X. induction n; simpl; constructor; auto.
525
    intros Hin; apply fresh_list_is_fresh in Hin; set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
526
527
528
529
530
531
532
533
534
535
536
  Qed.
  Lemma Forall_fresh_list X n : Forall_fresh X (fresh_list n X).
  Proof.
    rewrite Forall_fresh_alt; eauto using NoDup_fresh_list, fresh_list_is_fresh.
  Qed.
End fresh.

(** * Properties of implementations of collections that form a monad *)
Section collection_monad.
  Context `{CollectionMonad M}.

537
538
  Global Instance collection_fmap_mono {A B} :
    Proper (pointwise_relation _ (=) ==> () ==> ()) (@fmap M _ A B).
539
  Proof. intros f g ? X Y ?; set_solver by eauto. Qed.
540
541
  Global Instance collection_fmap_proper {A B} :
    Proper (pointwise_relation _ (=) ==> () ==> ()) (@fmap M _ A B).
542
  Proof. intros f g ? X Y [??]; split; set_solver by eauto. Qed.
543
544
  Global Instance collection_bind_mono {A B} :
    Proper (((=) ==> ()) ==> () ==> ()) (@mbind M _ A B).
545
  Proof. unfold respectful; intros f g Hfg X Y ?; set_solver. Qed.
546
547
  Global Instance collection_bind_proper {A B} :
    Proper (((=) ==> ()) ==> () ==> ()) (@mbind M _ A B).
548
  Proof. unfold respectful; intros f g Hfg X Y [??]; split; set_solver. Qed.
549
550
  Global Instance collection_join_mono {A} :
    Proper (() ==> ()) (@mjoin M _ A).
551
  Proof. intros X Y ?; set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
552
553
  Global Instance collection_join_proper {A} :
    Proper (() ==> ()) (@mjoin M _ A).
554
  Proof. intros X Y [??]; split; set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
555
556

  Lemma collection_bind_singleton {A B} (f : A  M B) x : {[ x ]} = f  f x.
557
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
558
  Lemma collection_guard_True {A} `{Decision P} (X : M A) : P  guard P; X  X.
559
  Proof. set_solver. Qed.
560
  Lemma collection_fmap_compose {A B C} (f : A  B) (g : B  C) (X : M A) :
Robbert Krebbers's avatar
Robbert Krebbers committed
561
    g  f <$> X  g <$> (f <$> X).
562
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
563
564
  Lemma elem_of_fmap_1 {A B} (f : A  B) (X : M A) (y : B) :
    y  f <$> X   x, y = f x  x  X.
565
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
566
567
  Lemma elem_of_fmap_2 {A B} (f : A  B) (X : M A) (x : A) :
    x  X  f x  f <$> X.
568
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
569
570
  Lemma elem_of_fmap_2_alt {A B} (f : A  B) (X : M A) (x : A) (y : B) :
    x  X  y = f x  y  f <$> X.
571
  Proof. set_solver. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
572
573
574
575
576

  Lemma elem_of_mapM {A B} (f : A  M B) l k :
    l  mapM f k  Forall2 (λ x y, x  f y) l k.
  Proof.
    split.
577
    - revert l. induction k; set_solver by eauto.
578
    - induction 1; set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
579
580
581
  Qed.
  Lemma collection_mapM_length {A B} (f : A  M B) l k :
    l  mapM f k  length l = length k.
582
  Proof. revert l; induction k; set_solver by eauto. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
583
584
585
586
  Lemma elem_of_mapM_fmap {A B} (f : A  B) (g : B  M A) l k :
    Forall (λ x,  y, y  g x  f y = x) l  k  mapM g l  fmap f k = l.
  Proof.
    intros Hl. revert k. induction Hl; simpl; intros;
587
      decompose_elem_of; f_equal/=; auto.
Robbert Krebbers's avatar
Robbert Krebbers committed
588
589
590
591
592
593
594
595
596
597
598
599
  Qed.
  Lemma elem_of_mapM_Forall {A B} (f : A  M B) (P : B  Prop) l k :
    l  mapM f k  Forall (λ x,  y, y  f x  P y) k  Forall P l.
  Proof. rewrite elem_of_mapM. apply Forall2_Forall_l. Qed.
  Lemma elem_of_mapM_Forall2_l {A B C} (f : A  M B) (P: B  C  Prop) l1 l2 k :
    l1  mapM f k  Forall2 (λ x y,  z, z  f x  P z y) k l2 
    Forall2 P l1 l2.
  Proof.
    rewrite elem_of_mapM. intros Hl1. revert l2.
    induction Hl1; inversion_clear 1; constructor; auto.
  Qed.
End collection_monad.
600
601
602
603
604
605

(** Finite collections *)
Definition set_finite `{ElemOf A B} (X : B) :=  l : list A,  x, x  X  x  l.

Section finite.
  Context `{SimpleCollection A B}.
606
607
  Global Instance set_finite_subseteq :
     Proper (flip () ==> impl) (@set_finite A B _).
608
  Proof. intros X Y HX [l Hl]; exists l; set_solver. Qed.
609
610
  Global Instance set_finite_proper : Proper (() ==> iff) (@set_finite A B _).
  Proof. by intros X Y [??]; split; apply set_finite_subseteq. Qed.
611
612
613
  Lemma empty_finite : set_finite .
  Proof. by exists []; intros ?; rewrite elem_of_empty. Qed.
  Lemma singleton_finite (x : A) : set_finite {[ x ]}.
Ralf Jung's avatar
Ralf Jung committed
614
  Proof. exists [x]; intros y ->%elem_of_singleton; left. Qed.
615
616
617
618
619
620
  Lemma union_finite X Y : set_finite X  set_finite Y  set_finite (X  Y).
  Proof.
    intros [lX ?] [lY ?]; exists (lX ++ lY); intros x.
    rewrite elem_of_union, elem_of_app; naive_solver.
  Qed.
  Lemma union_finite_inv_l X Y : set_finite (X  Y)  set_finite X.
621
  Proof. intros [l ?]; exists l; set_solver. Qed.
622
  Lemma union_finite_inv_r X Y : set_finite (X  Y)  set_finite Y.
623
  Proof. intros [l ?]; exists l; set_solver. Qed.
624
625
626
627
628
End finite.

Section more_finite.
  Context `{Collection A B}.
  Lemma intersection_finite_l X Y : set_finite X  set_finite (X  Y).
Ralf Jung's avatar
Ralf Jung committed
629
  Proof. intros [l ?]; exists l; intros x [??]%elem_of_intersection; auto. Qed.
630
  Lemma intersection_finite_r X Y : set_finite Y  set_finite (X  Y).
Ralf Jung's avatar
Ralf Jung committed
631
  Proof. intros [l ?]; exists l; intros x [??]%elem_of_intersection; auto. Qed.
632
  Lemma difference_finite X Y : set_finite X  set_finite (X  Y).
Ralf Jung's avatar
Ralf Jung committed
633
  Proof. intros [l ?]; exists l; intros x [??]%elem_of_difference; auto. Qed.
634
635
636
637
  Lemma difference_finite_inv X Y `{ x, Decision (x  Y)} :
    set_finite Y  set_finite (X  Y)  set_finite X.
  Proof.
    intros [l ?] [k ?]; exists (l ++ k).
638
    intros x ?; destruct (decide (x  Y)); rewrite elem_of_app; set_solver.
639
  Qed.
640
End more_finite.