Three-way comparison

In computer science, a three-way comparison takes two values A and B belonging to a type with a total order and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical law of trichotomy.

Machine-level computation

Many processors have instruction sets that support such an operation on primitive types. Some machines have signed integers based on a sign-and-magnitude or one's complement representation (see signed number representations), both of which allow a differentiated positive and negative zero. This does not violate trichotomy as long as we adopt a consistent total order: either -0 = +0 or -0 < +0 is valid. Common floating point types, however, have an exception to trichotomy: there is a special value "NaN" (Not a Number) such that "x" < NaN, "x" > NaN, and "x" = NaN are all false for all floating-point values "x" (including NaN itself).

High-level languages

In Perl, Ruby, and Groovy, the spaceship operator ("<=>") returns the sign function (a.k.a. signum) values of -1, 0, or 1 depending on whether A < B, A = B, or A > B, respectively. In Python, the cmp function computes the same thing. Since Java version 1.5, the same can be computed using the Math.signum static method if the difference can be known without computational problems such as arithmetic overflow mentioned below. Many computer languages allow the definition of functions so a "compare(A,B)" could be devised appropriately, but the question is whether or not its internal definition can employ some sort of three-way syntax or else must fall back on repeated tests.

When implementing a three-way comparison where a three-way comparison operator or method is not already available, it is common to combine two comparisons, such as A = B and A < B, or A < B and A > B. A compiler may be able to optimize these two comparisons into a single three-way comparison at a lower level, but this is not a common optimization.

In some cases, three-way comparison can be simulated by subtracting A and B and examining the sign of the result, exploiting special instructions for examining the sign of a number. However, this requires the type of A and B to have a well-defined difference. Fixed-width signed integers may overflow when they are subtracted, floating-point numbers have the value NaN with undefined sign, and character strings have no difference function corresponding to their total order. At the machine level, overflow is typically tracked and can be used to determine order after subtraction, but this information is not usually available to higher-level languages.

In one case of a three-way conditional provided by the programming language, Fortran's now-deprecated three-way arithmetic IF statement considers the sign of an arithmetic expression and offers three labels to jump to according to the sign of the result:

IF (expression) negative,zero,positive

Composite data types

Three-way comparisons have the elegant property of being simple to compose to build lexicographic comparisons of non-primitive data types, unlike two-way comparisons. This is used in the Haskell standard library where the three-way comparison function compare is defined for all types in the Ord class.

Here is a composition example in Perl. sub compare($$) { my ($a, $b) = @_; return $a->{unit} cmp $b->{unit}
| $a->{rank} <=> $b->{rank}
| $a->{name} cmp $b->{name}; }Note that cmp is for strings as <=> is for numbers and that || is lazy. Two-way equivalents tend to be less compact but not necessarily less legible.