3
$\begingroup$

The comparative relationship between objects is very complicated, there are all comparable, partial comparison, all equal, partial equal situations.

A total of twelve functions are needed. The return value types of these functions are as shown in the following table:

Sign Partial Total
Option<bool> bool | !
> Option<bool> bool | !
= Option<bool> bool | !
Option<bool> bool | !
< Option<bool> bool | !
Option<bool> bool | !
  • ! means panic in runtime call

But many of them can generate each other, such as = can generate , > can generate <, can generate . ​

Question

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

Consistency means to prevent accidental implementation errors, such as

  • making always false and = always true.
  • type A = type B always false, type B = type A always true.

For example, = and can be derived from each other, then if I support Negative Trait, I can prohibit implement of both to ensure consistency.

$\endgroup$
7
  • 3
    $\begingroup$ What does your notion of "partial comparison" (and "partial equal") mean? A partial order doesn't make comparisons three-valued, it just adds a fourth relationship one value can have to another--"incomparable" meaning "neither greater, less, nor equal", not that none of those three are "even false". $\endgroup$ Commented Feb 28 at 4:01
  • 4
    $\begingroup$ I'm kind of confused by the fact that, except for the far left column, each column has the same text going downwards. Can you expand on what those mean? $\endgroup$ Commented Feb 28 at 4:08
  • 1
    $\begingroup$ What exactly are you asking here? Which minimal set of comparisons is needed to generate all comparisons, like python's total ordering? Given all comparisons how to enforce/validate the results are consistent? Given that there are different orders, how to encode the different constraints/freedoms of each? $\endgroup$ Commented Feb 28 at 6:54
  • 3
    $\begingroup$ The minimum interface would be one method taking two arguments, returning either "less", "equal" or "more" (or "uncomparable" if you allow that). That's patently minimal because the interface for comparing two things can't be smaller than one method with two arguments. But this interface does exist in plenty of languages, e.g. Java and JavaScript use a negative, zero or positive return value for the three cases. $\endgroup$
    – kaya3
    Commented Feb 28 at 10:54
  • 3
    $\begingroup$ Maybe this question conflates implementing a partial order, with seeing the comparison function as a partial function (modeled as returning Option)? I mean, in addition to the problem of using bool instead of a three-valued {less,greater,equal} result for the comparison function. $\endgroup$ Commented Feb 28 at 11:13

5 Answers 5

5
$\begingroup$

There are a number of approaches, depending on the intended use cases and priorities of a language.

One way to think about this is that these are all just derivatives of a single compare method.

For example (in a Rust-like pseudo code):

enum Comparison = Lesser | Equal | Greater | Incomparable

trait Comparable {
    compare: (Self, Self) -> Comparison
}

... which can fill out the different operators like so:

a < b  <==>  compare(a, b) is Lesser
a > b  <==>  compare(a, b) is Greater
a = b  <==>  compare(a, b) is Equal
a ⩾ b  <==>  compare(a, b) is one of Greater | Equal
a ⩽ b  <==>  compare(a, b) is one of Lesser | Equal
a ≠ b  <==>  compare(a, b) is one of Lesser | Greater | Incomparable

This is consistent as long as compare is implemented correctly, because they all derive from a single method.

This handles both partially ordered types and totally ordered types, totally ordered types simply never returning Incomparable from compare (although you might want to be able to specify totally ordered types, to allow users to make use of properties like "exactly one of these statements: a < b, a ⩾ b is true").

You can even use it to implement equality checking for non-ordered type (by only returning Equal or Incomparable from compare -- although, again, it might make sense to separate that out too).


I don't believe comparison functions generally return None or raise an error if a and b are of the right type but are simply incomparable. That is because < and friends are mathematically not functions but relations, which are generally implemented in programming language as: for any relation $R$, the implementation function $f_R$ is defined such that $f_R(x, y)$ returns true if $xRy$ holds, otherwise it returns false.

$\endgroup$
5
  • $\begingroup$ In this case, are total ordering and total equal considered an author's guarantee? That is, a Marker Trait that does not actually need to be implemented? $\endgroup$
    – Aster
    Commented Feb 28 at 17:23
  • $\begingroup$ They could be, but depending on how the language works exactly, you could for example guarantee a total ordering by statically checking that totally ordered types always return the subtype Lesser | Equal | Greater. If that's a property you want your language to have it might be simpler to look at a language like Rust, which has partial_cmp returning Option<Ordering> and cmp returning Ordering separately, [...] $\endgroup$
    – Jasmijn
    Commented Feb 28 at 20:15
  • $\begingroup$ [...] as well as eq returning bool. (Note how Eq is a marker trait built on PartialEq, requiring no extra code, but only an author's guarantee that a == a.) $\endgroup$
    – Jasmijn
    Commented Feb 28 at 20:15
  • $\begingroup$ The problem is, this ignores the commutative properties of comparison -- the required realtionship between compare(a, b) and compare(b, a). It also ignores transitivity (eq, compare(a,b) is Equal and compare(b,c) is Equal -> compare(a,c) is Equal) So one can define a compare operation that meets these requirements, but is nonsensical. $\endgroup$
    – Chris Dodd
    Commented Mar 4 at 23:23
  • $\begingroup$ Yes that is a common trade-off. The only two ways I can think of off the top of my head are to require the programmer to write a formal proof of all the relevant axioms, or to instead map all values that need a Comparable implementation to other types that are known to have Comparable implementation that satisfies the right axioms. I don't know if the latter is always possible, so then it might be necessary to include an escape hatch with your custom implementation. That would be quite similar to Rust, where you can often derive implementations of these traits. $\endgroup$
    – Jasmijn
    Commented Mar 5 at 11:17
5
$\begingroup$

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).
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Does this work for partial orders where both a < b and b > a may be false without a == b being true? What would CompareTo return in this case? $\endgroup$ Commented Feb 28 at 11:09
  • $\begingroup$ For partially ordered types, an equivalent to CompareTo would have to have four possible return values, see my answer for one possible example. At any rate, you can't use the simple rule that a$R$b$\iff$a.CompareTo(b)$R\,0$ when it comes to partially ordered types. $\endgroup$
    – Jasmijn
    Commented Feb 28 at 12:42
  • $\begingroup$ In Kotlin, the comparison operators are indeed overridden by compareTo $\endgroup$
    – Seggan
    Commented Feb 28 at 16:08
  • $\begingroup$ @MisterMiyagi: IComparable is for implementing total orders; it's for sorting a list of stuff. If you've got some exotic scenario where you're topologically sorting a lattice or some such, that's not the mechanism for you. $\endgroup$ Commented Feb 29 at 1:33
1
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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 for two reasons: It makes it easier to understand which metamethods are called and why, and it is potentially slightly better for performance.
  • == 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).

$\endgroup$
2
  • $\begingroup$ "a > b and a >= b are just syntactic sugar for a < b and a <= b respectively as well." ─ this seems like an editing error, but I'm not sure if you mean b < a and b <= a (but presumably with a is still evaluated before b), or not (a <= b) and not (a < b) respectively. $\endgroup$
    – kaya3
    Commented Mar 15 at 2:37
  • $\begingroup$ @kaya3 Thanks for pointing that out, I mean b < a and b <= a, edited. Whether a is evaluated before b is to my knowledge not defined, see lua-users.org/lists/lua-l/2006-06/msg00378.html. $\endgroup$
    – Luatic
    Commented Mar 15 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .