Why can't I use `min_by_key` and friends with `PartialOrd`?

1

They’re still guaranteed to find a minimal or maximal element even if it isn’t a total order, right?

2

I don’t think so. The minimum or maximum of a poset are not uniquely defined.

3

You can say which is smaller of “Banana” and “Grape”, and which is smaller (by wavelength) of “Red” and “Purple”… but which is smaller of “Banana” and “Purple”?

4

It can still be useful to get any one of those minima.

5
  • f64::NAN < 0.0 is false
  • 0.0 < f64::NAN is false

Which should min_by_key return?

5 Likes
6

I want min to be equivalent to the following.

fn min<I: Iterator>(mut iter: I) -> Option<I::Item> where I::Item: PartialOrd {
    iter.next().map(|first| iter.fold(first, |current, other| if other < current { other } else { current }))
}

That’s guaranteed to return a minimal element. It’s not necessarily the first one, though. So I guess in your example the list [NAN, 0] would give NAN, but [0, NAN] would give 0.

7

That depends on your definitions. If you say a minimal element is an x such that x <= a[i] for all valid i -- which I think is a perfectly intuitive definition -- then NAN is not a minimal element, and in fact there is no minimal element if the sequence contains NAN.

3 Likes
8

In a partially-ordered set, all elements need not be comparable. In other words, for two elements a and b, it may be the case that none of a < b, a = b or a > b hold. In IEEE floating point, NaN is such an incomparable value (i.e., comparison to anything, even another NaN, is meaningless).

1 Like
9

That depends on your definitions.

Is there a reason not to use this definition (the common one in maths)?

10

For example because not even Wikipedia gets to use it consistently. In the article you linked, “minimum” and “minimal element” are treated as different; meanwhile, on the page about posets, these elements are referred to as “least element” and “minima”, and the elements called minima here aren’t unique (there can be 0, 1, or more of them).

I would say that if even the very same medium isn’t sure which concept bears which name, maybe totally different people using Rust wouldn’t agree either, so this has a decent amount of potential for causing confusion.

A different pair of methods with clearer names could help, though; for example something verbose like element_not_greater_than_any_other (this is just a strawman name, as it is obviously too long, but you get the idea.)

2 Likes
11

partial_min_by_key would fit partial_cmp & co.

2 Likes
12

Good point, “minimum” is vague, but “minimal element” always refers to “an element that is not more than any element” and “least element” always refers to “an element that is less than or equal to every element”.

13

But none of “minimum” or “minimal element” or “least element” apply to the NaNs of IEEE floating point, which by definition cannot be compared. If posets can contain such elements, per the Wikipedia definition, then some term like @kornel’s partial_min_by_key will necessarily be required.

1 Like
14

That’s actually a great idea.

15

You'll notice that's not "maximum". What I mentioned is Greatest element and least element - Wikipedia, which explicitly mentions

In a totally ordered set both terms coincide; it is also called maximum

So both definitions exist in math; I just prefer the one with what I consider the more useful postcondition.

1 Like
16

There are probably use cases for getting a minimal element from a collection of PartialOrd but you should have to opt-in to that behavior by using a different function. It seems likely to me that if the standard functions tried to “help” you in this situation it would more often lead to bugs discovered down the road than the desired behavior. It probably also means the implementation of min can be more efficient because it doesn’t need to consider the case of incomparable elements.

3 Likes
17

The commonly accepted definition of a (mathematical) partial order requires the (non-strict) order relation to be reflexive, which explicitly doesn’t hold for NaNs. Thus, you may even argue that terms like ‘least element’ and ‘minimal element’ are meaningless for the IEEE 754 ‘partial order’, because they presuppose conditions which don’t hold for the ‘ordering’ relation. If we overlook that technicality though, a NaN could be straightforwardly considered a minimal element, because it is true that ¬∃ x: (x ≤ NaN ∧ x ≠ NaN). No floating-point value is the least, though.

That said, given that in a general partial order multiple minimal elements may exist in a given collection, a ‘minimal element’ function would have to make some arbitrary choice among them (e.g. always return the leftmost on the argument list/first returned by an iterator). I’d be wary of code that would subtly rely on a particular choice of minimal element, even though some applications may not mind this nondeterminism.

4 Likes
18

I find that using IEEE floats as an example of a partially ordered set isn’t very compelling. In Haskell, the Ord typeclass is implemented by Float. The documentation mentions two caveats:

Ignoring NaN as an edge case seems plausible.

Semilattices make for much better examples of posets. Consider dictionary words ordered using the prefix relation. While the minimum of [“the”, “these”, “they”] is “the”, what is the maximum?

2 Likes
19

Personally, I find it extremely compelling. Porting a simulator from D to Rust caught several bugs specifically because Rust doesn't implement Ord on floats.

6 Likes
20

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.