monoid.v 2.08 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
From iris.algebra Require Export ofe.
Set Default Proof Using "Type".

(** The Monoid class that is used for generic big operators in the file
[algebra/big_op]. The operation is an argument because we want to have multiple
monoids over the same type (for example, on [uPred]s we have monoids for [],
[], and []). However, we do bundle the unit because:

- If we would not, it would appear explicitly in an argument of the big
  operators, which confuses rewrite. Now it is hidden in the class, and hence
  rewrite won't even see it.
- The unit is unique.

We could in principle have big ops over setoids instead of OFEs. However, since
we do not have a canonical structure for setoids, we do not go that way.

Note that we do not declare any of the projections as type class instances. That
is because we only need them in the [big_op] file, and nowhere else. Hence, we
declare these instances locally there to avoid them being used elsewhere. *)
Class Monoid {M : ofeT} (o : M  M  M) := {
  monoid_unit : M;
  monoid_ne : NonExpansive2 o;
  monoid_assoc : Assoc () o;
  monoid_comm : Comm () o;
  monoid_left_id : LeftId () monoid_unit o;
  monoid_right_id : RightId () monoid_unit o;
}.
Lemma monoid_proper `{Monoid M o} : Proper (() ==> () ==> ()) o.
Proof. apply ne_proper_2, monoid_ne. Qed.

(** The [Homomorphism] classes give rise to generic lemmas about big operators
commuting with each other. *)
Class WeakMonoidHomomorphism {M1 M2 : ofeT} (o1 : M1  M1  M1) (o2 : M2  M2  M2)
    `{Monoid M1 o1, Monoid M2 o2} (f : M1  M2) := {
  monoid_homomorphism_ne : NonExpansive f;
  monoid_homomorphism x y : f (o1 x y)  o2 (f x) (f y)
}.

Class MonoidHomomorphism {M1 M2 : ofeT} (o1 : M1  M1  M1) (o2 : M2  M2  M2)
    `{Monoid M1 o1, Monoid M2 o2} (f : M1  M2) := {
  monoid_homomorphism_weak :> WeakMonoidHomomorphism o1 o2 f;
  monoid_homomorphism_unit : f monoid_unit  monoid_unit
}.

Lemma weak_monoid_homomorphism_proper
  `{WeakMonoidHomomorphism M1 M2 o1 o2 f} : Proper (() ==> ()) f.
Proof. apply ne_proper, monoid_homomorphism_ne. Qed.