fin_maps.v 16.3 KB
Newer Older
1
2
3
From iris.algebra Require Export cmra option.
From iris.prelude Require Export gmap.
From iris.algebra Require Import upred.
4

5
6
Section cofe.
Context `{Countable K} {A : cofeT}.
7
Implicit Types m : gmap K A.
8

9
Instance map_dist : Dist (gmap K A) := λ n m1 m2,
10
   i, m1 !! i {n} m2 !! i.
11
Program Definition map_chain (c : chain (gmap K A))
12
  (k : K) : chain (option A) := {| chain_car n := c n !! k |}.
13
14
Next Obligation. by intros c k n i ?; apply (chain_cauchy c). Qed.
Instance map_compl : Compl (gmap K A) := λ c,
15
  map_imap (λ i _, compl (map_chain c i)) (c 0).
16
Definition map_cofe_mixin : CofeMixin (gmap K A).
17
18
Proof.
  split.
19
  - intros m1 m2; split.
20
21
    + by intros Hm n k; apply equiv_dist.
    + intros Hm k; apply equiv_dist; intros n; apply Hm.
22
  - intros n; split.
23
24
    + by intros m k.
    + by intros m1 m2 ? k.
25
    + by intros m1 m2 m3 ?? k; trans (m2 !! k).
26
  - by intros n m1 m2 ? k; apply dist_S.
Robbert Krebbers's avatar
Robbert Krebbers committed
27
  - intros n c k; rewrite /compl /map_compl lookup_imap.
28
    feed inversion (λ H, chain_cauchy c 0 n H k); simpl; auto with lia.
29
    by rewrite conv_compl /=; apply reflexive_eq.
30
Qed.
31
Canonical Structure mapC : cofeT := CofeT map_cofe_mixin.
32
33
Global Instance map_discrete : Discrete A  Discrete mapC.
Proof. intros ? m m' ? i. by apply (timeless _). Qed.
34
35
36
37
(* why doesn't this go automatic? *)
Global Instance mapC_leibniz: LeibnizEquiv A  LeibnizEquiv mapC.
Proof. intros; change (LeibnizEquiv (gmap K A)); apply _. Qed.

38
Global Instance lookup_ne n k :
39
  Proper (dist n ==> dist n) (lookup k : gmap K A  option A).
40
Proof. by intros m1 m2. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
41
42
Global Instance lookup_proper k :
  Proper (() ==> ()) (lookup k : gmap K A  option A) := _.
43
44
45
46
Global Instance alter_ne f k n :
  Proper (dist n ==> dist n) f  Proper (dist n ==> dist n) (alter f k).
Proof.
  intros ? m m' Hm k'.
47
  by destruct (decide (k = k')); simplify_map_eq; rewrite (Hm k').
48
Qed.
49
Global Instance insert_ne i n :
50
  Proper (dist n ==> dist n ==> dist n) (insert (M:=gmap K A) i).
51
Proof.
52
  intros x y ? m m' ? j; destruct (decide (i = j)); simplify_map_eq;
53
54
    [by constructor|by apply lookup_ne].
Qed.
55
Global Instance singleton_ne i n :
56
57
  Proper (dist n ==> dist n) (singletonM i : A  gmap K A).
Proof. by intros ???; apply insert_ne. Qed.
58
Global Instance delete_ne i n :
59
  Proper (dist n ==> dist n) (delete (M:=gmap K A) i).
60
Proof.
61
  intros m m' ? j; destruct (decide (i = j)); simplify_map_eq;
62
63
    [by constructor|by apply lookup_ne].
Qed.
64

65
Instance map_empty_timeless : Timeless ( : gmap K A).
66
67
68
69
Proof.
  intros m Hm i; specialize (Hm i); rewrite lookup_empty in Hm |- *.
  inversion_clear Hm; constructor.
Qed.
70
Global Instance map_lookup_timeless m i : Timeless m  Timeless (m !! i).
71
Proof.
72
  intros ? [x|] Hx; [|by symmetry; apply: timeless].
73
  assert (m {0} <[i:=x]> m)
Robbert Krebbers's avatar
Robbert Krebbers committed
74
75
    by (by symmetry in Hx; inversion Hx; cofe_subst; rewrite insert_id).
  by rewrite (timeless m (<[i:=x]>m)) // lookup_insert.
76
Qed.
77
Global Instance map_insert_timeless m i x :
78
79
  Timeless x  Timeless m  Timeless (<[i:=x]>m).
Proof.
80
  intros ?? m' Hm j; destruct (decide (i = j)); simplify_map_eq.
81
82
  { by apply: timeless; rewrite -Hm lookup_insert. }
  by apply: timeless; rewrite -Hm lookup_insert_ne.
83
Qed.
84
Global Instance map_singleton_timeless i x :
85
  Timeless x  Timeless ({[ i := x ]} : gmap K A) := _.
86
End cofe.
87

88
Arguments mapC _ {_ _} _.
89
90

(* CMRA *)
91
92
Section cmra.
Context `{Countable K} {A : cmraT}.
93
Implicit Types m : gmap K A.
94
95

