<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">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?</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">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).</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Regarding how this affects sorting methods though, some people (myself included) like the simplicity of being able to do the following:</div><div class=""><br class=""></div><div class=""><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>myArray.sort(>)<span class="Apple-tab-span" style="white-space:pre"> </span>// If array is of Comparable elements, just throw in the operator</font></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div><blockquote type="cite" class=""><div class="">On 24 Apr 2016, at 02:28, Brent Royal-Gordon via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">Currently, Comparable looks like this:<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>public protocol Comparable : Equatable {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// A [strict total order](<a href="http://en.wikipedia.org/wiki/Total_order#Strict_total_order" class="">http://en.wikipedia.org/wiki/Total_order#Strict_total_order</a>)<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// over instances of `Self`.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func < (lhs: Self, rhs: Self) -> Bool<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func <= (lhs: Self, rhs: Self) -> Bool<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func >= (lhs: Self, rhs: Self) -> Bool<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func > (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class="">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.<br class=""><br class="">The FloatingPoint proposal (SE-0067, <<a href="https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md" class="">https://github.com/apple/swift-evolution/blob/master/proposals/0067-floating-point-protocols.md</a>>) 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:<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>Welcome to Apple Swift version 2.2 (swiftlang-703.0.18.1 clang-703.0.29). Type :help for assistance. <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> 1> let numbers = Array(0.0.stride(to: 1.0, by: 0.2)) + [.NaN] + Array(1.0.stride(to: 0.0, by: -0.25)) <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>numbers: [Double] = 10 values {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [0] = 0<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [1] = 0.20000000000000001<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [2] = 0.40000000000000002<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [3] = 0.60000000000000009<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [4] = 0.80000000000000004<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [5] = NaN<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [6] = 1<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [7] = 0.75<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [8] = 0.5<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [9] = 0.25<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> 2> numbers.sort()<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>$R1: [Double] = 10 values {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [0] = 0<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [1] = 0.20000000000000001<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [2] = 0.40000000000000002<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [3] = 0.60000000000000009<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [4] = 0.80000000000000004<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [5] = NaN<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [6] = 0.25<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [7] = 0.5<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [8] = 0.75<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> [9] = 1<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class="">(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.)<br class=""><br class="">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.<br class=""><br class="">I think we should go in the other direction. Rather than weakening Comparable's promises, I think we should instead strengthen and clarify them.<br class=""><br class="">In short, I propose we:<br class=""><br class="">* 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 `<=>`.<br class="">* 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`.<br class="">* Define the friendly comparison operators like `<` and `==` as being a partial order covering all values which are not `<>`.<br class="">* 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.<br class="">* 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 `<`.<br class=""><br class="">Here's what the new `Comparable` might look like:<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>public enum Order {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> case firstEarlier<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> case bothEqual<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> case firstLater<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// Instances of conforming types can be compared using relational operators.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// Comparable includes both a total order, which sorts all possible values, <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// and a partial order, which compares only "normal" or "common" values.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// The partial order may consider some elements "unordered" and return `false` <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// for all operations.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// The `<=>` operator implements the total order; the others implement the <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// partial order. You may define only the total order, and `Comparable` will <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// provide default implementations which use it. You may also define both the <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// `<=>` operator and the `<>` "unordered" operator, and Comparable will <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// provide default implementations for the rest of the partial order which them. <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// You may also choose to implement the `<`, `>`, `<=`, `>=`, `==`, and <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>/// `!=` operators to completely customize the implementation.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>public protocol Comparable : Equatable {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// A [total order](<a href="http://en.wikipedia.org/wiki/Total_order#Strict_total_order" class="">http://en.wikipedia.org/wiki/Total_order#Strict_total_order</a>)<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// over instances of `Self`. In a total order, no element is permitted to be <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// unordered relative to any other.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func <=> (lhs: Self, rhs: Self) -> Order<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `true` if, to partial order operators like `<` and `==`, `lhs` is <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// unordered relative to `rhs`.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func <> (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `true` if `lhs` is less than `rhs`. Should be consistent with `<=>` except<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// when the elements are unordered relative to each other.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func < (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `true` if `lhs` is greater than `rhs`. Should be consistent with `<=>` except<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// when the elements are unordered relative to each other.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func > (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `true` if `lhs` is less than or equal to `rhs`. Should be consistent with `<=>` <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// except when the elements are unordered relative to each other.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func <= (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> <br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `true` if `lhs` is greater than or equal to `rhs`. Should be consistent with `<=>` except<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// when the elements are unordered relative to each other.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> @warn_unused_result<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func >= (lhs: Self, rhs: Self) -> Bool<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class="">Some APIs on Order which might be useful:<br class=""><br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>public extension Order {<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns the equivalent order for the two arguments reversed.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func reversed() -> Order {…}<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `x` and `y` reordered according to `self`, with the earlier one first.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> func reorder<T>(_ x: T, _ y: T) -> (T, T) {…}<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> /// Returns `x` and `y` reordered with the earlier one first.<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span> static func reorder<T: Comparable>(_ x: T, _ y: T) -> (T, T) {…}<br class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}<br class=""><br class="">Alternate designs:<br class=""><br class="">* 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.<br class="">* It might make sense to instead use `<>` to say "is comparable" and `!<>` to say "is incomparable".<br class="">* 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.)<br class="">* 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.<br class="">* 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.<br class="">* 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.<br class=""><br class="">Any thoughts?<br class=""><br class="">-- <br class="">Brent Royal-Gordon<br class="">Architechies<br class=""><br class="">_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></body></html>