[swift-evolution] [Idea] Bringing the partial/total ordering distinction into Comparable

[Chris Lattner]

On Apr 23, 2016, at 6:28 PM, Brent Royal-Gordon via swift-evolution <swift-evolution at swift.org> wrote:
> Simple and straightforward, but not actually accurate. In a strict total order, all elements are ordered, but that's not true of the current Comparable. For instance, floating-point NaNs are not ordered.
> In short, I propose we:
> 
> * Introduce a new `<=>` operator which implements a strict total ordering on the Comparable type. Rather than returning a `Bool`, it returns a new `Order` type which is similar to `NSComparisonResult`. This provides a semantic hint that non-ordering is not an option for `<=>`.

I’m generally in favor of moving to a comparison model like you propose, where we get a spaceship operator, an “Order” enum with less/equal/greater members, and have all the other operators be derived from that.

However, I don’t understand how that would help for floating point NaN behavior.  Wouldn’t you have to add a fourth member to the enum (“unordered’) that all clients would have to handle?  An approach like that could make sense.

-Chris


> Here's what the new `Comparable` might look like:
> 
> 	public enum Order {
> 	  case firstEarlier
> 	  case bothEqual
> 	  case firstLater
> 	}
> 
> 	/// Instances of conforming types can be compared using relational operators.
> 	/// 
> 	/// Comparable includes both a total order, which sorts all possible values, 
> 	/// and a partial order, which compares only "normal" or "common" values.
> 	/// The partial order may consider some elements "unordered" and return `false` 
> 	/// for all operations.
> 	/// 
> 	/// The `<=>` operator implements the total order; the others implement the 
> 	/// partial order. You may define only the total order, and `Comparable` will 
> 	/// provide default implementations which use it. You may also define both the 
> 	/// `<=>` operator and the `<>` "unordered" operator, and Comparable will 
> 	/// provide default implementations for the rest of the partial order which them. 
> 	/// You may also choose to implement the `<`, `>`, `<=`, `>=`, `==`, and 
> 	/// `!=` operators to completely customize the implementation.
> 	public protocol Comparable : Equatable {
> 	  /// A [total order](http://en.wikipedia.org/wiki/Total_order#Strict_total_order)
> 	  /// over instances of `Self`. In a total order, no element is permitted to be 
> 	  /// unordered relative to any other.
> 	  @warn_unused_result
> 	  func <=> (lhs: Self, rhs: Self) -> Order
> 	  
> 	  /// Returns `true` if, to partial order operators like `<` and `==`, `lhs` is 
> 	  /// unordered relative to `rhs`.
> 	  @warn_unused_result
> 	  func <> (lhs: Self, rhs: Self) -> Bool
> 	  
> 	  /// Returns `true` if `lhs` is less than `rhs`. Should be consistent with `<=>` except
> 	  /// when the elements are unordered relative to each other.
> 	  @warn_unused_result
> 	  func < (lhs: Self, rhs: Self) -> Bool
> 	  
> 	  /// Returns `true` if `lhs` is greater than `rhs`. Should be consistent with `<=>` except
> 	  /// when the elements are unordered relative to each other.
> 	  @warn_unused_result
> 	  func > (lhs: Self, rhs: Self) -> Bool
> 	  
> 	  /// Returns `true` if `lhs` is less than or equal to `rhs`. Should be consistent with `<=>` 
> 	  /// except when the elements are unordered relative to each other.
> 	  @warn_unused_result
> 	  func <= (lhs: Self, rhs: Self) -> Bool
> 	  
> 	  /// Returns `true` if `lhs` is greater than or equal to `rhs`. Should be consistent with `<=>` except
> 	  /// when the elements are unordered relative to each other.
> 	  @warn_unused_result
> 	  func >= (lhs: Self, rhs: Self) -> Bool
> 	}
> 
> Some APIs on Order which might be useful:
> 
> 	public extension Order {
> 	  /// Returns the equivalent order for the two arguments reversed.
> 	  func reversed() -> Order {…}
> 	  /// Returns `x` and `y` reordered according to `self`, with the earlier one first.
> 	  func reorder<T>(_ x: T, _ y: T) -> (T, T) {…}
> 	  /// Returns `x` and `y` reordered with the earlier one first.
> 	  static func reorder<T: Comparable>(_ x: T, _ y: T) -> (T, T) {…}
> 	}
> 
> Alternate designs:
> 
> * The `<>` operator is arguably not very obvious, or too confusable with some languages' use of that operator for "not equals". It could instead be a different operator, an instance method, or a class method.
> * It might make sense to instead use `<>` to say "is comparable" and `!<>` to say "is incomparable".
> * It may also be better to define Comparable such that certain *values* are incomparable with any value, rather than certain *pairs* of values being incomparable. If so, we would want an `isIncomparable` property instead of a method or function. That works for `FloatingPoint`, but it might not suit other types. (For instance, with the `<>` operator in place, `String.Index` could be made incomparable with indices from other strings, but all `String.Index`es would still have a total order. That design wouldn't be possible with an `isIncomparable` property.)
> * The `<=>` operator is common from other languages, but it might still be too jargony. One interesting design for this would be to expose the total order as a method on `Comparable` which is used as an implementation hook for an `Order.init(_:_:)` initializer.
> * The cases of Order are highly bikesheddable. I like these names more than `ascending` and `descending` because I have an easier time understanding what they mean, but others might disagree.
> * I'm also toying with the idea that the partial order, which includes `==`, may have a looser definition of equality than the total order; this would mean that, for instance, `String`'s total order could fall back to `UnicodeScalar.value` comparison to distinguish between strings which have equal graphemes. I'm not sure how useful that would be in practice, though.
> 
> Any thoughts?
> 
> -- 
> Brent Royal-Gordon
> Architechies
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution