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
trait Comparable[T] fun < (that: T): Boolean = ... fun > (that: T): Boolean = ...
… and an IEEE754-conformant 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 stand-in 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 language-wise 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 ...