Language Design: Comparing and Sorting

Published on 2018-10-31.

Similarly to equality and identity, most languages have severely restricted facilities to handle distinct ordering relationships like comparisons and sorting.

Languages usually provide only a single comparison operation/protocol, often requiring workarounds for some data types in which comparing and sorting operations return different results.

Consider the following Comparable trait:

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

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