Exhaustive Map comparison using higher-order functions
I'm going to approach this the same way I approached array comparison in this similar answer: How to compare arrays in JavaScript?
I'm going to go thru the code bit-by-bit, but I'll have a complete runnable example at the end
Shallow comparison
First off, we're going to start with a generic Map comparison function. This way we can do all sorts of comparisons on Map objects, not just testing for equality
This mapCompare function agrees with our intuition about how Maps should be compared - we compare each key from m1 against each key from m2. Note, this specific comparator is doing shallow comparison. We'll handle deep comparison in just a moment
const mapCompare = f => (m1, m2) => {
const aux = (it, m2) => {
let {value, done} = it.next()
if (done) return true
let [k, v] = value
return f (v, m2.get(k), $=> aux(it, m2))
}
return aux(m1.entries(), m2) && aux(m2.entries(), m1)
}
The only thing that might not be immediately clear is the $=> aux(it, m2) thunk. Maps have a built-in generator, .entries(), and we can take advantage of the lazy evaluation by returning an early false answer as soon as non-matching key/value pair is found. That means we have to write our comparators in a slightly special way.
const shortCircuitEqualComparator = (a, b, k) =>
a === b ? true && k() : false
a and b are values of m1.get(somekey) and m2.get(somekey) respectively. iff the two values are strictly equal (===), only then do we want to continue the comparison – in this case we return true && k() where k() is the remainder of the key/value pair comparison. On the other hand, if a and b do not match, we can return an early false and skip comparing the rest of the values – ie, we already know that m1 and m2 do not match if any a/b pair do not match.
Finally, we can define mapEqual - it's simple too. It's just mapCompare using our special shortCircuitEqualComparator
const mapEqual = mapCompare (shortCircuitEqualComparator)
Let's take a quick look at how this works
// define two maps that are equal but have keys in different order
const a = new Map([['b', 2], ['a', 1]])
const b = new Map([['a', 1], ['b', 2]])
// define a third map that is not equal
const c = new Map([['a', 3], ['b', 2]])
// verify results
// a === b should be true
// b === a should be true
console.log('true', mapEqual(a, b)) // true true
console.log('true', mapEqual(b, a)) // true true
// a === c should be false
// c === a should be false too
console.log('false', mapEqual(a, c)) // false false
console.log('false', mapEqual(c, a)) // false false
Heck yes. Things are looking good ...
Deep comparisons with Rick & Morty
Now that we have a fricken sweet mapCompare generic, deep comparison is a breeze. Take notice that we're actually implementing mapDeepCompare using mapCompare itself.
We use a custom comparator that simply checks if a and b are both Map objects – if so, we recurse using mapDeepCompare on the nested Maps; also being mindful to call ... && k() to ensure the remaining key/value pairs are compared. If, a or b is a non-Map object, normal comparison is doing using f and we pass the continuation k along directly
const mapDeepCompare = f => mapCompare ((a, b, k) => {
console.log(a, b)
if (a instanceof Map && b instanceof Map)
return mapDeepCompare (f) (a,b) ? true && k() : false
else
return f(a,b,k)
})
Now with mapDeepCompare, we can perform any type of deep comparison on nested Maps. Remember, equality is just one of the things we can be checking.
Without further ado, mapDeepEqual. Of importance, we get to reuse our shortCircuitEqualComparator that we defined before. This very clearly demonstrates that our comparators can be (re)used for shallow or deep Map comparisons.
const mapDeepEqual = mapDeepCompare (shortCircuitEqualComparator)
Let's see it work
// define two nested maps that are equal but have different key order
const e = new Map([
['a', 1],
['b', new Map([['c', 2]])]
])
const f = new Map([
['b', new Map([['c', 2]])],
['a', 1]
])
// define a third nested map that is not equal
const g = new Map([
['b', new Map([
['c', 3]
])],
['a', 1]
])
// e === f should be true
// f === e should also be true
console.log('true', mapDeepEqual(e, f)) // true
console.log('true', mapDeepEqual(f, e)) // true
// e === g should be false
// g === e should also be false
console.log('false', mapDeepEqual(e, g)) // false
console.log('false', mapDeepEqual(g, e)) // false
OK, and just to make sure. What happens if we call mapEqual on our nested Maps e and f? Since mapEqual does shallow comparison, we expect that the result should be false
console.log('false', mapEqual(e, f)) // false
console.log('false', mapEqual(f, e)) // false
And there you have it. Shallow and deep comparison of ES6 Map objects. A nearly identical set of functions could be written to support ES6 Set. I'll leave this as an exercise for the readers.
Runnable code demo
This is all of the code above compiled into a single runnable demo. Each console.log call outputs <expected>, <actual>. So true, true or false, false would be a passing test – whereas true, false would be a failed test.
// mapCompare :: ((a, a, (* -> Bool)) -> Bool) -> (Map(k:a), Map(k:a)) -> Bool
const mapCompare = f => (m1, m2) => {
const aux = (it, m2) => {
let {value, done} = it.next()
if (done) return true
let [k, v] = value
return f (v, m2.get(k), $=> aux(it, m2))
}
return aux(m1.entries(), m2) && aux(m2.entries(), m1)
}
// mapDeepCompare :: ((a, a, (* -> Bool)) -> Bool) -> (Map(k:a), Map(k:a)) -> Bool
const mapDeepCompare = f => mapCompare ((a, b, k) => {
if (a instanceof Map && b instanceof Map)
return mapDeepCompare (f) (a,b) ? true && k() : false
else
return f(a,b,k)
})
// shortCircuitEqualComparator :: (a, a, (* -> Bool)) -> Bool
const shortCircuitEqualComparator = (a, b, k) =>
a === b ? true && k() : false
// mapEqual :: (Map(k:a), Map(k:a)) -> Bool
const mapEqual = mapCompare (shortCircuitEqualComparator)
// mapDeepEqual :: (Map(k:a), Map(k:a)) -> Bool
const mapDeepEqual = mapDeepCompare (shortCircuitEqualComparator)
// fixtures
const a = new Map([['b', 2], ['a', 1]])
const b = new Map([['a', 1], ['b', 2]])
const c = new Map([['a', 3], ['b', 2]])
const d = new Map([['a', 1], ['c', 2]])
const e = new Map([['a', 1], ['b', new Map([['c', 2]])]])
const f = new Map([['b', new Map([['c', 2]])], ['a', 1]])
const g = new Map([['b', new Map([['c', 3]])], ['a', 1]])
// shallow comparison of two equal maps
console.log('true', mapEqual(a, b))
console.log('true', mapEqual(b, a))
// shallow comparison of two non-equal maps (differing values)
console.log('false', mapEqual(a, c))
console.log('false', mapEqual(c, a))
// shallow comparison of two other non-equal maps (differing keys)
console.log('false', mapEqual(a, d))
console.log('false', mapEqual(d, a))
// deep comparison of two equal nested maps
console.log('true', mapDeepEqual(e, f))
console.log('true', mapDeepEqual(f, e))
// deep comparison of two non-equal nested maps
console.log('false', mapDeepEqual(e, g))
console.log('false', mapDeepEqual(g, e))
// shallow comparison of two equal nested maps
console.log('false', mapEqual(e, f))
console.log('false', mapEqual(f, e))
