Optional comparison revisited

Independent of this topic, I think this is worth considering—the latter is intuitively a “more specific” overload in the same way that a subclass is more specific than a superclass in the same parameter position.

I don’t doubt that we can find some way to define a total ordering of all types, but is it a total ordering that users will want and find intuitive?

We have yet to converge on a totally (pun) confident interpretation of a total order for two floating-point values of the same type.

I think most would agree that it’d be certainly strange for a positive integer of some type to compare less than zero of another type, but two fixed-width integer values of equal magnitude and sign aren’t totally equivalent in terms of bitwise operations (or even negation if they differ in signedness).

We do currently support heterogeneous integer comparison, but these operators are not implementations of any protocol requirement, thus limiting the scenarios in which they are implicitly invoked and thus the impact of unanticipated results. For instance, we’ve never needed to answer the question of the signedness of the minimum value of an array of integers of heterogeneous types—and what happens if that isn’t deterministic since we don’t currently guarantee a stable sort.

And even if the latter issues were overcome, there are implementation-level issues to contend with. For example, comparison between heterogeneous integer types is still broken in generic code when one operand is a literal, because comparison with the default integer literal type is favored over homogeneous comparison, leading to errors with bitwise operations :(

My hunch is that to support an intuitive total ordering over all comparables in full generality without squashing these unexpected emergent behavior bugs left and right (cf. also AnyHashable implementation issues), we would probably need support for arbitrary subtyping relationships for value types.

Circling back to the central topic about comparison to an optional value specifically—it bears emphasizing that it is not an oversight that the language requires explicit handling of the nil case. We can discuss alternative designs about what that handling is. But if the question is whether we should make handling the nil case implicit—as in any other scenario, that would be contrary to the purpose of Optional.

4 Likes

Thinking out loud: what if equivalence and comparison operations were universally typed to return Optional<Bool>. That would solve not only the optionals discussed here, but the Float.nan weirdness.

I think it's too late to make any fundamental changes like that, but if we're discussing hypotheticals, I think it would better to solve it more fundamentally: Float shouldn't isn't totally ordered or equatable, and we should express that nuance.

I think Rust did this correctly, by seperate traits for partial vs total equality (PartialEq vs Eq) and ordering (PartialOrd vs Ord).

5 Likes

How does Rust compare its "equivalent" of this type?

enum Foo: Comparable /* or similar */ {
    case one
    case two(Int)
    case three(String)
}

It is getting off-topic, but IMHO this is very serious and really needs consideration before Swift 6 release.

If your goal is for one, two and three to be incomparable, then you would not be implementing the Ord trait (Equivalent to our Comparable), only PartialOrd.

This works exactly the way you were suggesting: PartialOrd.partial_cmp returns an Option<Ordering>.

If you want a non-optional comparison result, you need to implement the Ord trait to get cmp, which returns just Ordering.

With PartialOrd, you also lose access to min and max (which makes sense. In rocks-paper-scissors, what's the min or max element? There isn't any), and the default sort. You can do it yourself by calling partial_cmp, but you have to handle the Nones.

Aside: Rust can auto-generate the implementation for you, but it probably has a different meaning from what you indented in this discussion

Rust has the equivalent of what we call "synthesized conformances" (when the compiler can automatically generate the conformance to some protocols under some circumstances), which they call derivation. For Enums, it works in top-to-bottom order. So Foo::One is smaller than all other values. Foo::Two is greater than ::One and smaller than all possible Foo::Three values.

#[derive(PartialEq, Eq, PartialOrd, Ord)]
enum Foo {
    One,
    Two(i64),
    Three(String),
}

fn main() {
    print!("{}\n", Foo::One < Foo::Two(123));
    print!("{}\n", Foo::Two(123) < Foo::Three("abc".to_string()));
}
3 Likes

Looks exactly what I'm getting with the above MyOptional types.

One good thing about this approach is that it's completely additive: we could consider the addition of PartiallyComparable and PartiallyEquatable protocols if we come up with a good case, supported with sufficient examples, without modifying the behavior and semantics of the existing protocols.

An arbitrary ordering should be picked. It doesn’t matter which one. For tie breaking purposes I’d suggest the order of declaration in the source which is what you’d get if you used the synthesized Comparable.

There is precedent for this: String conforms to Comparable and the sort order should be considered arbitrary. It is not there for human display purposes (except, at a pinch, for debug output or personal tool hackery). It exists because the ability to sort strings is use algorithmically e.g. for setting up a binary search, or uniqueing values.

So the answer to “what if you want to sort nil to the other end” is “why are you doing that”. That answer will drive what you actually do (perhaps what you actually want is to substitute in another value for nil, like 0 or ”” or Error). Once you answer that question, you can write a comparator function for sort(by:) or do a map before sorting that does what you want.

Personally, I’m very skeptical of introducing the concept of partial ordering. Technically correct is really not always the best kind of correct: if you’re not careful it can just be annoying without bringing sufficient benefit (see the many developers who despise Swift’s string model – we walk a fine line here). And even if we did have it as a solution to the Float situation (and I think @scanon’s previous proposals would still be a much better solution to this), making Optional conform to it instead of Comparable would be the wrong thing to do.

2 Likes

It might be superficially strange, but there is an easily documentable explanation: the implementation of < for any Comparable orders first by type, then within the type by its ordering (including with any tragic flaws in that ordering, such as with Float).

String is the precedent here: it might seem strange for ”a” to be greater than ”B” but that is the implementation. Strings should not be compared for the purposes of user display. To do that you need to go further, and use some locale-aware function. The same goes for any Comparable… the comparison is just for either debugging or algorithmic purposes. Making that ordering intuitive or pleasing to humans should be a non-goal IMO.

Since any Comparable and any BinaryInteger are distinct types they could have their own different implementations. It might be reasonable to say that something like BinaryInteger could actually be ordered numerically, if the protocol provided enough functionality to do it properly. Heroic attempts to test for this in the any Comparable implementation should probably be avoided though.

This reminds me of NULL ordering in SQL.

By default, ORDER BY foo ASC and ORDER BY foo DESC put nulls at the end or the beginning. One arbitrary ordering was picked (one that nobody can never remember).

Of course the default ordering of null did not suit all use cases, because that's the fate of arbitrary choices. So ASC NULLS LAST and DESC NULLS FIRST were introduced into the SQL syntax. And let's add ASC NULLS FIRST and DESC NULLS LAST for consistency.

At least SQL does not favor one ordering of nulls above the others. All orderings are granted with the same syntax (the case of SQLite, for example). This consistency smoothes the bad consequences of the initial arbitrary ordering: no one is ever penalized for his ordering needs.

Unfortunately, Swift does not, today, grant users with the tooling that would provide such a uniform treatment of nil orderings. One will be favored, the other one will be painful to reach:

let texts = ["foo", "bar", nil]

// Favored case
let nilsFirst = texts.sorted()

// Disfavored case
let nilsLast = texts.sorted { lhs, rhs in
    guard let lhs = lhs else { return false }
    guard let rhs = rhs else { return true }
    return lhs < rhs
}

This is concerning (at least to me):

  • We won't be able to find any objective reason for favouring one use case over the other.
  • People won't remember it.
  • Yes, we could ship a favored case, and wait for a proposal that would eventually restore equality between use cases. But Swift is not SQL: this will be much harder. Inequality is likely to stay.
  • Breaking equality between use cases for some arbitrary reason is a moral test for api designers. The Core Team has been through a lot of such moral tests already, and taking such decisions is their daily job. But those are moral tests nevertheless: when there exists a path that does not break equality, it should be considered.
2 Likes

Continuing the comparison with SQL: SQL has partial ordering (1 < NULL is neither true or false, it is NULL). Despite this, it can sort collections that contain nulls. This is because it distinguishes value comparison from collection sorting. We may well be inspired from this precedent:

  • Optional would not become Comparable
  • Collections of optionals would get sorting methods that deal with nil.
1 < nil              // does not compile
[2, 1, nil].sorted() // does not compile

[2, 1, nil].sorted(.nilFirst) // OK: [nil, 1, 2]
[2, 1, nil].sorted(.nilLast)  // OK: [1, 2, nil]

Maybe that would address most of our users' needs?

This is somewhat complicated by the fact that we went and introduced heterogeneous comparisons for BinaryInteger that do the "right thing", which unfortunately puts us in a situation similar to where we are for floating-point--the arguably-desired protocol-level semantics are in conflict with the existing semantics of the concrete operations.

I think that this is resolvable, but probably not in a way that makes everyone totally happy.

I agree with Xiaodi's earlier point that one of the benefits of Optional is forcing you to think about the nil case. There isn't an obvious single answer here, and so Swift shouldn't just pick one for you. But that doesn't we can't make it more convenient to do these comparisons.

I think the right solution is to offer a proper comparator library. Optional would offer the obvious comparators in that library:

extension Optional {
  static func orderingNilsEarlier(lhs: Wrapped?, rhs: Wrapped?) -> ComparisonResult
    where Wrapped: Comparable

  static func orderingNilsLater(lhs: Wrapped?, rhs: Wrapped?) -> ComparisonResult
    where Wrapped: Comparable

  static func orderingNilsEarlier(comparator: (Wrapped, Wrapped) -> ComparisonResult)
    -> (Wrapped?, Wrapped?) -> ComparisonResult

  static func orderingNilsLater(comparator: (Wrapped, Wrapped) -> ComparisonResult)
    -> (Wrapped?, Wrapped?) -> ComparisonResult
}

It would be especially nice if that library were integrated into our Comparable derivation so that you could e.g. just specify the comparator to use for a particular stored property instead of being forced to write out the Comparable conformance from scratch. Well, assuming we had Comparable derivation for structs at all, which seems like something we should have. Someone ought to write a roadmap about where the language should be going with conformance derivation.

10 Likes

Mind you, we could take a similar approach to what we did with heterogeneous comparison operators for integers.

Namely, this would involve introducing custom (deliberately not protocol-conforming) concrete implementations of <, <=, >, and >= on Optional itself which return Bool? and propagate nil. Overload disfavoring shenanigans may be necessary to avoid clobbering the desired protocol-conforming operations, but it should be possible to introduce such an ad hoc notion of partial ordering specifically for Optional.

Whether that would be wise…

1 Like

Great example, thank you.

"a".compare("b") == .orderedAscending  is to  1.0 < 2.0
as
"a" < "b"   is to   1.0.lessThan(2.0) // bike shedding

where "lessThan" works sensibly on all numbers including "nans".

Or, (with the help of some explicit compatibility opt-in toggle) we could even flip the default and make "<" working sensibly with nans and another operation like "lessThan" be more like "high level comparison" (as String's compare is).