Language Design: Comparing and Sorting

Published on 2018-10-31. Last updated on 2022-06-11

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).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 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 trait2 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)) { ... }
  1. See also Comparison in C++

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