Comparisons of incompatible types

[Mark Wooding]

John Nagle <nagle at animats.com> writes:

> >>> NaN = float("nan")
> >>> arr = [1.0, 4.0, 3.0, 2.0, 5.0, NaN, 6.0, 3.0, NaN, 0.0, 1.0, 4.0, 
> 3.0, 2.0, 5.0, NaN, 6.0, 3.0, NaN, 0.0]
> >>> sorted(arr)
> [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 3.0, 3.0, 4.0, 5.0, nan, 5.0, 6.0,
> nan, 4.0, nan, 6.0, nan]
>
> The sorted numerical values aren't in order. 

Indeed.  You failed to provide a valid ordering to `sorted'.  By failing
to satisfy its precondition, you relieved it of its obligation to
satisfy its postcondition.

> "sort" has failed because it assumes that a < b and b < c implies a <
> c. But that's not a valid assumption here.
>
> It's not good to break trichotomy.

You're confused.  The property

        a < b and b < c => a < c

is called `transitivity'.  But the `float' ordering /is/ transitive.
Note that a < b implies that neither a nor b is a NaN.

Also, trichotomy is unnecessary for sorting, and Python's `sort' method
doesn't require it; it does require a total preorder, though.  What
properties does a total preorder require?

  1. Transitivity: a <= b and b <= c => a <= c

  2. Totality: a <= b or b <= a

The above list sorting goes wrong because the `float' ordering isn't
total.  In particular, x </= NaN and NaN </= x for all x (including x =
NaN!).

So, your last remark is in the right direction (though strict trichotomy
is unnecessary, as I've mentioned), but apparently only by accident
since the preceding discussion is completely wrong.

-- [mdw]