1

Currently, Comparable looks like this:

  public protocol Comparable : Equatable {
    /// A [strict total order](Total order - Wikipedia)
    /// over instances of `Self`.
    @warn_unused_result
    func < (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func <= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func >= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func > (lhs: Self, rhs: Self) -> Bool
  }

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.

The FloatingPoint proposal (SE-0067, <https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md&gt;\) suggests that Comparable's requirements should be weakened so that only "normal" members of types need to be ordered, while "exceptional" members like NaNs are permitted to violate the rules. In practice, though, this ends up making algorithms give bizarre and incorrect results:

  Welcome to Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29). Type :help for assistance.
    1> let numbers = Array(0.0.stride(to: 1.0, by: 0.2)) + [.NaN] + Array(1.0.stride(to: 0.0, by: -0.25))
  numbers: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 1
    [7] = 0.75
    [8] = 0.5
    [9] = 0.25
  }
    2> numbers.sort()
  $R1: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 0.25
    [7] = 0.5
    [8] = 0.75
    [9] = 1
  }

(Note that the behavior is actually much stranger than simply having the NaN act as a partition of the list—try sorting `Array(0.0.stride(to: 1.0, by: 0.1)) + [.NaN] + Array(0.0.stride(to: 1.0, by: 0.1))` to see what I mean. I'm sure there are sensible implementation reasons why `sort()` behaves this way, but they aren't really relevant to this discussion.)

To address this, FloatingPoint introduces an ad-hoc mechanism: there is a `totalOrder` method in the protocol which actually *does* sort NaNs in a useful way. But because this is ad-hoc, it can't be extended to other, non-floating-point types. And since it's not part of Comparable, the plain `sort()` (well, `sorted()` in Swift 3) method on Sequences of Comparable elements doesn't use it. That's not great; the type system shouldn't lead us astray like this.

I think we should go in the other direction. Rather than weakening Comparable's promises, I think we should instead strengthen and clarify them.

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 `<=>`.
* Introduce a new `<>` operator which captures the concept of two values being unordered relative to one another. For example, `1.0 <> .nan` would be `true`.
* Define the friendly comparison operators like `<` and `==` as being a partial order covering all values which are not `<>`.
* Include default implementations such that you only need to define `<=>`; `<>` is always `false` by default, and the other operators call through to `<=>` and `<>` to determine the correct values to return.
* Redefine functions like `sorted(_:)` and `max(_:)` to take a total ordering function returning an `Order`, not a partial ordering function returning a `Bool`. In other words, you would pass `<=>` instead of `<`.

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](Total order - Wikipedia)
    /// 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

2

Is there a reason that NaN can’t just compare in a more useful way, e.g- always return true for the less than operator unless the other value is also NaN, thus ensuring it always comes first in ascending order? Or is there too much of a performance cost to make it a special case?

That said I’m a +1 to the idea, especially as only the new operator would really need to be implemented in cases happy to use the defaults for everything else (as the new operator covers them all, so long as it’s implemented with O(1) complexity).

For naming I’d prefer the simpler .Before, .Same and .After, but that’s minor detail, as it reads as Order.Before and so-on.

Regarding how this affects sorting methods though, some people (myself included) like the simplicity of being able to do the following:

  myArray.sort(>) // If array is of Comparable elements, just throw in the operator

While for less-than you could just pass in the new operator instead, is there an easy way to flip the operator to achieve a similar result? When dealing with Comparable elements you usually only need the ascending and descending options after all, so they’re pretty common ways to sort.

···

On 24 Apr 2016, at 02:28, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

