Is there a conflict between `Ord` implementation for `Results<T, ()>` and `Option<T>`?

help
1

This issue come from this discussion.

When I check the detailed Ord implementation, it said that, Ord uses a Lexicographical comparison to compare two differnet item. It is said that,

An empty sequence is lexicographically less than any non-empty sequence.

In this case, None is less than Some(T) since None could be regarded as empty. But same thing is not true for Result type. For results, Err(..) always larger than Ok(..).

Why the order in both Option and Result are different? Should it be corrected into Err(..)<Ok(..) ?

2

I don't know why. But changing it would be a breaking change, I assume, so it won't happen. Right?

3 Likes
3

I think this is where you become mislead. None isn't less than Some(T) because None is empty; None is less than Some(T) because None lexicographically precedes Some(T) in terms of the declaration order of the enums variants.

When derived on structs, it will produce a lexicographic ordering based on the top-to-bottom declaration order of the struct’s members.

When derived on enums, variants are ordered primarily by their discriminants. Secondarily, they are ordered by their fields. By default, the discriminant is smallest for variants at the top, and largest for variants at the bottom.

I.e. make your own Option-alike with None as the second variant, derive the lexicographic Ord implementation, and see how None is greater than any Some(_).

Also, these are distinct types. I don't see how they're "the same thing" at all.

7 Likes
4

Lexicographical order necessarily applies to product-like types, i.e., structs, tuples, and sequences/contains. It doesn't make any sense to talk about "lexicographical" order in the case of enum variants.

You should think about how things are (or can logically be) implemented instead of blindly assigning the meaning of one part of the documentation to a completely unrelated concept.

1 Like
5

Well, this doesn't really answer why it's designed this way though. Why we declare None before Some(T)? Is it arbitrarily chosen? Or there's some deeper reason? I can come up with some explanation like it is done this way so Option<NonNull<T>> or Option<NonZero<X>> behave well. But I don't have a very good example for the Ok vs Err case.

2 Likes
6

They answered this in the text you quoted. It's the declaration order of the enum variants. Option is an enum.

7

I guess the question is "why the enum was declared in this order?", and the most realistic answer, in my opinion, is "it's not that important".

4 Likes
8

I wish that neither of them was Ord, just PartialOrd.

Because I've never heard a good reason why the current order is better than the opposite order, and the current arbitrary choice means weird asymmetries.

(But as was said above, there's no way it's changing.)

4 Likes
9

Lexicographical order necessarily applies to product-like types, i.e., structs, tuples, and sequences/contains. It doesn't make any sense to talk about "lexicographical" order in the case of enum variants.

Lexicographical ordering does make perfect sense for Option, which is isomorphic to the type of lists up to length 1. Thus None (empty list) indeed precedes Some (1-list) lexicographically, and the order chosen for Option is arguably the correct one. The same logic does not apply to Result, though, because Ok and Err are equivalent in that sense.

1 Like
10

You can view it as a special case, yes, but in general, this is not the case with all enums.

11

The lexicographic order makes sense on any indexed sum, of which enums and product types are some special cases.

In fact you can think of enums as a pair where the left type is the discriminant type and the right type depends on the discriminant value. Then you can first order by the left value, the discriminant, and when it's equal you can order by the right value, which must have the same type because the discriminant was equal.

12

Probably for lexicographic reasons, as you noted. Possibly also because it matches a common convention in C that the "0" variant of an enum is the default and/or false-y case.

1 Like
13

None being sorted first also means that types like Option<NonNull<T>> and Option<NonZeroUsize> will sort the same way as isomorphic types *const T and usize, and that comparisons of these types can in theory (but not in practice?) compile to a single instruction.

4 Likes
14

Ancient bug: Comparison of Option<NonZeroU*> is not fully optimized · Issue #49892 · rust-lang/rust · GitHub (and others too, like Missed optimization: Option<fieldless enum> equality · Issue #72646 · rust-lang/rust · GitHub )

There's good news, though! With Add range attribute to scalar function results and arguments by andjo403 · Pull Request #128371 · rust-lang/rust · GitHub it's reasonably probably that a whole bunch of these cases are going to start getting better soon.

1 Like
15

I have no idea, but the current implementation stop us defining things like type Option<T> = Result<T,()>, and thus, for error handling, we must write almost the same code for both Option<T> and Result<T,()>

Although it is a breaking change, since people hardly compare a Some(T) to None, or compare Ok(T) to Err(E), that might be fine.

I agree, that's what the code does. But I'm talking about design choose Some(T) greater than None.

In fact Option<T> and Result<T,()> share lots of interfaces.

The question is that, why Option is {None, Some(T)} and is not {Some(T), None}. We all know that according to the doc, {None, Some(T)} means None < Some.

2 Likes
16

To elaborate more on this point, you're making at least two leaps-of-logic:

  • Some::<T> is in some sense the same as Ok::<T, E>
    • This isn't a given, but let's roll with it in this comment; consider this "the presence of the primary value type"
  • None::<T> is similarly the same as Err::<T, E>
    • I don't buy this one; in general the absence of a value is not an error for example

If we throw out the second assumption, and combine the possible variants, we have three cases:

  • The presence of the primary value type
  • The presence of an error instead of the primary value type
  • The absence of both the primary value type and any error

That could be represented by an enum with three variants:

#[derive(Ord)]
enum ResOpt<T, E> {
    None,
    SomeOk(T),
    Err(E),
}

which has an order consistent with both Option<T> and Result<T, E>.

It's also consistent with both of these types,[1] i.e. they are consistent with each other:

Result<Option<T>, E>
Option<Result<T, E>>

If the order of Result was Err(_), Ok(_), then the order between the two above types would be inconsistent.

Under the above point of view, there is no conflict between the order of Result and Option.

There are much more fundamental reasons that can't happen, like the fact that coherence would cause the ecosystem to stop compiling.

  1. which you can convert between with the .transpose methods ↩︎

5 Likes
17

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.