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
Squash
instead ofsUnit
to ensure thatcoqchk
comes back clean. - Make the proofs of data structures like
pmap
andgmap
opaque 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
SProp
forcoPset
andQp
(!189 (closed) only consideredpmap
,gmap
, andgset
)- The change for
coPset
was pretty simple, but instead of a Sigma type, I had to use a record with anSProp
field. - The change for
Qp
was more involved.Qp
was originally defined in terms ofQc
from the Coq standard lib, which itself is aQ
+ aProp
proof. Due to theProp
proof, I could no longer useQc
and had to inline anSProp
version ofQp
. In the process, I also decided to no longer useQ
, which is defined as a pair of aZ
and 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 theQp
API.
- 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