Instance map_op : Op (gmap K A) := merge op.
Ralf Jung's avatar
Ralf Jung committed
96
Instance map_core : Core (gmap K A) := fmap core.
97
Instance map_valid : Valid (gmap K A) := λ m,  i,  (m !! i).
98
Instance map_validN : ValidN (gmap K A) := λ n m,  i, {n} (m !! i).
99
Instance map_div : Div (gmap K A) := merge div.
100

101
Lemma lookup_op m1 m2 i : (m1  m2) !! i = m1 !! i  m2 !! i.
102
Proof. by apply lookup_merge. Qed.
103
Lemma lookup_div m1 m2 i : (m1 ÷ m2) !! i = m1 !! i ÷ m2 !! i.
104
Proof. by apply lookup_merge. Qed.
Ralf Jung's avatar
Ralf Jung committed
105
Lemma lookup_core m i : core m !! i = core (m !! i).
106
Proof. by apply lookup_fmap. Qed.
107

108
Lemma map_included_spec (m1 m2 : gmap K A) : m1  m2   i, m1 !! i  m2 !! i.
109
110
Proof.
  split.
111
  - by intros [m Hm]; intros i; exists (m !! i); rewrite -lookup_op Hm.
112
113
  - intros Hm; exists (m2 ÷ m1); intros i.
    by rewrite lookup_op lookup_div cmra_op_div.
114
Qed.
115
Lemma map_includedN_spec (m1 m2 : gmap K A) n :
116
117
118
  m1 {n} m2   i, m1 !! i {n} m2 !! i.
Proof.
  split.
119
  - by intros [m Hm]; intros i; exists (m !! i); rewrite -lookup_op Hm.
120
121
  - intros Hm; exists (m2 ÷ m1); intros i.
    by rewrite lookup_op lookup_div cmra_op_div'.
122
Qed.
123

124
Definition map_cmra_mixin : CMRAMixin (gmap K A).
125
126
Proof.
  split.
127
  - by intros n m1 m2 m3 Hm i; rewrite !lookup_op (Hm i).
Ralf Jung's avatar
Ralf Jung committed
128
  - by intros n m1 m2 Hm i; rewrite !lookup_core (Hm i).
129
  - by intros n m1 m2 Hm ? i; rewrite -(Hm i).
130
  - by intros n m1 m1' Hm1 m2 m2' Hm2 i; rewrite !lookup_div (Hm1 i) (Hm2 i).
131
132
133
  - intros m; split.
    + by intros ? n i; apply cmra_valid_validN.
    + intros Hm i; apply cmra_valid_validN=> n; apply Hm.
134
135
136
  - intros n m Hm i; apply cmra_validN_S, Hm.
  - by intros m1 m2 m3 i; rewrite !lookup_op assoc.
  - by intros m1 m2 i; rewrite !lookup_op comm.
Ralf Jung's avatar
Ralf Jung committed
137
138
  - by intros m i; rewrite lookup_op !lookup_core cmra_core_l.
  - by intros m i; rewrite !lookup_core cmra_core_idemp.
Robbert Krebbers's avatar
Robbert Krebbers committed
139
  - intros x y; rewrite !map_included_spec; intros Hm i.
Ralf Jung's avatar
Ralf Jung committed
140
    by rewrite !lookup_core; apply cmra_core_preserving.
141
  - intros n m1 m2 Hm i; apply cmra_validN_op_l with (m2 !! i).
Robbert Krebbers's avatar
Robbert Krebbers committed
142
    by rewrite -lookup_op.
Robbert Krebbers's avatar
Robbert Krebbers committed
143
  - intros x y; rewrite map_included_spec=> ? i.
