Use `SProp` to obtain better definitional equality for `pmap`, `gmap`, `gset`, `Qp`, and `coPset`
This MR ensures that more equalities hold definitionally, and can thus be proved by reflexivity or even by conversion as part of unification.
For example 1/4 + 3/4 = 1, or {[ 1 := 1; 2 := 2 ]} = {[ 2 := 2; 1 := 1 ]}, or {[ 1 ]} ∖ {[ 1 ]} = ∅ can be proved using a mere reflexivity with this MR. Moreover, if you have a goal that involves, say 1/4 + 3/4, then you can just apply a lemma involving 1 because both are convertible.
This MR is based on !189 (closed) but makes various changes:
- Use
Squashinstead ofsUnitto ensure thatcoqchkcomes back clean. - Make the proofs of data structures like
pmapandgmapopaque so that we obtainO(log n)operations. This MR includes some tests, but they are commented out because such timings cannot be tested by CI. - Use
SPropforcoPsetandQp(!189 (closed) only consideredpmap,gmap, andgset)- The change for
coPsetwas pretty simple, but instead of a Sigma type, I had to use a record with anSPropfield. - The change for
Qpwas more involved.Qpwas originally defined in terms ofQcfrom the Coq standard lib, which itself is aQ+ aPropproof. Due to thePropproof, I could no longer useQcand had to inline anSPropversion ofQp. In the process, I also decided to no longer useQ, which is defined as a pair of aZand apositive, but just use pairs ofpositives. That avoids the need for a proof of the fraction being positive. None of these changes should be visible in theQpAPI.
- The change for
This MR changes the implementations of the aforementioned data structures, but their APIs should not have changed.
Fixes #85
Edited by Ralf Jung