How to define comparators and maintain consistency?

One solution to this problem is C++'s operator<=> (a.k.a spaceship oerator).

There is a detailed description in the P0515 proposal, and shorter descriptions in cppreeference and this C++faq answer (section on Default Comparisons (C++20)).

The topic is somewhat complex in its details [it's C++ ;-)], but on the surface:

• you define an operator<=>(sometype y) in-class, or two-parameter stand-alone, possibly friend;
• its return type (std::strong_ordering, std::weak_ordering, or std::partial_ordering) is used by the compiler to decide which other comparison operators to generate automatically;
• operator<=>() can be defaulted, then the compiler will generate it automatically (e.g. by memberwise comparison).

This is a peeve of mine. In C# for example, in order to implement a new type that has equality and inequality operators you end up having to override the ==, !=, <, >, <=, >= operators, and override the Equals method, and implement IComparable<T>, and get the hashing logic right. It's a lot.

We could make it a lot easier. It would be nice that if you said:

class X : IComparable<X> { public int CompareTo(X other) { // return 0, 1 or -1 depending on comparison } 

that the compiler would pretend that you had also written all the boilerplate:

 public static bool operator <(X a, X b) => a.CompareTo(b) < 0; public static bool operator >(X a, X b) => a.CompareTo(b) > 0; ... and so on ... 

It's not hard boilerplate to write, but it would be nice if you didn't have to.

However this sort of feature is very low priority because it doesn't add new representational power or solve a major pain point. It's low bang for buck, so I wouldn't expect this sort of thing soon in C#. If you're designing a new language though, go for it.

TL;DR: What, not How.

There is one further important relationship: that of hashing and equality. You really want the hash operation and the equal operation to operate on the same set of fields.

While a single compare method, returning a (potentially partial) order can help with all the comparison operators, it does not solve the problem of having a hash operation consistent with the equal operation.

The simplest way to achieve consistency, thus, is to have the users specify the fields that participate in the equality/ordering, instead of how to hash or compare.

Note that unlike hashing, however, a simple visitation method is not quite suitable for comparison, and instead you'd want a method which returns an iterator over the fields, so the framework can ask for the first field to compare of each type, then the second field, etc...

Let's have an example in Python:

class User: def __init__(self, name: String, age: int): self.__name = name self.__age = age def id(self) -> Iterator[Any]: yield self.__name yield self.__age def hash(object: Any, hasher: Any) -> int: """Computes the hash of `object` as per the `hasher` incremental algorithm.""" # User override hash_override = getattribute(object, '__hash__', None) if callable(hash_override): hash_override(object, hasher) else: for field in object.id(): hash(field, hasher) return hasher.finalize() def compare(left: Any, right: Any) -> int: """Returns 0 for equal, -1 for left < right, +1 for left > right.""" # User override comparator = getattribute(left, '__cmp__', None) if callable(comparator): return comparator(left, right) for left_field, right_field in zip_longest(left.ids(), right.ids()): result = compare(left_field, right_field) if result == 0: continue return result return 0 

It should generally be possible to implement the scheme in a static language, though how to will depend on the capabilities of said language:

• In Java, one would use Object as the central key of the scheme.
• In Rust, one would create an associated type representing the sequence of fields to iterate through.

Many examples of more complicated "comparables" or "comparators", often in statically typed languages, have been given, so let's take a look at languages that aim to be simple.

First, comparators should not be tied to objects. I want to be able to sort the same people both by age and name. Thus, we need some kind of "comparator" interface. You asked

How to define the minimum interface and ensure that there is no conflict?

The simplest way is to just require a function(a, b T) bool, a "less than" function, as a comparator. This function should return true if and only if a < b. This is what Lua's and Go's sort functions do.

Now developers just need to implement one function correctly. The rest follows from the definition of "less than":

• If a < b, then a is less than b.
• If b < a, then a is greater than b.
• Otherwise, a and b must be equal (assuming a total order)

Want to sort by age? Simply pass function(a, b) return a.age < b.age end.

The advantage of this approach is that it's about as simple as can be - no "spaceship" operator, no need for an "enum" - or worse, signed number, which invites using arithmetic, which runs the risk of overflows - return type, no need for a "comparator" interface/trait, just a simple boolean function.

Worth mentioning here: Python functions that require an ordering let you pass a key function (rather than a comparator). This is often slightly more convenient and reduces the potential for mistakes - often you just want to sort by a property (perhaps one that you haven't calculated yet), or a bunch of properties (in which case you can pack them up in a tuple).

There are downsides to this approach, though. For one it can be slightly less efficient due to having to make (up to) two calls (but only 1.5 on average, assuming < and > appear equally often and == is rare) calls to the "comparator" rather than a single call. It also assumes a total order, usually. I find that this is not a major limitation, though. The most common applications where orders are needed require a total order. Floats may technically have NaN, but nobody would expect sorting a list with NaNs in it to produce a sensible result; the NaNs ending up in the list would be considered a bug, and it is welcomed if sorting throws an error.

Now, Lua also has "metamethods" to redefine the behavior of the comparison operators for tables. Some things Lua did right here:

• There are no separate metamethods for ~=, > or >=. a ~= b is just syntactic sugar for not (a == b). It does not let programmers redefine ~= to potentially be inconsistent with ==. a > b and a >= b are just syntactic sugar for b < a and b <= a respectively as well.
• == is special: If objects are "primitively equal" (equal by reference), they are always equal and the metamethod is not called. This also makes sense (and saves the programmer from writing the if rawequal(a, b) then return true end optimization boilerplate themselves). One thing that is debatable is that Lua only calls the metamethod if both operands are tables (/ full userdata) - that is, if you implement a custom number type (say bigints), you can't implement comparisons against primitive numbers (this is relevant to performance, however: Checks can be more efficient if there is no need to check the metatable; this does not apply to <, because a "raw" table < primitive is of course an error, whereas a "raw" table == primitive is just false). It is also inconsistent with hashing, as there is no way to provide a custom "hash" metamethod.
• This leaves us with < and <= metamethods. Older Lua versions would "emulate" a <= b using not (a < b) if it was missing, automatically ensuring consistency, newer Lua versions (5.4+) don't, probably because it makes it easier to understand which metamethods are called and why.
• == could be emulated with < or <= in principle. But this is not a good idea for performance. == can often be faster than < or <= - for example all (only "short" ones in newer versions) strings in Lua are interned, so string comparison for equality is O(1), whereas lexicographic comparison can very well be O(n).

Another interesting case is Haskell. If you look at Haskell's Ord typeclass, it gives you a "best of both worlds": Either <= or compare are enough for a "minimal complete definition" such that the compiler fills out the rest.

To recap: A single < or <= function in principle suffices to "emulate" all other comparison methods (for a total order). There are tradeoffs, which is why you might want to allow for multiple, technically "redundant" implementations for some of these methods. A "spaceship"-style operator can efficiently unify the comparison operations, but is not as simple as can be.

Some languages have facilities to autogenerate these (like #derive in Rust) or implementations which let you order by (computed) "key" (like Python).

All comparisons can be defined in terms of ≤ alone:

• a ≥ b means b ≤ a

• a = b means a ≤ b ∧ b ≤ a

• a ≠ b means ¬(a = b)

• a < b means a ≤ b ∧ ¬(b ≤ a)

• a > b means b < a

Thus, you can check whether these conditions are satisfied.

In mathematical terminology:

• ≤ is a preorder, that is, a reflexive and transitive binary relation

• = is its symmetric part, which is an equivalence relation

• < is its asymmetric part, which is a strict preorder