Language Design: Comparing and Sorting
Similarly to equality and identity, most languages have severely restricted facilities to handle distinct ordering relationships like comparison and sorting.
Languages usually provide only a single operation/protocol, often requiring workarounds for some data types in which the comparison operation and the sorting operation return distinct results.
Consider the following Comparable
trait:
trait Comparable[T]
fun < (that: T): Boolean = ...
fun > (that: T): Boolean = ...
… and an IEEE754conformant implementation of Comparable
for floating point values, such that 0.0 < +0.0
, and Float.NaN < Float.PositiveInfinity
are both false.
As it becomes obvious, such an implementation of partial order used to correctly compare values, cannot be used to correctly sort values (total order).^{1}
Worded differently, an implementation of comparison operations for floating point values cannot be used as a standin for sorting operations on floating point values.^{2}
Conveniently, IEEE754 standardizes a totalOrder
relation in §5.10, defining how floating point numbers should be sorted.
The only requirement languagewise is to introduce a distinct trait which represents total ordering, enabling a clean separation of comparisons and sorting operations:
trait Sortable[T]
fun sortsBefore(that: T): Boolean = ...
fun sortsAfter (that: T): Boolean = ...
This enables the use of each individual trait for its specific purpose, without conflating different concerns:
// compare values using Comparable
fun compareReversed[T : Comparable](x: T, y: T) = y < x
// sort values using Sortable
fun sort[T : Sortable](values: Array[T]) =
...
x sortsBefore y
...

See also Comparison in C++. ↩

Rust is a good example of a language suffering from the problems caused by intermingling partial order with total order. ↩