Currently, Comparable looks like this:

  public protocol Comparable : Equatable {
    /// A [strict total order](Total order - Wikipedia)
    /// over instances of `Self`.
    @warn_unused_result
    func < (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func <= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func >= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func > (lhs: Self, rhs: Self) -> Bool
  }

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.

The FloatingPoint proposal (SE-0067, <https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md&gt;\) suggests that Comparable's requirements should be weakened so that only "normal" members of types need to be ordered, while "exceptional" members like NaNs are permitted to violate the rules. In practice, though, this ends up making algorithms give bizarre and incorrect results:

  Welcome to Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29). Type :help for assistance.
    1> let numbers = Array(0.0.stride(to: 1.0, by: 0.2)) + [.NaN] + Array(1.0.stride(to: 0.0, by: -0.25))
  numbers: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 1
    [7] = 0.75
    [8] = 0.5
    [9] = 0.25
  }
    2> numbers.sort()
  $R1: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 0.25
    [7] = 0.5
    [8] = 0.75
    [9] = 1
  }

(Note that the behavior is actually much stranger than simply having the NaN act as a partition of the list—try sorting `Array(0.0.stride(to: 1.0, by: 0.1)) + [.NaN] + Array(0.0.stride(to: 1.0, by: 0.1))` to see what I mean. I'm sure there are sensible implementation reasons why `sort()` behaves this way, but they aren't really relevant to this discussion.)

To address this, FloatingPoint introduces an ad-hoc mechanism: there is a `totalOrder` method in the protocol which actually *does* sort NaNs in a useful way. But because this is ad-hoc, it can't be extended to other, non-floating-point types. And since it's not part of Comparable, the plain `sort()` (well, `sorted()` in Swift 3) method on Sequences of Comparable elements doesn't use it. That's not great; the type system shouldn't lead us astray like this.

I think we should go in the other direction. Rather than weakening Comparable's promises, I think we should instead strengthen and clarify them.

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 `<=>`.
* Introduce a new `<>` operator which captures the concept of two values being unordered relative to one another. For example, `1.0 <> .nan` would be `true`.
* Define the friendly comparison operators like `<` and `==` as being a partial order covering all values which are not `<>`.
* Include default implementations such that you only need to define `<=>`; `<>` is always `false` by default, and the other operators call through to `<=>` and `<>` to determine the correct values to return.
* Redefine functions like `sorted(_:)` and `max(_:)` to take a total ordering function returning an `Order`, not a partial ordering function returning a `Bool`. In other words, you would pass `<=>` instead of `<`.

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](Total order - Wikipedia)
    /// 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

3

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

···

On Apr 23, 2016, at 6:28 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

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](Total order - Wikipedia)
    /// 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

4

Currently, Comparable looks like this:

  public protocol Comparable : Equatable {
    /// A [strict total order](Total order - Wikipedia)
    /// over instances of `Self`.
    @warn_unused_result
    func < (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func <= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func >= (lhs: Self, rhs: Self) -> Bool

    @warn_unused_result
    func > (lhs: Self, rhs: Self) -> Bool
  }

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.

The FloatingPoint proposal (SE-0067,
<https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md&gt;\)
suggests that Comparable's requirements should be weakened so that
only "normal" members of types need to be ordered, while "exceptional"
members like NaNs are permitted to violate the rules. In practice,
though, this ends up making algorithms give bizarre and incorrect
results:

  Welcome to Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29). Type :help for assistance.
    1> let numbers = Array(0.0.stride(to: 1.0, by: 0.2)) + [.NaN] + Array(1.0.stride(to: 0.0, by: -0.25))
  numbers: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 1
    [7] = 0.75
    [8] = 0.5
    [9] = 0.25
  }
    2> numbers.sort()
  $R1: [Double] = 10 values {
    [0] = 0
    [1] = 0.20000000000000001
    [2] = 0.40000000000000002
    [3] = 0.60000000000000009
    [4] = 0.80000000000000004
    [5] = NaN
    [6] = 0.25
    [7] = 0.5
    [8] = 0.75
    [9] = 1
  }

(Note that the behavior is actually much stranger than simply having the NaN act as a partition of the list—try sorting `Array(0.0.stride(to: 1.0, by: 0.1)) + [.NaN] + Array(0.0.stride(to: 1.0, by: 0.1))` to see what I mean. I'm sure there are sensible implementation reasons why `sort()` behaves this way, but they aren't really relevant to this discussion.)

