Support equality between commutative expressions #27
Comments
|
Trying to dive into this, I naïvely thought, "No problem, we just want to sort the operands when dealing with a commutative infix operator!" completely forgetting that the operands are themselves |
|
Yup, I think you're right! Closing. |
genos
pushed a commit
that referenced
this issue
Aug 10, 2023
BREAKING: Expressions no longer use hashing for implementing equality BREAKING: Expression equality no longer takes commutativity into account In #276, @Shadow53 noted > One thing that may be useful enough to pull into its own PR is the > change to not use hashing in the implementation of `PartialEq` for > `Expression`, which also helps speed things up. We originally put this together in #27 to ensure that equality held in the face of commutativity, e.g., `1 + x == x + 1`. In addition to the performance benefits of decoupling the hashing and equality implementations, it makes sense to remove any special status for commutative operations in light of all the work we're doing on expression simplification. If we wished to ensure expressions are `Eq` if and only if they represent the same mathematical expression, we'd have to have equality contingent upon simplification, which would be even more costly.
genos
added a commit
that referenced
this issue
Aug 10, 2023
* feat!: Decouple expression hashing and equality BREAKING: Expressions no longer use hashing for implementing equality BREAKING: Expression equality no longer takes commutativity into account In #276, @Shadow53 noted > One thing that may be useful enough to pull into its own PR is the > change to not use hashing in the implementation of `PartialEq` for > `Expression`, which also helps speed things up. We originally put this together in #27 to ensure that equality held in the face of commutativity, e.g., `1 + x == x + 1`. In addition to the performance benefits of decoupling the hashing and equality implementations, it makes sense to remove any special status for commutative operations in light of all the work we're doing on expression simplification. If we wished to ensure expressions are `Eq` if and only if they represent the same mathematical expression, we'd have to have equality contingent upon simplification, which would be even more costly. * fix: Use Self::
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Expressions which are equal by the commutative property should evaluate to equal and hash the same. As an example, an expression
1 + thetashould be equivalent totheta + 1both when compared directly (e.g.assert_eq!) and when hashed (e.g. added to aHashSet).Per this comment we have some internal code in the QCS backend which creates a "canonical" or "normal" form of expressions which we can likely reuse.
The text was updated successfully, but these errors were encountered: