47

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?

Joshua
  • 40,822
  • 8
  • 72
  • 132
Shailesh Kumar
  • 6,457
  • 8
  • 35
  • 60

2 Answers2

26

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.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
  • I didn't know that the total order predicate is not implemented in hardware. – Shailesh Kumar Oct 21 '14 at 16:06
  • 1
    @ShaileshKumar You can get one total order predicate (I don't know if it is exactly the same as the IEEE 754 one) by first comparing the signs of the values (- < +) and then, if the values are of the same sign, comparing the other bits with an integer comparison instruction on the bits of the representation. – Pascal Cuoq Oct 21 '14 at 16:23
13

It cannot, because of Rust's core design mistake of making Ord a sub-type of PartialOrd.

This means that despite floating point values having a total order, there can only ever be one implementation inside that hierarchy; and that implementation uses the comparison predicate (which is only a partial order), instead of the total-order predicate (which is a total order (and therefore a partial order as well)).

If Ord and PartialOrd were unrelated, it would be trivial to implement both 5.10 and 5.11 from the IEEE754 spec – but because they aren't – Rust has to pick one, and it chose 5.11.

It's easy to imagine a different design in which e. g. Sortable provided 5.10 and Comparable provided 5.11, with types implementing both as appropriate.

Then, a user could write Sortable if she needed the total order, and Comparable if she needs the partial order.

soc
  • 27,983
  • 20
  • 111
  • 215