To address this, FloatingPoint introduces an ad-hoc mechanism: there is a `totalOrder` method in the protocol which actually *does* sort NaNs in a useful way. But because this is ad-hoc, it can't be extended to other, non-floating-point types. And since it's not part of Comparable, the plain `sort()` (well, `sorted()` in Swift 3) method on Sequences of Comparable elements doesn't use it. That's not great; the type system shouldn't lead us astray like this.

I think we should go in the other direction. Rather than weakening Comparable's promises, I think we should instead strengthen and clarify them.

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

That has been my plan for some time.

* Introduce a new `<>` operator which captures the concept of two
values being unordered relative to one another. For example, `1.0 <>
.nan` would be `true`.

Cute. I'm not sure we need this operator, though. Is this a test you
actually want in real code often enough to make it worth having?

* Define the friendly comparison operators like `<` and `==` as being
a partial order covering all values which are not `<>`.

Natch'.

* Include default implementations such that you only need to define
`<=>`; `<>` is always `false` by default, and the other operators call
through to `<=>` and `<>` to determine the correct values to return.

I think you can do the default implementations of `<`, `>`, `<=`, `>=`,
`==` and `!=` using just `<=>`. Why involve `<>`?

* Redefine functions like `sorted(_:)` and `max(_:)` to take a total
ordering function returning an `Order`, not a partial ordering
function returning a `Bool`.

They don't accept partial ordering functions today.

In other words, you would pass `<=>` instead of `<`.

One problem I haven't come to a conclusion about is the total- vs
strict-weak- ordering question. For me, this area is where most of the
uncertainty about pursuing something like this lies, and once we get it
sorted out I'd be very happy to move ahead. I'm sure it's doable but I
just haven't had the time to devote. In short:

Almost all types can reasonably implement a total order, but almost any
algorithm that can be implemented with just a binary comparison
predicate (sort, binary search, partition, et al) only needs a strict
weak ordering to produce sensible results, because as far as the
ordering is concerned, unordered values appear to be equivalent.

In fact it seems to me that the distinction between a total ordering and
a strict-weak ordering is *only* observable in the presence of an
equality comparison. When an algorithm takes a single comparison
function (whether it has binary or trinary results) and doesn't
additionally require Equatable conformance, there is no reason
whatsoever to require a total ordering, and you can easily argue that it
is meaningless to do so.

[If you're reading along and wondering what all these kinds of orderings are
about, I once figured that out and wrote a blog post about it:
http://web.archive.org/web/20120422220137/http://cpp-next.com/archive/2010/02/order-i-say/\]

···

on Sat Apr 23 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

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](Total order - Wikipedia)
    /// 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?

--
Dave

5

Is there a reason that NaN can’t just compare in a more useful way, e.g-
always return true for the less than operator unless the other value is
also NaN, thus ensuring it always comes first in ascending order? Or is
there too much of a performance cost to make it a special case?

Because NaN is not less than the other value. I'd be very much against
changing how comparison operators work with floating point values to
deviate from standards. What you're describing is the IEEE 754 function
minNum, which is proposed as `minimum` in the Swift floating point protocol
proposal.

That said I’m a +1 to the idea, especially as only the new operator would
really need to be implemented in cases happy to use the defaults for
everything else (as the new operator covers them all, so long as it’s
implemented with O(1) complexity).

For naming I’d prefer the simpler .Before, .Same and .After, but that’s
minor detail, as it reads as Order.Before and so-on.

At least with respect to floating point, the IEEE 754 standard goes with
the terminology "below" and "above"--which is reflected also in the names
"nextUp" and "nextDown".

Regarding how this affects sorting methods though, some people (myself

included) like the simplicity of being able to do the following:

myArray.sort(>) // If array is of Comparable elements, just throw in the
operator

While for less-than you could just pass in the new operator instead, is
there an easy way to flip the operator to achieve a similar result?

What's wrong with reverse()?

···

On Sun, Apr 24, 2016 at 5:28 AM, Haravikk via swift-evolution < swift-evolution@swift.org> wrote:

When dealing with Comparable elements you usually only need the ascending
and descending options after all, so they’re pretty common ways to sort.

On 24 Apr 2016, at 02:28, Brent Royal-Gordon via swift-evolution < > swift-evolution@swift.org> wrote:

Currently, Comparable looks like this:

public protocol Comparable : Equatable {
/// A [strict total order](
Total order - Wikipedia)
/// over instances of `Self`.
@warn_unused_result
func < (lhs: Self, rhs: Self) -> Bool

@warn_unused_result
func <= (lhs: Self, rhs: Self) -> Bool

@warn_unused_result
func >= (lhs: Self, rhs: Self) -> Bool

@warn_unused_result
func > (lhs: Self, rhs: Self) -> Bool
}

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.

The FloatingPoint proposal (SE-0067, <
https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md&gt;\)
suggests that Comparable's requirements should be weakened so that only
"normal" members of types need to be ordered, while "exceptional" members
like NaNs are permitted to violate the rules. In practice, though, this
ends up making algorithms give bizarre and incorrect results:

Welcome to Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29).
Type :help for assistance.
1> let numbers = Array(0.0.stride(to: 1.0, by: 0.2)) + [.NaN] +
Array(1.0.stride(to: 0.0, by: -0.25))
numbers: [Double] = 10 values {
[0] = 0
[1] = 0.20000000000000001
[2] = 0.40000000000000002
[3] = 0.60000000000000009
[4] = 0.80000000000000004
[5] = NaN
[6] = 1
[7] = 0.75
[8] = 0.5
[9] = 0.25
}
2> numbers.sort()
$R1: [Double] = 10 values {
[0] = 0
[1] = 0.20000000000000001
[2] = 0.40000000000000002
[3] = 0.60000000000000009
[4] = 0.80000000000000004
[5] = NaN
[6] = 0.25
[7] = 0.5
[8] = 0.75
[9] = 1
}

(Note that the behavior is actually much stranger than simply having the
NaN act as a partition of the list—try sorting `Array(0.0.stride(to: 1.0,
by: 0.1)) + [.NaN] + Array(0.0.stride(to: 1.0, by: 0.1))` to see what I
mean. I'm sure there are sensible implementation reasons why `sort()`
behaves this way, but they aren't really relevant to this discussion.)

To address this, FloatingPoint introduces an ad-hoc mechanism: there is a
`totalOrder` method in the protocol which actually *does* sort NaNs in a
useful way. But because this is ad-hoc, it can't be extended to other,
non-floating-point types. And since it's not part of Comparable, the plain
`sort()` (well, `sorted()` in Swift 3) method on Sequences of Comparable
elements doesn't use it. That's not great; the type system shouldn't lead
us astray like this.

I think we should go in the other direction. Rather than weakening
Comparable's promises, I think we should instead strengthen and clarify
them.

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 `<=>`.
* Introduce a new `<>` operator which captures the concept of two values
being unordered relative to one another. For example, `1.0 <> .nan` would
be `true`.
* Define the friendly comparison operators like `<` and `==` as being a
partial order covering all values which are not `<>`.
* Include default implementations such that you only need to define `<=>`;
`<>` is always `false` by default, and the other operators call through to
`<=>` and `<>` to determine the correct values to return.
* Redefine functions like `sorted(_:)` and `max(_:)` to take a total
ordering function returning an `Order`, not a partial ordering function
returning a `Bool`. In other words, you would pass `<=>` instead of `<`.

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](
Total order - Wikipedia)
/// 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

6

Regarding how this affects sorting methods though, some people (myself included) like the simplicity of being able to do the following:

  myArray.sort(>) // If array is of Comparable elements, just throw in the operator

That is extremely convenient. With my proposed extensions, it's actually writeable as this:

  myArray.sorted { ($0 <=> $1).reversed() }

But that's obviously much less convenient. It's also equivalent to this:

  myArray.sorted { $1 <=> $0 }

Which means, with the proper higher-order function, it's the same as this:

  myArray.sorted(flip(<=>))

···

--
Brent Royal-Gordon
Architechies

7

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.

The point is precisely that there *isn't* an `unordered` case. The spaceship operator *must* order all values; that makes it suitable for operations like `sort()` and `max()` which assume there is a total order over all values they encounter. Meanwhile, the traditional comparison operators like `<` and `==` are given flexibility to implement looser semantics like those seen in `FloatingPoint`.

On the other hand, just because there is *an* order doesn't mean it'll be a *sensible* order. In particular, if `min()` and `max()` are based on an ordering which includes NaNs, then in some circumstances at least one of them will favor a NaN over a normal value. It might be that the total order is not actually a good match for `min()` and `max()`, and they should instead use the partial order and ignore unordered elements.

(Of course, that again raises the question of whether it is an element or a *pair* of elements which is unordered.)

Perhaps think of it this way: `<=>` is an *ordering* operator; the others are *comparison* operators. The difference is that, even if two elements cannot be compared, they can still have a consistent order.

···

--
Brent Royal-Gordon
Architechies

8

Ah, I see what you’re saying. I don’t think that I would be in favor of this sort of approach: the only model we have to motivate this is floating point, and the use cases (e.g. sorting an array with nans in it) are uncommon, and it isn’t clear where nans should sort (beginning, middle, or end?).

For specific call sites that do have a specific handling in mind, they can pass in a closure predicate that does the specific comparison necessary for that call.

-Chris

···

On Apr 24, 2016, at 2:51 PM, Brent Royal-Gordon <brent@brentdax.com> wrote:

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.

The point is precisely that there *isn't* an `unordered` case. The spaceship operator *must* order all values; that makes it suitable for operations like `sort()` and `max()` which assume there is a total order over all values they encounter. Meanwhile, the traditional comparison operators like `<` and `==` are given flexibility to implement looser semantics like those seen in `FloatingPoint`.

On the other hand, just because there is *an* order doesn't mean it'll be a *sensible* order. In particular, if `min()` and `max()` are based on an ordering which includes NaNs, then in some circumstances at least one of them will favor a NaN over a normal value. It might be that the total order is not actually a good match for `min()` and `max()`, and they should instead use the partial order and ignore unordered elements.

(Of course, that again raises the question of whether it is an element or a *pair* of elements which is unordered.)

Perhaps think of it this way: `<=>` is an *ordering* operator; the others are *comparison* operators. The difference is that, even if two elements cannot be compared, they can still have a consistent order.

9

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

The point is precisely that there *isn't* an `unordered` case. The
spaceship operator *must* order all values; that makes it suitable for
operations like `sort()` and `max()` which assume there is a total order
over all values they encounter. Meanwhile, the traditional comparison
operators like `<` and `==` are given flexibility to implement looser
semantics like those seen in `FloatingPoint`.

On the other hand, just because there is *an* order doesn't mean it'll be
a *sensible* order. In particular, if `min()` and `max()` are based on an
ordering which includes NaNs, then in some circumstances at least one of
them will favor a NaN over a normal value. It might be that the total order
is not actually a good match for `min()` and `max()`, and they should
instead use the partial order and ignore unordered elements.

(Of course, that again raises the question of whether it is an element or
a *pair* of elements which is unordered.)

Perhaps think of it this way: `<=>` is an *ordering* operator; the others
are *comparison* operators. The difference is that, even if two elements
cannot be compared, they can still have a consistent order.

I think this is an important distinction to make and perhaps argues against
including these changes to Comparable; rather, a separate protocol might be
most appropriate. It's important, for instance, that -0.0 and +0.0 compare
equal, but also that they be ordered differently. Something else to
consider if you insist that all floating point values must be "orderable"
would be how two NaNs are ordered if they have different payloads. As far
as I'm aware, that goes beyond what IEEE 754 has to say about total
ordering of floating point values.

···

On Sun, Apr 24, 2016 at 4:51 PM, Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

10

Nothing in that specific case I suppose, but in similar cases that don’t return something that .reverse() can be used with it will be a bit more awkward to work with; in-place sorting would perhaps be a better example, as you can’t just expect everything the array is passed on to to call .reverse(), as they may not know what the order is supposed to be. This is where the full range of current comparison operators are useful. I considered that we could have two ordering operators such as <=< and >=> for ascending and descending respectively as drop-in replacements for < and >, but this wouldn’t help cases where <= and >= are used and I doubt we want yet more operators.

The enum could be given a raw type of Int with values of .Below (-1), .Same (0) and .Above (1), which would allow me to do: .sortInPlace({ $0 <=> $1 > 0 })
Though that feels a bit weird, like I should be testing against the actual enum cases, but doing so gets messy very quickly. Java uses an integer for sorting order, but then iirc their enum type came later so they might have used it if they’d had it, but their integer value has the added bonus that it can also optionally represent an estimate of how far two elements are displaced from one another.

On which note actually, should the .Below and .After cases include a stored value to give an optional estimate of displacement? This needn’t actually be used, and for some types won’t be accurate enough to be useful (in which case it should just be 1), but in some cases it can be useful to provide and use when documented properly.

···

On 24 Apr 2016, at 17:41, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Regarding how this affects sorting methods though, some people (myself included) like the simplicity of being able to do the following:

  myArray.sort(>) // If array is of Comparable elements, just throw in the operator

While for less-than you could just pass in the new operator instead, is there an easy way to flip the operator to achieve a similar result?

What's wrong with reverse()?

11

There's no reason we can't accept both kinds of ordering function, though it
does expand the overload set, which is a usability downside.

···

on Sun Apr 24 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

Regarding how this affects sorting methods though, some people (myself included) like the simplicity of being able to do the following:

  myArray.sort(>) // If array is of Comparable elements, just throw in the operator

That is extremely convenient. With my proposed extensions, it's actually writeable as this:

  myArray.sorted { ($0 <=> $1).reversed() }

But that's obviously much less convenient. It's also equivalent to this:

  myArray.sorted { $1 <=> $0 }

Which means, with the proper higher-order function, it's the same as this:

  myArray.sorted(flip(<=>))

--
Dave

12

The IEEE 754 totalOrder predicate is an honest-to-god total order on all canonical members of a format (this includes ordering all NaNs by sign, signalingness, and payload).

– Steve

···

On Apr 24, 2016, at 6:08 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Something else to consider if you insist that all floating point values must be "orderable" would be how two NaNs are ordered if they have different payloads. As far as I'm aware, that goes beyond what IEEE 754 has to say about total ordering of floating point values.

13

And that, almost by itself, is enough justification for us to use this
ordering for the result of <=> on floats. The fact that this ordering
is consistent with the results of < (for values that are ordered with
respect to <) is a bonus.

···

on Mon Apr 25 2016, Stephen Canon <swift-evolution@swift.org> wrote:

    On Apr 24, 2016, at 6:08 PM, Xiaodi Wu via swift-evolution > <swift-evolution@swift.org> wrote:

    Something else to consider if you insist that all floating point values must
    be "orderable" would be how two NaNs are ordered if they have different
    payloads. As far as I'm aware, that goes beyond what IEEE 754 has to say
    about total ordering of floating point values.

The IEEE 754 totalOrder predicate is an honest-to-god total order on all
canonical members of a format (this includes ordering all NaNs by sign,
signalingness, and payload).

--
Dave