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 as it frequently exists across many languages
(like Haskell,
Rust,
Swift, …):
trait Comparable[T]
fun < (that: T): Bool
fun > (that: T): Bool
...
… and an IEEE754conformant comparison implementation for floating point values,
i. e. 0.0 < +0.0
, and Float.NaN < Float.PositiveInfinity
are both false.
As it becomes obvious, such an implementation of partial order can be used to compare values, but cannot be used to correctly sort values (total order).^{1}
The reason is that the implementation of comparison operations for floating point values (a partial order, IEEE754 §5.11) cannot be used as a standin for sorting operations on floating point values.
Conveniently, IEEE754 standardizes a totalOrder
relation in §5.10, defining how floating point numbers are sorted.
The only requirement languagewise is to introduce a distinct trait^{2} which represents total ordering,
enabling a clean separation of comparison operations from sorting operations:
trait Sortable[T]
fun sortsBefore(that: T): Bool
fun sortsAfter (that: T): Bool
...
This enables the use of each individual trait for its specific purpose, without conflating different concerns:
// example of comparing values using Comparable
fun compareReversed[T : Comparable](x: T, y: T) = y < x
// example of sorting values using Sortable
fun sort[T : Sortable](values: Array[T]) =
...
if values(i).sortsBefore(values(j)) { ... }
...

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. ↩