144
    by rewrite lookup_op lookup_div cmra_op_div.
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
  - intros n m m1 m2 Hm Hm12.
    assert ( i, m !! i {n} m1 !! i  m2 !! i) as Hm12'
      by (by intros i; rewrite -lookup_op).
    set (f i := cmra_extend n (m !! i) (m1 !! i) (m2 !! i) (Hm i) (Hm12' i)).
    set (f_proj i := proj1_sig (f i)).
    exists (map_imap (λ i _, (f_proj i).1) m, map_imap (λ i _, (f_proj i).2) m);
      repeat split; intros i; rewrite /= ?lookup_op !lookup_imap.
    + destruct (m !! i) as [x|] eqn:Hx; rewrite !Hx /=; [|constructor].
      rewrite -Hx; apply (proj2_sig (f i)).
    + destruct (m !! i) as [x|] eqn:Hx; rewrite /=; [apply (proj2_sig (f i))|].
      pose proof (Hm12' i) as Hm12''; rewrite Hx in Hm12''.
      by symmetry; apply option_op_positive_dist_l with (m2 !! i).
    + destruct (m !! i) as [x|] eqn:Hx; simpl; [apply (proj2_sig (f i))|].
      pose proof (Hm12' i) as Hm12''; rewrite Hx in Hm12''.
      by symmetry; apply option_op_positive_dist_r with (m1 !! i).
160
Qed.
161
Canonical Structure mapR : cmraT := CMRAT map_cofe_mixin map_cmra_mixin.
Ralf Jung's avatar
Ralf Jung committed
162
Global Instance map_cmra_unit : CMRAUnit mapR.
163
164
Proof.
  split.
165
  - by intros i; rewrite lookup_empty.
166
167
  - by intros m i; rewrite /= lookup_op lookup_empty (left_id_L None _).
  - apply map_empty_timeless.
168
Qed.
169
Global Instance map_cmra_discrete : CMRADiscrete A  CMRADiscrete mapR.
170
Proof. split; [apply _|]. intros m ? i. by apply: cmra_discrete_valid. Qed.
171
172
173

(** Internalized properties *)
Lemma map_equivI {M} m1 m2 : (m1  m2)%I  ( i, m1 !! i  m2 !! i : uPred M)%I.
174
Proof. by uPred.unseal. Qed.
175
Lemma map_validI {M} m : ( m)%I  ( i,  (m !! i) : uPred M)%I.
176
Proof. by uPred.unseal. Qed.
177
End cmra.
178

179
Arguments mapR _ {_ _} _.
180
181

Section properties.
182
Context `{Countable K} {A : cmraT}.
Robbert Krebbers's avatar
Robbert Krebbers committed
183
Implicit Types m : gmap K A.
184
185
Implicit Types i : K.
Implicit Types a : A.
186

187
Lemma map_lookup_validN n m i x : {n} m  m !! i {n} Some x  {n} x.
Robbert Krebbers's avatar
Robbert Krebbers committed
188
Proof. by move=> /(_ i) Hm Hi; move:Hm; rewrite Hi. Qed.
189
Lemma map_lookup_valid m i x :  m  m !! i  Some x   x.
190
Proof. move=> Hm Hi. move:(Hm i). by rewrite Hi. Qed.
191
Lemma map_insert_validN n m i x : {n} x  {n} m  {n} <[i:=x]>m.
192
Proof. by intros ?? j; destruct (decide (i = j)); simplify_map_eq. Qed.
193
Lemma map_insert_valid m i x :  x   m   <[i:=x]>m.
194
Proof. by intros ?? j; destruct (decide (i = j)); simplify_map_eq. Qed.
195
Lemma map_singleton_validN n i x : {n} ({[ i := x ]} : gmap K A)  {n} x.
196
Proof.
Ralf Jung's avatar
Ralf Jung committed
197
  split; [|by intros; apply map_insert_validN, cmra_unit_validN].
198
  by move=>/(_ i); simplify_map_eq.
199
Qed.
200
Lemma map_singleton_valid i x :  ({[ i := x ]} : gmap K A)   x.
201
Proof. rewrite !cmra_valid_validN. by setoid_rewrite map_singleton_validN. Qed.
202

203
Lemma map_insert_singleton_opN n m i x :
Ralf Jung's avatar
Ralf Jung committed
204
  m !! i = None  m !! i {n} Some (core x)  <[i:=x]> m {n} {[ i := x ]}  m.
205
Proof.
206
207
208
  intros Hi j; destruct (decide (i = j)) as [->|];
    [|by rewrite lookup_op lookup_insert_ne // lookup_singleton_ne // left_id].
  rewrite lookup_op lookup_insert lookup_singleton.
Ralf Jung's avatar
Ralf Jung committed
209
  by destruct Hi as [->| ->]; constructor; rewrite ?cmra_core_r.
210
Qed.
211
Lemma map_insert_singleton_op m i x :
Ralf Jung's avatar
Ralf Jung committed
212
  m !! i = None  m !! i  Some (core x)  <[i:=x]> m  {[ i := x ]}  m.
213
Proof.
214
  rewrite !equiv_dist; naive_solver eauto using map_insert_singleton_opN.
215
216
Qed.

Ralf Jung's avatar
Ralf Jung committed
217
218
Lemma map_core_singleton (i : K) (x : A) :
  core ({[ i := x ]} : gmap K A) = {[ i := core x ]}.
219
220
Proof. apply map_fmap_singleton. Qed.
Lemma map_op_singleton (i : K) (x y : A) :
221
  {[ i := x ]}  {[ i := y ]} = ({[ i := x  y ]} : gmap K A).
222
Proof. by apply (merge_singleton _ _ _ x y). Qed.
223

Robbert Krebbers's avatar
Robbert Krebbers committed
224
Lemma singleton_includedN n m i x :
225
  {[ i := x ]} {n} m   y, m !! i {n} Some y  x  y.
Robbert Krebbers's avatar
Robbert Krebbers committed
226
227
228
  (* not m !! i = Some y ∧ x ≼{n} y to deal with n = 0 *)
Proof.
  split.
229
  - move=> [m' /(_ i)]; rewrite lookup_op lookup_singleton=> Hm.
Robbert Krebbers's avatar
Robbert Krebbers committed
230
    destruct (m' !! i) as [y|];
231
      [exists (x  y)|exists x]; eauto using cmra_included_l.
232
  - intros (y&Hi&?); rewrite map_includedN_spec=>j.
233
    destruct (decide (i = j)); simplify_map_eq.
Robbert Krebbers's avatar
Robbert Krebbers committed
234
    + rewrite Hi. by apply (includedN_preserving _), cmra_included_includedN.
Ralf Jung's avatar
Ralf Jung committed
235
    + apply: cmra_unit_leastN.
Robbert Krebbers's avatar
Robbert Krebbers committed
236
Qed.
237
Lemma map_dom_op m1 m2 : dom (gset K) (m1  m2)  dom _ m1  dom _ m2.
238
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
239
  apply elem_of_equiv; intros i; rewrite elem_of_union !elem_of_dom.
240
241
242
  unfold is_Some; setoid_rewrite lookup_op.
  destruct (m1 !! i), (m2 !! i); naive_solver.
Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
243

244
Lemma map_insert_updateP (P : A  Prop) (Q : gmap K A  Prop) m i x :
245
  x ~~>: P  ( y, P y  Q (<[i:=y]>m))  <[i:=x]>m ~~>: Q.
246
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
247
248
  intros Hx%option_updateP' HP n mf Hm.
  destruct (Hx n (mf !! i)) as ([y|]&?&?); try done.
249
  { by generalize (Hm i); rewrite lookup_op; simplify_map_eq. }
250
251
  exists (<[i:=y]> m); split; first by auto.
  intros j; move: (Hm j)=>{Hm}; rewrite !lookup_op=>Hm.
252
  destruct (decide (i = j)); simplify_map_eq/=; auto.
253
Qed.
254
Lemma map_insert_updateP' (P : A  Prop) m i x :
255
  x ~~>: P  <[i:=x]>m ~~>: λ m',  y, m' = <[i:=y]>m  P y.
256
Proof. eauto using map_insert_updateP. Qed.
257
Lemma map_insert_update m i x y : x ~~> y  <[i:=x]>m ~~> <[i:=y]>m.
258
Proof.
259
  rewrite !cmra_update_updateP; eauto using map_insert_updateP with subst.
260
261
Qed.

262
Lemma map_singleton_updateP (P : A  Prop) (Q : gmap K A  Prop) i x :
263
  x ~~>: P  ( y, P y  Q {[ i := y ]})  {[ i := x ]} ~~>: Q.
264
265
Proof. apply map_insert_updateP. Qed.
Lemma map_singleton_updateP' (P : A  Prop) i x :
266
  x ~~>: P  {[ i := x ]} ~~>: λ m,  y, m = {[ i := y ]}  P y.
267
Proof. apply map_insert_updateP'. Qed.
268
Lemma map_singleton_update i (x y : A) : x ~~> y  {[ i := x ]} ~~> {[ i := y ]}.
269
Proof. apply map_insert_update. Qed.
270

Ralf Jung's avatar
Ralf Jung committed
271
Lemma map_singleton_updateP_empty `{Empty A, !CMRAUnit A}
Robbert Krebbers's avatar
Robbert Krebbers committed
272
    (P : A  Prop) (Q : gmap K A  Prop) i :
273
   ~~>: P  ( y, P y  Q {[ i := y ]})   ~~>: Q.
Robbert Krebbers's avatar
Robbert Krebbers committed
274
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
275
276
  intros Hx HQ n gf Hg.
  destruct (Hx n (from_option  (gf !! i))) as (y&?&Hy).
Robbert Krebbers's avatar
Robbert Krebbers committed
277
  { move:(Hg i). rewrite !left_id.
Ralf Jung's avatar
Ralf Jung committed
278
    case _: (gf !! i); simpl; auto using cmra_unit_validN. }
279
  exists {[ i := y ]}; split; first by auto.
Robbert Krebbers's avatar
Robbert Krebbers committed
280
281
282
283
284
  intros i'; destruct (decide (i' = i)) as [->|].
  - rewrite lookup_op lookup_singleton.
    move:Hy; case _: (gf !! i); first done.
    by rewrite right_id.
  - move:(Hg i'). by rewrite !lookup_op lookup_singleton_ne // !left_id.
285
Qed.
Ralf Jung's avatar
Ralf Jung committed
286
Lemma map_singleton_updateP_empty' `{Empty A, !CMRAUnit A} (P: A  Prop) i :
287
   ~~>: P   ~~>: λ m,  y, m = {[ i := y ]}  P y.
288
289
Proof. eauto using map_singleton_updateP_empty. Qed.

290
Section freshness.
Robbert Krebbers's avatar
Robbert Krebbers committed
291
Context `{Fresh K (gset K), !FreshSpec K (gset K)}.
292
293
Lemma map_updateP_alloc_strong (Q : gmap K A  Prop) (I : gset K) m x :
   x  ( i, m !! i = None  i  I  Q (<[i:=x]>m))  m ~~>: Q.
294
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
295
  intros ? HQ n mf Hm. set (i := fresh (I  dom (gset K) (m  mf))).
296
297
  assert (i  I  i  dom (gset K) m  i  dom (gset K) mf) as [?[??]].
  { rewrite -not_elem_of_union -map_dom_op -not_elem_of_union; apply is_fresh. }
298
299
300
301
302
  exists (<[i:=x]>m); split.
  { by apply HQ; last done; apply not_elem_of_dom. }
  rewrite map_insert_singleton_opN; last by left; apply not_elem_of_dom.
  rewrite -assoc -map_insert_singleton_opN;
    last by left; apply not_elem_of_dom; rewrite map_dom_op not_elem_of_union.
303
  by apply map_insert_validN; [apply cmra_valid_validN|].
304
Qed.
305
306
307
308
309
310
Lemma map_updateP_alloc (Q : gmap K A  Prop) m x :
   x  ( i, m !! i = None  Q (<[i:=x]>m))  m ~~>: Q.
Proof. move=>??. eapply map_updateP_alloc_strong with (I:=); by eauto. Qed.
Lemma map_updateP_alloc_strong' m x (I : gset K) :
   x  m ~~>: λ m',  i, i  I  m' = <[i:=x]>m  m !! i = None.
Proof. eauto using map_updateP_alloc_strong. Qed.
311
Lemma map_updateP_alloc' m x :
312
   x  m ~~>: λ m',  i, m' = <[i:=x]>m  m !! i = None.
313
Proof. eauto using map_updateP_alloc. Qed.
314
315
End freshness.

316
317
(* Allocation is a local update: Just use composition with a singleton map. *)
(* Deallocation is *not* a local update. The trouble is that if we
Ralf Jung's avatar
Ralf Jung committed
318
   own {[ i ↦ x ]}, then the frame could always own "core x", and prevent
319
320
321
   deallocation. *)

(* Applying a local update at a position we own is a local update. *)
322
323
Global Instance map_alter_update `{!LocalUpdate Lv L} i :
  LocalUpdate (λ m,  x, m !! i = Some x  Lv x) (alter L i).
324
Proof.
325
326
327
328
  split; first apply _.
  intros n m1 m2 (x&Hix&?) Hm j; destruct (decide (i = j)) as [->|].
  - rewrite lookup_alter !lookup_op lookup_alter Hix /=.
    move: (Hm j); rewrite lookup_op Hix.
329
    case: (m2 !! j)=>[y|] //=; constructor. by apply (local_updateN L).
330
  - by rewrite lookup_op !lookup_alter_ne // lookup_op.
331
Qed.
332
333
End properties.

334
(** Functor *)
335
336
337
338
339
340
Instance map_fmap_ne `{Countable K} {A B : cofeT} (f : A  B) n :
  Proper (dist n ==> dist n) f  Proper (dist n ==>dist n) (fmap (M:=gmap K) f).
Proof. by intros ? m m' Hm k; rewrite !lookup_fmap; apply option_fmap_ne. Qed.
Instance map_fmap_cmra_monotone `{Countable K} {A B : cmraT} (f : A  B)
  `{!CMRAMonotone f} : CMRAMonotone (fmap f : gmap K A  gmap K B).
Proof.
Robbert Krebbers's avatar
Robbert Krebbers committed
341
  split; try apply _.
342
  - by intros n m ? i; rewrite lookup_fmap; apply (validN_preserving _).
Robbert Krebbers's avatar
Robbert Krebbers committed
343
344
  - intros m1 m2; rewrite !map_included_spec=> Hm i.
    by rewrite !lookup_fmap; apply: included_preserving.
345
Qed.
346
347
348
349
350
351
352
353
Definition mapC_map `{Countable K} {A B} (f: A -n> B) : mapC K A -n> mapC K B :=
  CofeMor (fmap f : mapC K A  mapC K B).
Instance mapC_map_ne `{Countable K} {A B} n :
  Proper (dist n ==> dist n) (@mapC_map K _ _ A B).
Proof.
  intros f g Hf m k; rewrite /= !lookup_fmap.
  destruct (_ !! k) eqn:?; simpl; constructor; apply Hf.
Qed.
Ralf Jung's avatar
Ralf Jung committed
354

355
356
357
Program Definition mapCF K `{Countable K} (F : cFunctor) : cFunctor := {|
  cFunctor_car A B := mapC K (cFunctor_car F A B);
  cFunctor_map A1 A2 B1 B2 fg := mapC_map (cFunctor_map F fg)
Ralf Jung's avatar
Ralf Jung committed
358
|}.
359
360
361
Next Obligation.
  by intros K ?? F A1 A2 B1 B2 n f g Hfg; apply mapC_map_ne, cFunctor_ne.
Qed.
Ralf Jung's avatar
Ralf Jung committed
362
Next Obligation.
363
364
  intros K ?? F A B x. rewrite /= -{2}(map_fmap_id x).
  apply map_fmap_setoid_ext=>y ??; apply cFunctor_id.
Ralf Jung's avatar
Ralf Jung committed
365
366
Qed.
Next Obligation.
367
368
369
  intros K ?? F A1 A2 A3 B1 B2 B3 f g f' g' x. rewrite /= -map_fmap_compose.
  apply map_fmap_setoid_ext=>y ??; apply cFunctor_compose.
Qed.
370
371
372
373
374
375
Instance mapCF_contractive K `{Countable K} F :
  cFunctorContractive F  cFunctorContractive (mapCF K F).
Proof.
  by intros ? A1 A2 B1 B2 n f g Hfg; apply mapC_map_ne, cFunctor_contractive.
Qed.

376
377
378
379
Program Definition mapRF K `{Countable K} (F : rFunctor) : rFunctor := {|
  rFunctor_car A B := mapR K (rFunctor_car F A B);
  rFunctor_map A1 A2 B1 B2 fg := mapC_map (rFunctor_map F fg)
|}.
380
381
382
Next Obligation.
  by intros K ?? F A1 A2 B1 B2 n f g Hfg; apply mapC_map_ne, rFunctor_ne.
Qed.
383
384
385
386
387
388
389
Next Obligation.
  intros K ?? F A B x. rewrite /= -{2}(map_fmap_id x).
  apply map_fmap_setoid_ext=>y ??; apply rFunctor_id.
Qed.
Next Obligation.
  intros K ?? F A1 A2 A3 B1 B2 B3 f g f' g' x. rewrite /= -map_fmap_compose.
  apply map_fmap_setoid_ext=>y ??; apply rFunctor_compose.
Ralf Jung's avatar
Ralf Jung committed
390
Qed.
391
392
393
394
395
Instance mapRF_contractive K `{Countable K} F :
  rFunctorContractive F  rFunctorContractive (mapRF K F).
Proof.
  by intros ? A1 A2 B1 B2 n f g Hfg; apply mapC_map_ne, rFunctor_contractive.
Qed.