Skip to content
  • Robbert Krebbers's avatar
    Generic big operators that are no longer tied to CMRAs. · 6fbff46e
    Robbert Krebbers authored
    Instead, I have introduced a type class `Monoid` that is used by the big operators:
    
        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;
        }.
    
    Note that 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, the unit would appear explicitly in an implicit argument of the
      big operators, which confuses rewrite. By bundling the unit in the `Monoid` class
      it is hidden, 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 bundled setoids, I did not go that way.
    6fbff46e