Then, we can do O(N^2) comparisons by recursively comparing everything randomly, which is incredibly inefficient.As long as we force and ensure recursive set equality is indeed transitive and reflexive and symmetric, we can make sure nothing horribly wrong happens.even the strict equality = operator in ecmascriptĭoes not obey these properties, because the strict equality comparison algorithm of ecmascript has NaN!=NaN this is why many native datatypes like Set and Map 'equate' NaNs to consider them the same values when they appear as keys.the equality = operator obviously does not obey many of these properties.trying to get recursive equality to work is kind of meaningless if the recursive notion of equality you use is not 1) reflexive (a=b implies b=a) and 2) symmetric (a=a) and 3) transitive (a=b and b=c implies a=c) this is the definition of an equivalence class.set A =? set B being synonymous with B.has(k) for every k in A implicitly uses =-equality ( !=), not recursive equality ( deepEquals(,) = true), so two new Set(]) would not be equal because we don't recurse.Set equality is the tree isomorphism problem but a bit simpler.To summarize the complexity of recursive equality on Sets: This is not an issue usually with most Sets of homogenous datatype. You'd also maybe get weird (but potentially not that weird) edge cases with and Truthy values (with the exception that NaN=NaN. Certainly one could do the O(N^2) performance thing and remove pairs of = items one by one like a bubble sort, and then do a second O(N^2) pass to confirm things in equivalence classes are actually = to each other, and also != to everything not thus paired, but you'd STILL have to throw a runtime error if you have some coercion going on. However if one uses a non-transitive notion of equality like =, you open a can of worms: Even if you forced the user to define a hash function on the domain (hash(a)!=hash(b) implies a!=b) I'm not sure that would help. If one is using the built-in notion of Set equality (that is, =), then the above should work. This is relevant for Sets: I do not think one can override the notion of Set equality in a meaningful way. Note that if one is using the = notion of equality, then know that falsey values and coercion means that = equality is NOT TRANSITIVE. Easiest option, works in almost all cases, except that null!= undefined but they both are converted to JSON representation null and considered equal: function arraysEqual(a1,a2), new Map(,]), nineTen],
0 kommentar(er)
