Equality Operator

A BooleanOperator? that determines whether two objects are "equal" (have the same state or effective value). A weaker relationship than the IdentityOperator?. Sounds simple enough, but there are lots of cans of worms here:

Deep vs shallow traversal For compound types and objects (those which contain references to other objects), should a deep traversal algorithm (in which all referred-to objects are recursively compared for equality) be used, or a shallow traversal (in which referred-to objects are compared for identity, rather than equality) be used? Shallow traversal is quicker to compute and guaranteed to terminate; but deep traversal might be more appropriate. Unfortunately, if objects that contain cycles are compared using deep traversal, the computation might diverge (unless additional work is done to detect and handle the cycle; making deep traversal even more expensive).

Homogenous vs heterogenous The equality operator is homogenous if both operands are of the same type; for example, comparing two ints. Otherwise, it is heterogenous; e.g., comparing an int with a float (which makes sense; as both ints and floats are subsets of the real numbers); comparing an int with a string (which might make sense if the string is a textual representation of a number); or comparing an int with a ScreenWidget? (which almost never makes sense).

Standard properties of equality. Generally, the equality operator is assumed to be reflexive (a == a), symmetric (a == b -> b == a) and transitive (a == b && b == c -> a == c). Most language-supplied equality operators have these properties; however user-supplied equality operators frequently don't. (Proving that they do is probably equivalent to the HaltingProblem).

:Caution must be taken about the "reflexive" property of equality. In any programming language that follows the IEEE floating-point standard, the special floating-point value "NaN" is not equal to itself. The languages which follow this behavior include, but are not limited to, CeeLanguage, JavaLanguage, OcamlLanguage, HaskellLanguage, PythonLanguage, RubyLanguage, PerlLanguage, and many others.

Many languages (such as CeePlusPlus and JavaLanguage) allow the user to supply custom definitions for the EqualityOperator for user defined types; in which case the above issues are LeftAsAnExerciseForTheReader?. C++ forces you to provide your own, no default is provided. The EqualityOperator in Java defaults to the IdentityOperator?, which is the correct thing to do for ReferenceObjects (not necessarily for ValueObjects).

engineer_scotty (ScottJohnson)


The question of deep vs. shallow traversal begs for a form of LazyEvaluation: returning YesNoMaybe? results. If the shallow traversal proves that the objects are equal, return yes; if the shallow traversal finds a difference (other than sub-object identity), return no; if the shallow traversal finds that there are differences, but only in sub-object identity, return maybe. Perhaps let the caller ask for a clarification on the maybes.


EditText of this page (last edited January 9, 2009) or FindPage with title or text search