On Mar 4, 2020, at 01:56, Mark Dickinson <dickinsm@gmail.com> wrote:

On Wed, Mar 4, 2020 at 9:22 AM Andrew Barnert via Python-ideas <python-ideas@python.org> wrote:
Is there any commonly used or even imaginable useful type that uses them in weirder ways than set and float (which are both partially ordered) [...]

Nitpick: why do you say "partially ordered" for float? If we take NaNs into account, then the float type is neither partially nor totally ordered, since x <= x is False when x is a NaN.

In math, non-strict orders (<=) are usually considered the more fundamental and useful concept, but in programming it’s the other way around: Python’s sort is based on < rather than <=, and the same is true in C++, Haskell, etc. And < (and IEEE lessThan) is a strict partial order: it’s irreflexive, transitive, and antisymmetric. And it’s properly partial, because of NaN values.

So, how can < be a strict partial order when <= is not a non-strict partial order, even though they’re related in the usual way (x<=y iff x<y or x==y)? Because == is not an equivalence relation.

Define any natural equivalence relation on floats (e.g., make each NaN value equal itself), and (x<y or x=y) is a correspondingly natural non-strict partial order (e.g., with all the NaNs as an antichain).

And I’m pretty sure this is all intentional on the part of the IEEE 754 committee and various language designers: if == is not going to be an equivalence relation, you can’t have a natural non-strict partial order—but you can still have a natural strict partial order, and it’s useful, so that’s what they defined. And that’s what languages use to sort numbers (and, usually, everything else—it’s also more naturql to use strict orders to do topological sorts on DAGs, etc.).

If we don't take NaNs into account (which is probably the way we'd want to go from a practicality standpoint), it's both partially and totally ordered. (To David Mertz's earlier comment, "not a total order when you include nans and infs", infinities don't affect the existence of a total or partial order here; it's only the NaNs that we have to worry about.)

You do have to worry about -0 and +0, however, but only very briefly: -0 == 0, not -0 < 0, not 0 < -0, so they aren’t breaking the equivalence or the order. Only NaNs break the equivalence, and therefore the non-strict partial order, and they also turn the strict total order into a strict properly partial order.