sortingrustfloating-pointpartial-ordering

Why does Rust not implement total ordering via the Ord trait for f64 and f32?

While all the integer types in Rust implement Ord which emphasizes total ordering, the floating point types only implement PartialOrd. This means that there could be floating point values which cannot be compared. This seems difficult to digest since floating point numbers can be thought of as approximations to real numbers which happen to be a totally ordered set. Even the addition of positive and negative infinity keeps the set of real numbers totally ordered. Why this odd choice in Rust?

This restriction means that a generic sort/search algorithm can only assume partial ordering on numbers. The IEEE 754 standard seems to provide for a total ordering predicate.

Are NaN's so much of a problem in generic code?

Solution

  • What is your question, precisely? Are you asking whether NaN exists, or whether it can be obtained as the result of accidental or voluntary computations? Yes, it does and it can. The sort of data structure that requires a total order for keys breaks down completely when the provided order is not a total order. You do not want even one exceptional value be different from itself, because it would break invariants of the structure and mean that anything can happen henceforth. NaN is not something that should be assumed to be innocuous as long as no problem has been shown, although that has been tried in other languages.

    IEEE 754's definition of the ordinary comparison operators <, <=, … makes them very useful in general—if not when you need a total order. In particular, it is easy to write conditions so that NaN inputs will be sent to the error branch:

    if (!(x <= MAX)) { // NaN makes this condition true
  error();
}

if (!(x >= MIN)) { // NaN makes this condition true
  error();
}

    Because < and <= are so useful, they are the operations implemented as single, fast instructions in modern processors—the totalOrder predicate from IEEE 754 is typically not implemented in hardware. Programming languages map the fast instructions to constructs in the language and leave anyone who exceptionally needs totalOrder to pick it from a library or even to define it themselves.