DeepEquals should handle Sets (and Maps)

[pygy]

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]

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