Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

DeepEquals should handle Sets (and Maps) #66

Open
pygy opened this issue Dec 15, 2023 · 1 comment
Open

DeepEquals should handle Sets (and Maps) #66

pygy opened this issue Dec 15, 2023 · 1 comment

Comments

@pygy
Copy link
Member

pygy commented Dec 15, 2023

For sets, this does an object identity check for membership, I suppose we could do N^2 deepEqual() checks on the set members to determine if they match... Likewise for maps...

      if (a instanceof Set && b instanceof Set) {
        for (const el of a) {
          if (!b.has(el)) return false
        }
        for (const el of b) {
          if (!a.has(el)) return false
        }
        return true
      }
@dead-claudia
Copy link
Member

dead-claudia commented Jan 10, 2024

You don't need to check both sets. Just assert the size. If sizes are equal and all keys of a are contained in b, you have equal sets.

if (a.size !== b.size) return false
for (const key of a) {
    if (!b.has(key)) return false
}
return true

The proof is relatively straightforward:

  • a can't contain duplicates by definition of a set.
  • b can't contain duplicates by definition of a set.
  • Sets a and b are equal iff they are subsets of each other.
  • If a subsets b, it must have a minimum size of b.size.
  • Suppose b has an element not in a.
    • If a also subsets b, b.size must be greater than a.size.
    • Due to the law of the excluded middle, if b has a.size elements and a subsets b, there cannot exist an element in a not in b.
    • Thus, by definition of a subset, if b has a.size elements and a subsets b, b must subset a.
  • Thus, if a has b.size elements and subsets b, b must subset a. QED.

Edit: the same goes for maps. Proof is similar.

if (a.size !== b.size) return false
for (const [key, value] of a) {
    if (!b.has(key)) return false
    if (!deepEqual(value, b.get(key)) return false
}
return true

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants