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

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

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

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”?

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

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

Which should `min_by_key` return?

5 Likes

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`.

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

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

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

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

`partial_min_by_key` would fit `partial_cmp` & co.

2 Likes

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”.

But none of “minimum” or “minimal element” or “least element” apply to the `NaN`s 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

That’s actually a great idea.

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

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

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

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:

• Note that due to the presence of `NaN` , `Float` 's `Ord` instance does not satisfy reflexivity.
• Also note that, due to the same, `Ord` 's operator interactions are not respected by `Float` 's instance. See http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Ord.html

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

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

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