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 IEEE754-conformant 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).¹

The reason is that the implementation of comparison operations for floating point values (a partial order, IEEE754 §5.11) cannot be used as a stand-in 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 language-wise is to introduce a distinct trait² 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)) { ... }
  ...