search

ElectrifyPro / cas-rs

An opinionated computer algebra system written in Rust, used by CalcBot.
MIT License
35 stars 3 forks source link

Manual std::hash::Hash implementation for consistency with PartialEq #2

Closed BilakshanP closed 1 month ago

BilakshanP commented 2 months ago

This guarantees that the PartialEq for Hash would be consistent. Please let me know if anything has to be changed, modified or if it is bluntly incorrect.

This implementation is similar to the derive macro implementation.

ElectrifyPro commented 2 months ago

Hi, thank you very much for the PR! This looks nearly perfect, but there is one important implementation detail to note.

It's important that two Expr::Adds or two Expr::Mul instances that would be semantically equal are considered equal under PartialEq. For example, the existing PartialEq implementation on Expr treats these as equal:

Expr::Add([1, 4, 9, 16, 25]) == Expr::Add([25, 16, 9, 4, 1])
Expr::Mul([36, x, y]) == Expr::Mul([y, 36, x])

You would need to consider this detail in your implementation of Hash. Currently, it appears that the order of terms in Expr::Add or products in Expr::Mul would influence the resulting hash. However, this shouldn't be the case to match PartialEq.

BilakshanP commented 2 months ago

Yeah, you are right I didn't take that into account. I might do something and figure how does the order affect the (hash) output. On-top of my head I can't think of any good (efficient) way to solve this problem.

Either we can sort the arguments or simplify them. There should be a better way.

Edit: Though, Hash might use the existing definition of PartialEq as I am not sure. I'd look into that.

ElectrifyPro commented 2 months ago

This problem is akin to the problem of hashing a multiset, where the order of elements does not matter, but the frequency in which they occur does. One idea is hashing each element on its own, and summing or XORing the resulting hashes, which would result in the same hash regardless of order, though there are a lot of interesting reads online about this topic. That could possibly give you some inspiration.

BilakshanP commented 2 months ago

Yeah, that would a good place to start from. Found something related: CS Stack Exchange

ElectrifyPro commented 1 month ago

This looks good to me! There are still a number of things I would change style-wise, but as the functionality is all there, I've decided to merge this. Thanks for your hard work!