# \[Proposal\] Formalized Ordering, take 2

**URL:** <https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540>\
**Category:** Discussion\
**Created:** [July 25, 2016, 11:41am UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540 "2016-07-25T11:41:33Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![pyrtsa](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/pyrtsa/32/740_2.png) [@pyrtsa](https://forums.swift.org/u/pyrtsa)\
**Post date:** [July 25, 2016, 11:41am UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/1 "2016-07-25T11:41:33Z")

</div>

Since we're running short on time, and the previous discussion thread diverged, here's my attempt to fix the Comparable protocol.

Pull request: [Formalized ordering by pyrtsa · Pull Request #464 · apple/swift-evolution · GitHub](https://github.com/apple/swift-evolution/pull/464)

TL;DR:

1. Equatable remains unchanged, while Comparable bloats a bit to support several use cases.  
2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal to minus zero.  
3. Types are not strictly required to become totally ordered, even if it's strongly recommended.

— — —

I simply can't see how a pure total order version of Comparable would fit the standard way floating point values are expected to behave. However, I think we can reach a satisfactory conclusion, one that involves no crashing in the standard library, which is what I previously suggested.

What I'm trying to fix is so that all operations listed in [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws for types without incomparable values, and that types with weaker order can still work in some well-defined way outside their totally ordered range.

PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for time is tight. I can pull back or revise the proposal if you don't want to be involved.

— Pyry

Formalized Ordering

Proposal: SE-NNNN \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller \<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins \<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola \<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
Status: Awaiting review  
Review manager: TBD  
\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt;Introduction)

This proposal cleans up the semantics of ordering relations in the standard library. Our goal is to formalize the total ordering semantics of the Comparable protocol and still provide accessible ordering definitions for types without total ordering semantics.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt;Motivation)

The standard comparison operators have an intuitive meaning to programmers. Swift encourages encoding that in an implementation of Comparable that respects the rules of a total order \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes advantage of these rules to provide consistent implementations for sorting and searching generic collections of Comparable types.

Not all types behave so well in this framework, unfortunately. There are cases where the semantics of a total order cannot apply and still maintain the traditional definition of “comparison” over these types. Take, for example, sorting an array of Float s. Today, Float ‘s instance of Comparable follows IEEE-754 and returns false for all comparisons of NaN . In order to sort this array, NaN s are considered outside the domain of \< , and the order of a “sorted” array containing them is undefined.

In addition, generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make twice as many comparisons to request the ordering of values with respect to each other than they should. Having a central operation to return information about the ordering of values once should provide a speedup for these operations.

In the interest of cleaning up the semantics of Comparable types of all shapes and sizes and their uses in the Swift Standard Library, this proposal is going to re-arrange the requirements of the Comparable and Equatable protocols.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed) solution

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt;Equatable)

The interface of Equatable remains unchanged under this proposal. Equatable types should still respect the equivalence laws of reflexivity (a == a), symmetry (a == b iff b == a), and transitivity (if a == b and b == c, then a == c). Further, != remains a top-level binary operator for which a != b iff !(a == b).

Types containing properties inessential to equality, however, are allowed to retain their notion of identity. For example Array's capacity isn't considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.

IEEE-754 floating point numbers are allowed to break the reflexivity law by defining that .nan != x for any value of x, which is the standard behaviour documented in IEEE-754 and implemented the same way in other programming languages.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt;Comparable)

The Comparable protocol will now require (without default implementation provided) a single operator definition: \<=\> — the comparison operator. From this, all other comparison operators will be derived so as to respect the total order semantics of Comparable:

To maintain compatibility with IEEE-754, the interface of Comparable also contains as customization points the operators \<, \<=, and == (derived from Equatable) as well as the static binary functions \_min(\_:\_:) and \_max(\_:\_:). User-defined types are recommended against overriding the default implementations.

The uncustomizable top-level binary comparison operators a \> b and a \>= b are implemented as synonyms to b \< aand b \<= a, respectively.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard) Library

Unlike a previous revision of this proposal, standard library algorithms specific to FloatingPoint remain unchanged.

Overloads of \<=\> for tuples of Comparable elements are provided up to a library-defined arity.

The intent of this proposal is to later augment the standard library so that functions that take an ordering predicate by: (T, T) -\> Bool will have an overload ordering: (T, T) -\> Ordering that will provide a — potentially — more efficient implementation. A list of such functions is provided in Future directions.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed) design

The Comparable protocol will be amended by taking away \> and \>=, adding customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the ordering operator \<=\> that makes use of the Ordering enum defined below.

enum Ordering : Equatable {  
&nbsp;&nbsp;case ascending  
&nbsp;&nbsp;case equal  
&nbsp;&nbsp;case descending  
}

infix operator \<=\> { associativity none precedence 130 }

public protocol Comparable : Equatable {  
&nbsp;&nbsp;// Implementation required:  
&nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering

&nbsp;&nbsp;// Default implementations provided:  
&nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
&nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
&nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
&nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
&nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
}  
The \<=\> operator defines a relationship between == and \<=\> such that a == b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics in the way of IEEE-754. Likewise, it should hold that (a \<=\> b) == .ascending iff a \< b, and (a \<=\> b) != .descending iff a \<= b.

The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the right-hand side to retain identity, as presently explained in this comment \<[swift/Algorithm.swift at 4614adc16168d612b6fc7e7a161dd5b6b34be704 · apple/swift · GitHub](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C). Making them customization points of Comparable, we get to fix their behaviour in the presense of unorderable values (SR-1011 \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).

Most user types should only implement \<=\> and leave the other members of Equatable and Comparable to their default implementations. Note that even == has a sane default implementation if Self is made Comparable:

// Default implementations, which should be used for most Comparable types:  
extension Comparable {  
&nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
&nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
&nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
&nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
&nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
}

// Unoverridable top-level operators and functions for Comparable:  
public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }  
public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }  
public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }  
public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }  
\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling) of floating point comparisons

The following text is written in terms of Double but other floating-point types (Float, Float80) are proposed the same treatment.

The IEEE-754 floating point specification has two oddities when it comes to orderability: there are two zeros (0.0 and -0.0) which are considered equal to each other, and there are multiple not-a-number values x for which x.isNaN == true and x != y with any value of y, even x itself. (Remark: the most common NaN value is obtained by the static property Double.nan.)

The interface of Comparable is designed so that \<=\> alone is able to produce a total order among all possible Doublevalues, sorting negative NaNs less than any other values, and positive NaNs greater than any other. Otherwise, within the range of totally ordered floating point values, -Double.infinity ... Double.infinity, the result of a \<=\> b remains in full agreement with the laws of a \< b, a \<= b, and a == b.

The suggested implementation of Double : Comparable makes \<=\> distinguish between every different bitPatternof NaN:

extension Double : Comparable {  
&nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
&nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
&nbsp;&nbsp;}  
&nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
&nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
&nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
&nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
&nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
}

// Likewise:  
extension Float : Comparable { ... }  
extension Float80 : Comparable { ... }  
\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples) and order reversal

Due to missing language support, tuples of Comparable elements cannot be Comparable themselves, but in the spirit of SE-0015 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;), such tuples are given their overloads of \<=\> up to a standard library defined maximum arity:

public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
&nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
&nbsp;&nbsp;if a != .equal { return a }  
&nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
&nbsp;&nbsp;if b != .equal { return b }  
&nbsp;&nbsp;return .equal  
}

// Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.  
To simplify the reversal of a given ordering operation, two members of Ordering are provided in an extension:

extension Ordering {  
&nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
&nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
&nbsp;&nbsp;{  
&nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
&nbsp;&nbsp;}

&nbsp;&nbsp;public var reversed: Ordering {  
&nbsp;&nbsp;&nbsp;&nbsp;switch self {  
&nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
&nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
&nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;}  
}  
\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt;Foundation)

In addition, Foundation code will now bridge NSComparisonResult to Ordering allowing for a fluid, natural, and safe API.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact) on existing code

The biggest drawback of the proposed design is the large surface area of Comparable's interface, as well as the possibility of overriding the comparison operators by mistake. On the other hand, since the required \<=\> operator is new and affects all users porting their previously Comparable data types to Swift 3, we can use documentation to suggest removing the redundant (and possibly faulty) implementations of other comparison operators.

Existing Equatable but not Comparable types that define an equivalence relation with == will remain unchanged.

Existing Comparable types that define a total ordering with \< will need to implement \<=\> and should remove their existing implementation of any comparison operators, including ==. All other existing Comparable types should implement \<=\> that provides a total ordering, or should drop their Comparable conformance.

Before:

struct Date: Comparable {  
&nbsp;&nbsp;let year: Int  
&nbsp;&nbsp;let month: Int  
&nbsp;&nbsp;let day: Int  
}

func ==(lhs: Date, rhs: Date) -\> Bool {  
&nbsp;&nbsp;return lhs.year == rhs.year  
&nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
&nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
}

func \<(lhs: Date, rhs: Date) -\> Bool {  
&nbsp;&nbsp;if lhs.year != rhs.year {  
&nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
&nbsp;&nbsp;} else if lhs.month != rhs.month {  
&nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
&nbsp;&nbsp;} else {  
&nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
&nbsp;&nbsp;}  
}  
After, using the tuple overload of \<=\>:

struct Date: Comparable {  
&nbsp;&nbsp;let year: Int  
&nbsp;&nbsp;let month: Int  
&nbsp;&nbsp;let day: Int

&nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
&nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
&nbsp;&nbsp;}

&nbsp;&nbsp;// // Explicit version:  
&nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
&nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
&nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
&nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
&nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
&nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
&nbsp;&nbsp;// }  
}  
\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives) considered

A previous design of this proposal suggested a strict total order upon Comparable. While that would make generic algorithms more correct, the definition ended up fighting against the expected behaviour of floating point numbers.

An alternative design that better matches the existing arithmetic-related protocols in Swift is one that uses a member function.

public protocol Comparable: Equatable {  
&nbsp;&nbsp;func compare(to: Self) -\> Ordering  
}  
However, while this API does read better than an operator, we believe that this imposes a number of artificial restrictions (especially in light of SE-0091 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;\](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;%5C))

There is no way to use Comparable.compare as a higher-order function in a non-generic context.  
If a member is desired, it can be provided in a protocol extension and defined in terms of the ordering operator; to each according to their need.  
The existing tuple overloads cannot be expressed with a member function.  
One other that Rust has adopted is the inclusion of PartialEquatable and PartialComparable as ancestors of their flavor of Equatable and Comparable . Having protocols to organize and catalogue types that can only guarantee partial equivalence and ordering relations is a good approach for modularity but clutters the standard library with two new protocols for which few useful algorithms could be written against.

\<[swift-evolution/NNNN-formalized-ordering.md at ca89e7b3a1dffc99baa695a03544fcba75afd0f3 · pyrtsa/swift-evolution · GitHub](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future) directions

That the default sort() compares by \< and not \<=\> should be considered a bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved in the presense of NaN. However, given that the current behaviour is to produce an unspecified order, the fix is additive and can be slipped past Swift 3.

With \<=\> in place, several present and future standard library algorithms involving a \<T : Comparable\> requirement will possibly benefit from knowing the total ordering of two operands at once. This is a list of possible such functions (taking Array as example), to be proposed separately as an additive change:

extension Array {  
&nbsp;&nbsp;// Sorting

&nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
&nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
&nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
&nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]

&nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
&nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
&nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
&nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
&nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>

&nbsp;&nbsp;// Binary search

&nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
&nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
&nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
&nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
}

---

<div class="post-metadata">

**Author:** ![Stephen\_Canon](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/stephen_canon/32/7220_2.png) [@Stephen\_Canon](https://forums.swift.org/u/Stephen_Canon)\
**Post date:** [July 25, 2016, 5:26pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/2 "2016-07-25T17:26:22Z")

</div>

Hi Pyry —

Dave and I spent some time discussing the details of how this applies to floating point earlier today. We’re now in agreement that \<=\> should treat -0 and +0 as distinct, and treat all NaNs as .equal. There are three motivating considerations:

1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that can produce both of them. In the parlance of IEEE 754, for any rounding mode, the sets of real values that round to them are disjoint. Because of this, if -0 and +0 appear as members of a set, or as keys in a dictionary, they necessarily are the result of distinct computations or data.

2. Substitutability. Adopting these semantics means that if `x \<=\> y` is `.equal`, `f(x) \<=\> f(y)` is also `.equal` for any computation `f(x)` that depends on the represented value (as opposed to the encoding) of its argument.

3. 754 defines four “specification levels”, or models:

&nbsp;&nbsp;- Level 1: The two-point compactification of the reals, or “extended real numbers”.  
&nbsp;&nbsp;- Level 2: The set of representable floating-point data: {-inf … -0} union { 0 … inf } union { NaN }.  
&nbsp;&nbsp;- Level 3: The set of representations of floating-point data: sign-exponent-significand triples, +/-inf, qNaN, sNaN.  
&nbsp;&nbsp;- Level 4: Floating-point encodings (bit patterns).

The `\<=\>` semantics we propose constitute a total order on level 2, which is the computable model closest to the (reasonably familiar) extended real numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s land between levels 1 and 2.

Thanks,  
– Steve

> **···**
>
> > On Jul 25, 2016, at 7:41 AM, Pyry Jahkola \<pyry.jahkola@iki.fi\> wrote:
> > 
> > Since we're running short on time, and the previous discussion thread diverged, here's my attempt to fix the Comparable protocol.
> > 
> > Pull request: [Formalized ordering by pyrtsa · Pull Request #464 · apple/swift-evolution · GitHub](https://github.com/apple/swift-evolution/pull/464)
> > 
> > TL;DR:
> > 
> > 1. Equatable remains unchanged, while Comparable bloats a bit to support several use cases.  
> > 2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal to minus zero.  
> > 3. Types are not strictly required to become totally ordered, even if it's strongly recommended.
> > 
> > — — —
> > 
> > I simply can't see how a pure total order version of Comparable would fit the standard way floating point values are expected to behave. However, I think we can reach a satisfactory conclusion, one that involves no crashing in the standard library, which is what I previously suggested.
> > 
> > What I'm trying to fix is so that all operations listed in [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws for types without incomparable values, and that types with weaker order can still work in some well-defined way outside their totally ordered range.
> > 
> > PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for time is tight. I can pull back or revise the proposal if you don't want to be involved.
> > 
> > — Pyry
> > 
> > Formalized Ordering
> > 
> > Proposal: SE-NNNN \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
> > Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller \<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins \<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola \<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
> > Status: Awaiting review  
> > Review manager: TBD  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt;Introduction](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt;Introduction)
> > 
> > This proposal cleans up the semantics of ordering relations in the standard library. Our goal is to formalize the total ordering semantics of the Comparable protocol and still provide accessible ordering definitions for types without total ordering semantics.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt;Motivation](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt;Motivation)
> > 
> > The standard comparison operators have an intuitive meaning to programmers. Swift encourages encoding that in an implementation of Comparable that respects the rules of a total order \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes advantage of these rules to provide consistent implementations for sorting and searching generic collections of Comparable types.
> > 
> > Not all types behave so well in this framework, unfortunately. There are cases where the semantics of a total order cannot apply and still maintain the traditional definition of “comparison” over these types. Take, for example, sorting an array of Float s. Today, Float ‘s instance of Comparable follows IEEE-754 and returns false for all comparisons of NaN . In order to sort this array, NaN s are considered outside the domain of \< , and the order of a “sorted” array containing them is undefined.
> > 
> > In addition, generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make twice as many comparisons to request the ordering of values with respect to each other than they should. Having a central operation to return information about the ordering of values once should provide a speedup for these operations.
> > 
> > In the interest of cleaning up the semantics of Comparable types of all shapes and sizes and their uses in the Swift Standard Library, this proposal is going to re-arrange the requirements of the Comparable and Equatable protocols.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed) solution
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt;Equatable](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt;Equatable)
> > 
> > The interface of Equatable remains unchanged under this proposal. Equatable types should still respect the equivalence laws of reflexivity (a == a), symmetry (a == b iff b == a), and transitivity (if a == b and b == c, then a == c). Further, != remains a top-level binary operator for which a != b iff !(a == b).
> > 
> > Types containing properties inessential to equality, however, are allowed to retain their notion of identity. For example Array's capacity isn't considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
> > 
> > IEEE-754 floating point numbers are allowed to break the reflexivity law by defining that .nan != x for any value of x, which is the standard behaviour documented in IEEE-754 and implemented the same way in other programming languages.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt;Comparable](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt;Comparable)
> > 
> > The Comparable protocol will now require (without default implementation provided) a single operator definition: \<=\> — the comparison operator. From this, all other comparison operators will be derived so as to respect the total order semantics of Comparable:
> > 
> > To maintain compatibility with IEEE-754, the interface of Comparable also contains as customization points the operators \<, \<=, and == (derived from Equatable) as well as the static binary functions \_min(\_:\_:) and \_max(\_:\_:). User-defined types are recommended against overriding the default implementations.
> > 
> > The uncustomizable top-level binary comparison operators a \> b and a \>= b are implemented as synonyms to b \< aand b \<= a, respectively.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard) Library
> > 
> > Unlike a previous revision of this proposal, standard library algorithms specific to FloatingPoint remain unchanged.
> > 
> > Overloads of \<=\> for tuples of Comparable elements are provided up to a library-defined arity.
> > 
> > The intent of this proposal is to later augment the standard library so that functions that take an ordering predicate by: (T, T) -\> Bool will have an overload ordering: (T, T) -\> Ordering that will provide a — potentially — more efficient implementation. A list of such functions is provided in Future directions.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed) design
> > 
> > The Comparable protocol will be amended by taking away \> and \>=, adding customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the ordering operator \<=\> that makes use of the Ordering enum defined below.
> > 
> > enum Ordering : Equatable {  
> > &nbsp;&nbsp;case ascending  
> > &nbsp;&nbsp;case equal  
> > &nbsp;&nbsp;case descending  
> > }
> > 
> > infix operator \<=\> { associativity none precedence 130 }
> > 
> > public protocol Comparable : Equatable {  
> > &nbsp;&nbsp;// Implementation required:  
> > &nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering
> > 
> > &nbsp;&nbsp;// Default implementations provided:  
> > &nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
> > &nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > &nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > }  
> > The \<=\> operator defines a relationship between == and \<=\> such that a == b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics in the way of IEEE-754. Likewise, it should hold that (a \<=\> b) == .ascending iff a \< b, and (a \<=\> b) != .descending iff a \<= b.
> > 
> > The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the right-hand side to retain identity, as presently explained in this comment \<[https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;\](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C). Making them customization points of Comparable, we get to fix their behaviour in the presense of unorderable values (SR-1011 \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).
> > 
> > Most user types should only implement \<=\> and leave the other members of Equatable and Comparable to their default implementations. Note that even == has a sane default implementation if Self is made Comparable:
> > 
> > // Default implementations, which should be used for most Comparable types:  
> > extension Comparable {  
> > &nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
> > &nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
> > &nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
> > &nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
> > &nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
> > }
> > 
> > // Unoverridable top-level operators and functions for Comparable:  
> > public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }  
> > public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }  
> > public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }  
> > public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling) of floating point comparisons
> > 
> > The following text is written in terms of Double but other floating-point types (Float, Float80) are proposed the same treatment.
> > 
> > The IEEE-754 floating point specification has two oddities when it comes to orderability: there are two zeros (0.0 and -0.0) which are considered equal to each other, and there are multiple not-a-number values x for which x.isNaN == true and x != y with any value of y, even x itself. (Remark: the most common NaN value is obtained by the static property Double.nan.)
> > 
> > The interface of Comparable is designed so that \<=\> alone is able to produce a total order among all possible Doublevalues, sorting negative NaNs less than any other values, and positive NaNs greater than any other. Otherwise, within the range of totally ordered floating point values, -Double.infinity ... Double.infinity, the result of a \<=\> b remains in full agreement with the laws of a \< b, a \<= b, and a == b.
> > 
> > The suggested implementation of Double : Comparable makes \<=\> distinguish between every different bitPatternof NaN:
> > 
> > extension Double : Comparable {  
> > &nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
> > &nbsp;&nbsp;}  
> > &nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
> > &nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
> > &nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
> > &nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
> > &nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
> > }
> > 
> > // Likewise:  
> > extension Float : Comparable { ... }  
> > extension Float80 : Comparable { ... }  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples) and order reversal
> > 
> > Due to missing language support, tuples of Comparable elements cannot be Comparable themselves, but in the spirit of SE-0015 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;), such tuples are given their overloads of \<=\> up to a standard library defined maximum arity:
> > 
> > public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
> > &nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
> > &nbsp;&nbsp;if a != .equal { return a }  
> > &nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
> > &nbsp;&nbsp;if b != .equal { return b }  
> > &nbsp;&nbsp;return .equal  
> > }
> > 
> > // Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.  
> > To simplify the reversal of a given ordering operation, two members of Ordering are provided in an extension:
> > 
> > extension Ordering {  
> > &nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
> > &nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
> > &nbsp;&nbsp;{  
> > &nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;public var reversed: Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;switch self {  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;}  
> > }  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt;Foundation](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt;Foundation)
> > 
> > In addition, Foundation code will now bridge NSComparisonResult to Ordering allowing for a fluid, natural, and safe API.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact) on existing code
> > 
> > The biggest drawback of the proposed design is the large surface area of Comparable's interface, as well as the possibility of overriding the comparison operators by mistake. On the other hand, since the required \<=\> operator is new and affects all users porting their previously Comparable data types to Swift 3, we can use documentation to suggest removing the redundant (and possibly faulty) implementations of other comparison operators.
> > 
> > Existing Equatable but not Comparable types that define an equivalence relation with == will remain unchanged.
> > 
> > Existing Comparable types that define a total ordering with \< will need to implement \<=\> and should remove their existing implementation of any comparison operators, including ==. All other existing Comparable types should implement \<=\> that provides a total ordering, or should drop their Comparable conformance.
> > 
> > Before:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int  
> > }
> > 
> > func ==(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;return lhs.year == rhs.year  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
> > }
> > 
> > func \<(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;if lhs.year != rhs.year {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
> > &nbsp;&nbsp;} else if lhs.month != rhs.month {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
> > &nbsp;&nbsp;} else {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
> > &nbsp;&nbsp;}  
> > }  
> > After, using the tuple overload of \<=\>:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int
> > 
> > &nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;// // Explicit version:  
> > &nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
> > &nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
> > &nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
> > &nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
> > &nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
> > &nbsp;&nbsp;// }  
> > }  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives) considered
> > 
> > A previous design of this proposal suggested a strict total order upon Comparable. While that would make generic algorithms more correct, the definition ended up fighting against the expected behaviour of floating point numbers.
> > 
> > An alternative design that better matches the existing arithmetic-related protocols in Swift is one that uses a member function.
> > 
> > public protocol Comparable: Equatable {  
> > &nbsp;&nbsp;func compare(to: Self) -\> Ordering  
> > }  
> > However, while this API does read better than an operator, we believe that this imposes a number of artificial restrictions (especially in light of SE-0091 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;\](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;%5C))
> > 
> > There is no way to use Comparable.compare as a higher-order function in a non-generic context.  
> > If a member is desired, it can be provided in a protocol extension and defined in terms of the ordering operator; to each according to their need.  
> > The existing tuple overloads cannot be expressed with a member function.  
> > One other that Rust has adopted is the inclusion of PartialEquatable and PartialComparable as ancestors of their flavor of Equatable and Comparable . Having protocols to organize and catalogue types that can only guarantee partial equivalence and ordering relations is a good approach for modularity but clutters the standard library with two new protocols for which few useful algorithms could be written against.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future) directions
> > 
> > That the default sort() compares by \< and not \<=\> should be considered a bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved in the presense of NaN. However, given that the current behaviour is to produce an unspecified order, the fix is additive and can be slipped past Swift 3.
> > 
> > With \<=\> in place, several present and future standard library algorithms involving a \<T : Comparable\> requirement will possibly benefit from knowing the total ordering of two operands at once. This is a list of possible such functions (taking Array as example), to be proposed separately as an additive change:
> > 
> > extension Array {  
> > &nbsp;&nbsp;// Sorting
> > 
> > &nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
> > &nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]
> > 
> > &nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
> > &nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
> > &nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
> > &nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
> > &nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>
> > 
> > &nbsp;&nbsp;// Binary search
> > 
> > &nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
> > &nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
> > }

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [July 25, 2016, 6:23pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/3 "2016-07-25T18:23:58Z")

</div>

Pyry, this proposal looks great to me. My one question is, will I be able  
to write `someCollection.sort(.ascending)` and get the expected  
result? (This could be an additive future direction.)

Stephen, what is your rationale for wanting `\<=\>` to identify NaN values  
with different payloads as `.equal`?

I believe the IEEE 754 total order specification uses the bit-pattern just  
as Pyry’s proposal does, and there is value is adhering to the standard.  
Besides, if someone intentionally wishes to consider all NaN values as  
equivalent they can use `.isNaN` (or even map them to .nan first for  
uniformity).

Nevin

> **···**
>
> On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution \< swift-evolution@swift.org\> wrote:
> 
> > Hi Pyry —
> > 
> > Dave and I spent some time discussing the details of how this applies to  
> > floating point earlier today. We’re now in agreement that \<=\> should treat  
> > -0 and +0 as distinct, and treat all NaNs as .equal. There are three  
> > motivating considerations:
> > 
> > 1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that  
> > can produce both of them. In the parlance of IEEE 754, for any rounding  
> > mode, the sets of real values that round to them are disjoint. Because of  
> > this, if -0 and +0 appear as members of a set, or as keys in a dictionary,  
> > they necessarily are the result of distinct computations or data.
> > 
> > 2. Substitutability. Adopting these semantics means that if `x \<=\> y` is  
> > `.equal`, `f(x) \<=\> f(y)` is also `.equal` for any computation `f(x)` that  
> > depends on the represented value (as opposed to the encoding) of its  
> > argument.
> > 
> > 3. 754 defines four “specification levels”, or models:
> > 
> > - Level 1: The two-point compactification of the reals, or “extended real  
> > numbers”.  
> > - Level 2: The set of representable floating-point data: {-inf … -0} union  
> > { 0 … inf } union { NaN }.  
> > - Level 3: The set of representations of floating-point data:  
> > sign-exponent-significand triples, +/-inf, qNaN, sNaN.  
> > - Level 4: Floating-point encodings (bit patterns).
> > 
> > The `\<=\>` semantics we propose constitute a total order on level 2, which  
> > is the computable model closest to the (reasonably familiar) extended real  
> > numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s  
> > land between levels 1 and 2.
> > 
> > Thanks,  
> > – Steve
> > 
> > On Jul 25, 2016, at 7:41 AM, Pyry Jahkola \<pyry.jahkola@iki.fi\> wrote:
> > 
> > Since we're running short on time, and the previous discussion thread  
> > diverged, here's my attempt to fix the Comparable protocol.
> > 
> > \*Pull request:\* [Formalized ordering by pyrtsa · Pull Request #464 · apple/swift-evolution · GitHub](https://github.com/apple/swift-evolution/pull/464)
> > 
> > TL;DR:
> > 
> > 1. Equatable remains unchanged, while Comparable bloats a bit to support  
> > several use cases.  
> > 2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal to  
> > minus zero.  
> > 3. Types are not strictly required to become totally ordered, even if it's  
> > strongly recommended.
> > 
> > — — —
> > 
> > I simply can't see how a pure total order version of Comparable would fit  
> > the standard way floating point values are expected to behave. However, I  
> > think we can reach a satisfactory conclusion, one that involves no crashing  
> > in the standard library, which is what I previously suggested.
> > 
> > What I'm trying to fix is so that all operations listed in  
> > [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws  
> > for types without incomparable values, and that types with weaker order can  
> > still work in \*some\* well-defined way outside their totally ordered range.
> > 
> > PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for  
> > time is tight. I can pull back or revise the proposal if you don't want to  
> > be involved.
> > 
> > — Pyry
> > 
> > Formalized Ordering
> > 
> > &nbsp;&nbsp;&nbsp;- Proposal: SE-NNNN  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
> > &nbsp;&nbsp;&nbsp;- Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
> > &nbsp;&nbsp;&nbsp;- Status: Awaiting review  
> > &nbsp;&nbsp;&nbsp;- Review manager: TBD
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt);  
> > Introduction
> > 
> > This proposal cleans up the semantics of ordering relations in the  
> > standard library. Our goal is to formalize the total ordering semantics of  
> > the Comparable protocol and still provide accessible ordering definitions  
> > for types without total ordering semantics.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt);  
> > Motivation
> > 
> > The standard comparison operators have an intuitive meaning to  
> > programmers. Swift encourages encoding that in an implementation of  
> > Comparable that respects the rules of a total order  
> > \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes  
> > advantage of these rules to provide consistent implementations for sorting  
> > and searching generic collections of Comparable types.
> > 
> > Not all types behave so well in this framework, unfortunately. There are  
> > cases where the semantics of a total order cannot apply and still maintain  
> > the traditional definition of “comparison” over these types. Take, for  
> > example, sorting an array of Float s. Today, Float ‘s instance of  
> > Comparable follows IEEE-754 and returns false for all comparisons of NaN .  
> > In order to sort this array, NaN s are considered outside the domain of \< ,  
> > and the order of a “sorted” array containing them is undefined.
> > 
> > In addition, generic algorithms in the Swift Standard Library that make  
> > use of the current Comparable protocol may have to make twice as many  
> > comparisons to request the ordering of values with respect to each other  
> > than they should. Having a central operation to return information about  
> > the ordering of values once should provide a speedup for these operations.
> > 
> > In the interest of cleaning up the semantics of Comparable types of all  
> > shapes and sizes and their uses in the Swift Standard Library, this  
> > proposal is going to re-arrange the requirements of the Comparable and  
> > Equatable protocols.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed)  
> > solution  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt);  
> > Equatable
> > 
> > The interface of Equatable remains unchanged under this proposal.  
> > Equatable types should still respect the equivalence laws of \*reflexivity\*  
> > (a == a), \*symmetry\* (a == b iff b == a), and \*transitivity\* (if a == b  
> > and b == c, then a == c). Further, != remains a top-level binary  
> > operator for which a != b iff !(a == b).
> > 
> > Types containing properties \*inessential to equality\*, however, are  
> > allowed to retain their notion of identity. For example Array's capacity isn't  
> > considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign  
> > != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
> > 
> > IEEE-754 floating point numbers are allowed to break the reflexivity law  
> > by defining that .nan != x for any value of x, which is the standard  
> > behaviour documented in IEEE-754 and implemented the same way in other  
> > programming languages.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt);  
> > Comparable
> > 
> > The Comparable protocol will now require (without default implementation  
> > provided) a single operator definition: \<=\> — the comparison operator.  
> > From this, all other comparison operators will be derived so as to respect  
> > the total order semantics of Comparable:
> > 
> > To maintain compatibility with IEEE-754, the interface of Comparable also  
> > contains as customization points the operators \<, \<=, and == (derived  
> > from Equatable) as well as the static binary functions \_min(\_:\_:) and  
> > \_max(\_:\_:). User-defined types are recommended against overriding the  
> > default implementations.
> > 
> > The uncustomizable top-level binary comparison operators a \> b and a \>= b are  
> > implemented as synonyms to b \< aand b \<= a, respectively.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard)  
> > Library
> > 
> > Unlike a previous revision of this proposal, standard library algorithms  
> > specific to FloatingPoint remain unchanged.
> > 
> > Overloads of \<=\> for tuples of Comparable elements are provided up to a  
> > library-defined arity.
> > 
> > The intent of this proposal is to later augment the standard library so  
> > that functions that take an ordering predicate by: (T, T) -\> Bool will  
> > have an overload ordering: (T, T) -\> Ordering that will provide a —  
> > potentially — more efficient implementation. A list of such functions is  
> > provided in Future directions.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed)  
> > design
> > 
> > The Comparable protocol will be amended by taking away \> and \>=, adding  
> > customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the  
> > ordering operator \<=\> that makes use of the Ordering enum defined below.
> > 
> > enum Ordering : Equatable {  
> > &nbsp;&nbsp;case ascending  
> > &nbsp;&nbsp;case equal  
> > &nbsp;&nbsp;case descending  
> > }  
> > infix operator \<=\> { associativity none precedence 130 }  
> > public protocol Comparable : Equatable {  
> > &nbsp;&nbsp;// Implementation required:  
> > &nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering
> > 
> > &nbsp;&nbsp;// Default implementations provided:  
> > &nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
> > &nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > &nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > }
> > 
> > The \<=\> operator defines a relationship between == and \<=\> such that a ==  
> > b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics in  
> > the way of IEEE-754. Likewise, it should hold that (a \<=\> b) == .ascending  
> > iff a \< b, and (a \<=\> b) != .descending iff a \<= b.
> > 
> > The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or  
> > greater of the two operands, respectively, while in case of equal  
> > arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the  
> > right-hand side to retain identity, as presently explained in this comment  
> > \<[https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;\](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C).  
> > Making them customization points of Comparable, we get to fix their  
> > behaviour in the presense of unorderable values (SR-1011  
> > \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).
> > 
> > Most user types should only implement \<=\> and leave the other members of  
> > Equatable and Comparable to their default implementations. Note that even  
> > == has a sane default implementation if Self is made Comparable:
> > 
> > // Default implementations, which should be used for most Comparable types:extension Comparable {  
> > &nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
> > &nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
> > &nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
> > &nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
> > &nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
> > }  
> > // Unoverridable top-level operators and functions for Comparable:public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling)  
> > of floating point comparisons
> > 
> > \*The following text is written in terms of Double but other floating-point  
> > types (Float, Float80) are proposed the same treatment.\*
> > 
> > The IEEE-754 floating point specification has two oddities when it comes  
> > to orderability: there are two zeros (0.0 and -0.0) which are considered  
> > equal to each other, and there are \*multiple\* not-a-number values x for  
> > which x.isNaN == true and x != y with any value of y, even x itself.  
> > (Remark: the most common NaN value is obtained by the static property  
> > Double.nan.)
> > 
> > The interface of Comparable is designed so that \<=\> alone is able to  
> > produce a total order among all possible Doublevalues, sorting negative  
> > NaNs less than any other values, and positive NaNs greater than any other.  
> > Otherwise, within the range of totally ordered floating point values, -Double.infinity  
> > ... Double.infinity, the result of a \<=\> b remains in full agreement with  
> > the laws of a \< b, a \<= b, and a == b.
> > 
> > The suggested implementation of Double : Comparable makes \<=\> distinguish  
> > between every different bitPatternof NaN:
> > 
> > extension Double : Comparable {  
> > &nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
> > &nbsp;&nbsp;}  
> > &nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
> > &nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
> > &nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
> > &nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
> > &nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
> > }  
> > // Likewise:extension Float : Comparable { ... }extension Float80 : Comparable { ... }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples)  
> > and order reversal
> > 
> > Due to missing language support, tuples of Comparable elements cannot be  
> > Comparable themselves, but in the spirit of SE-0015  
> > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;),  
> > such tuples are given their overloads of \<=\> up to a standard library  
> > defined maximum arity:
> > 
> > public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
> > &nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
> > &nbsp;&nbsp;if a != .equal { return a }  
> > &nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
> > &nbsp;&nbsp;if b != .equal { return b }  
> > &nbsp;&nbsp;return .equal  
> > }  
> > // Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.
> > 
> > To simplify the reversal of a given ordering operation, two members of  
> > Ordering are provided in an extension:
> > 
> > extension Ordering {  
> > &nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
> > &nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
> > &nbsp;&nbsp;{  
> > &nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;public var reversed: Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;switch self {  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;}  
> > }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt);  
> > Foundation
> > 
> > In addition, Foundation code will now bridge NSComparisonResult to  
> > Ordering allowing for a fluid, natural, and safe API.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact)  
> > on existing code
> > 
> > The biggest drawback of the proposed design is the large surface area of  
> > Comparable's interface, as well as the possibility of overriding the  
> > comparison operators by mistake. On the other hand, since the required \<=\> operator  
> > is new and affects all users porting their previously Comparable data  
> > types to Swift 3, we can use documentation to suggest removing the  
> > redundant (and possibly faulty) implementations of other comparison  
> > operators.
> > 
> > Existing Equatable but not Comparable types that define an equivalence  
> > relation with == will remain unchanged.
> > 
> > Existing Comparable types that define a total ordering with \< will need  
> > to implement \<=\> and should remove their existing implementation of any  
> > comparison operators, including ==. All other existing Comparable types  
> > should implement \<=\> that provides a total ordering, or should drop their  
> > Comparable conformance.
> > 
> > Before:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int  
> > }  
> > func ==(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;return lhs.year == rhs.year  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
> > }  
> > func \<(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;if lhs.year != rhs.year {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
> > &nbsp;&nbsp;} else if lhs.month != rhs.month {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
> > &nbsp;&nbsp;} else {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
> > &nbsp;&nbsp;}  
> > }
> > 
> > After, using the tuple overload of \<=\>:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int
> > 
> > &nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;// // Explicit version:  
> > &nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
> > &nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
> > &nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
> > &nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
> > &nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
> > &nbsp;&nbsp;// }  
> > }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives)  
> > considered
> > 
> > A previous design of this proposal suggested a strict total order upon  
> > Comparable. While that would make generic algorithms more correct, the  
> > definition ended up fighting against the expected behaviour of floating  
> > point numbers.
> > 
> > An alternative design that better matches the existing arithmetic-related  
> > protocols in Swift is one that uses a member function.
> > 
> > public protocol Comparable: Equatable {  
> > &nbsp;&nbsp;func compare(to: Self) -\> Ordering  
> > }
> > 
> > However, while this API does read better than an operator, we believe that  
> > this imposes a number of artificial restrictions (especially in light of  
> > SE-0091  
> > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt);  
> > )
> > 
> > &nbsp;&nbsp;&nbsp;1. There is no way to use Comparable.compare as a higher-order  
> > &nbsp;&nbsp;&nbsp;function in a non-generic context.  
> > &nbsp;&nbsp;&nbsp;2. If a member is desired, it can be provided in a protocol extension  
> > &nbsp;&nbsp;&nbsp;and defined in terms of the ordering operator; to each according to their  
> > &nbsp;&nbsp;&nbsp;need.  
> > &nbsp;&nbsp;&nbsp;3. The existing tuple overloads cannot be expressed with a member  
> > &nbsp;&nbsp;&nbsp;function.
> > 
> > One other that Rust has adopted is the inclusion of PartialEquatable and  
> > PartialComparable as ancestors of their flavor of Equatable and Comparable .  
> > Having protocols to organize and catalogue types that can only guarantee  
> > partial equivalence and ordering relations is a good approach for  
> > modularity but clutters the standard library with two new protocols for  
> > which few useful algorithms could be written against.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future)  
> > directions
> > 
> > That the default sort() compares by \< and not \<=\> should be considered a  
> > bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved  
> > in the presense of NaN. However, given that the current behaviour is to  
> > produce an unspecified order, the fix is additive and can be slipped past  
> > Swift 3.
> > 
> > With \<=\> in place, several present and future standard library algorithms  
> > involving a \<T : Comparable\> requirement will possibly benefit from  
> > knowing the total ordering of two operands at once. This is a list of  
> > possible such functions (taking Array as example), to be proposed  
> > separately as an additive change:
> > 
> > extension Array {  
> > &nbsp;&nbsp;// Sorting
> > 
> > &nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
> > &nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]
> > 
> > &nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
> > &nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
> > &nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
> > &nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
> > &nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>
> > 
> > &nbsp;&nbsp;// Binary search
> > 
> > &nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
> > &nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
> > }
> > 
> > \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
> > swift-evolution mailing list  
> > swift-evolution@swift.org  
> > [https://lists.swift.org/mailman/listinfo/swift-evolution](https://lists.swift.org/mailman/listinfo/swift-evolution)

---

<div class="post-metadata">

**Author:** ![Stephen\_Canon](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/stephen_canon/32/7220_2.png) [@Stephen\_Canon](https://forums.swift.org/u/Stephen_Canon)\
**Post date:** [July 25, 2016, 6:52pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/4 "2016-07-25T18:52:46Z")

</div>

First, this is orthogonal to "adhering to the standard". isTotallyOrdered( ) provides the total order predicate required by IEEE 754. The standard has no opinion about whether or not `\<=\>` is bound to that predicate.

Personally, I would be OK with using the `isTotallyOrdered` semantics for `\<=\>`. However, it leads to some behavior that would be surprising for novices: x is NaN, and a set S is { 1, 2, NaN }, but S does not contain x. I am skeptical that the distinction between NaN payloads is salient \*for generic code written on Comparable types\*. It \*is\* salient for some (rare!) floating-point specific code, but `isTotallyOrdered` is available for floating-point types.

There’s also the issue that if we want to be able to point at IEEE 754 and say “\<=\> implements a total order on Level N”, distinguishing distinct NaNs has consequences for other values. In particular, it means that a decimal type should distinguish between 1e0 and 10e-1, because it would necessarily be an ordering on level 3 or 4. For { 1, 20 } to not contain 2e1 seems highly dubious to me.

– Steve

> **···**
>
> > On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky \<nevin.brackettrozinsky@gmail.com\> wrote:
> > 
> > Pyry, this proposal looks great to me. My one question is, will I be able to write `someCollection.sort(.ascending)` and get the expected result? (This could be an additive future direction.)
> > 
> > Stephen, what is your rationale for wanting `\<=\>` to identify NaN values with different payloads as `.equal`?
> > 
> > I believe the IEEE 754 total order specification uses the bit-pattern just as Pyry’s proposal does, and there is value is adhering to the standard. Besides, if someone intentionally wishes to consider all NaN values as equivalent they can use `.isNaN` (or even map them to .nan first for uniformity).
> > 
> > Nevin
> > 
> > On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution \<swift-evolution@swift.org \<mailto:swift-evolution@swift.org\>\> wrote:  
> > Hi Pyry —
> > 
> > Dave and I spent some time discussing the details of how this applies to floating point earlier today. We’re now in agreement that \<=\> should treat -0 and +0 as distinct, and treat all NaNs as .equal. There are three motivating considerations:
> > 
> > 1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that can produce both of them. In the parlance of IEEE 754, for any rounding mode, the sets of real values that round to them are disjoint. Because of this, if -0 and +0 appear as members of a set, or as keys in a dictionary, they necessarily are the result of distinct computations or data.
> > 
> > 2. Substitutability. Adopting these semantics means that if `x \<=\> y` is `.equal`, `f(x) \<=\> f(y)` is also `.equal` for any computation `f(x)` that depends on the represented value (as opposed to the encoding) of its argument.
> > 
> > 3. 754 defines four “specification levels”, or models:
> > 
> > &nbsp;&nbsp;- Level 1: The two-point compactification of the reals, or “extended real numbers”.  
> > &nbsp;&nbsp;- Level 2: The set of representable floating-point data: {-inf … -0} union { 0 … inf } union { NaN }.  
> > &nbsp;&nbsp;- Level 3: The set of representations of floating-point data: sign-exponent-significand triples, +/-inf, qNaN, sNaN.  
> > &nbsp;&nbsp;- Level 4: Floating-point encodings (bit patterns).
> > 
> > The `\<=\>` semantics we propose constitute a total order on level 2, which is the computable model closest to the (reasonably familiar) extended real numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s land between levels 1 and 2.
> > 
> > Thanks,  
> > – Steve
> > 
> > > On Jul 25, 2016, at 7:41 AM, Pyry Jahkola \<pyry.jahkola@iki.fi \<mailto:pyry.jahkola@iki.fi\>\> wrote:
> > > 
> > > Since we're running short on time, and the previous discussion thread diverged, here's my attempt to fix the Comparable protocol.
> > > 
> > > Pull request: [https://github.com/apple/swift-evolution/pull/464](https://github.com/apple/swift-evolution/pull/464)
> > > 
> > > TL;DR:
> > > 
> > > 1. Equatable remains unchanged, while Comparable bloats a bit to support several use cases.  
> > > 2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal to minus zero.  
> > > 3. Types are not strictly required to become totally ordered, even if it's strongly recommended.
> > > 
> > > — — —
> > > 
> > > I simply can't see how a pure total order version of Comparable would fit the standard way floating point values are expected to behave. However, I think we can reach a satisfactory conclusion, one that involves no crashing in the standard library, which is what I previously suggested.
> > > 
> > > What I'm trying to fix is so that all operations listed in [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws for types without incomparable values, and that types with weaker order can still work in some well-defined way outside their totally ordered range.
> > > 
> > > PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for time is tight. I can pull back or revise the proposal if you don't want to be involved.
> > > 
> > > — Pyry
> > > 
> > > Formalized Ordering
> > > 
> > > Proposal: SE-NNNN \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
> > > Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller \<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins \<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola \<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
> > > Status: Awaiting review  
> > > Review manager: TBD  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt;Introduction](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt;Introduction)
> > > 
> > > This proposal cleans up the semantics of ordering relations in the standard library. Our goal is to formalize the total ordering semantics of the Comparable protocol and still provide accessible ordering definitions for types without total ordering semantics.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt;Motivation](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt;Motivation)
> > > 
> > > The standard comparison operators have an intuitive meaning to programmers. Swift encourages encoding that in an implementation of Comparable that respects the rules of a total order \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes advantage of these rules to provide consistent implementations for sorting and searching generic collections of Comparable types.
> > > 
> > > Not all types behave so well in this framework, unfortunately. There are cases where the semantics of a total order cannot apply and still maintain the traditional definition of “comparison” over these types. Take, for example, sorting an array of Float s. Today, Float ‘s instance of Comparable follows IEEE-754 and returns false for all comparisons of NaN . In order to sort this array, NaN s are considered outside the domain of \< , and the order of a “sorted” array containing them is undefined.
> > > 
> > > In addition, generic algorithms in the Swift Standard Library that make use of the current Comparable protocol may have to make twice as many comparisons to request the ordering of values with respect to each other than they should. Having a central operation to return information about the ordering of values once should provide a speedup for these operations.
> > > 
> > > In the interest of cleaning up the semantics of Comparable types of all shapes and sizes and their uses in the Swift Standard Library, this proposal is going to re-arrange the requirements of the Comparable and Equatable protocols.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed) solution
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt;Equatable](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt;Equatable)
> > > 
> > > The interface of Equatable remains unchanged under this proposal. Equatable types should still respect the equivalence laws of reflexivity (a == a), symmetry (a == b iff b == a), and transitivity (if a == b and b == c, then a == c). Further, != remains a top-level binary operator for which a != b iff !(a == b).
> > > 
> > > Types containing properties inessential to equality, however, are allowed to retain their notion of identity. For example Array's capacity isn't considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
> > > 
> > > IEEE-754 floating point numbers are allowed to break the reflexivity law by defining that .nan != x for any value of x, which is the standard behaviour documented in IEEE-754 and implemented the same way in other programming languages.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt;Comparable](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt;Comparable)
> > > 
> > > The Comparable protocol will now require (without default implementation provided) a single operator definition: \<=\> — the comparison operator. From this, all other comparison operators will be derived so as to respect the total order semantics of Comparable:
> > > 
> > > To maintain compatibility with IEEE-754, the interface of Comparable also contains as customization points the operators \<, \<=, and == (derived from Equatable) as well as the static binary functions \_min(\_:\_:) and \_max(\_:\_:). User-defined types are recommended against overriding the default implementations.
> > > 
> > > The uncustomizable top-level binary comparison operators a \> b and a \>= b are implemented as synonyms to b \< aand b \<= a, respectively.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard) Library
> > > 
> > > Unlike a previous revision of this proposal, standard library algorithms specific to FloatingPoint remain unchanged.
> > > 
> > > Overloads of \<=\> for tuples of Comparable elements are provided up to a library-defined arity.
> > > 
> > > The intent of this proposal is to later augment the standard library so that functions that take an ordering predicate by: (T, T) -\> Bool will have an overload ordering: (T, T) -\> Ordering that will provide a — potentially — more efficient implementation. A list of such functions is provided in Future directions.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed) design
> > > 
> > > The Comparable protocol will be amended by taking away \> and \>=, adding customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the ordering operator \<=\> that makes use of the Ordering enum defined below.
> > > 
> > > enum Ordering : Equatable {  
> > > &nbsp;&nbsp;case ascending  
> > > &nbsp;&nbsp;case equal  
> > > &nbsp;&nbsp;case descending  
> > > }
> > > 
> > > infix operator \<=\> { associativity none precedence 130 }
> > > 
> > > public protocol Comparable : Equatable {  
> > > &nbsp;&nbsp;// Implementation required:  
> > > &nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering
> > > 
> > > &nbsp;&nbsp;// Default implementations provided:  
> > > &nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
> > > &nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
> > > &nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
> > > &nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > > &nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > > }  
> > > The \<=\> operator defines a relationship between == and \<=\> such that a == b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics in the way of IEEE-754. Likewise, it should hold that (a \<=\> b) == .ascending iff a \< b, and (a \<=\> b) != .descending iff a \<= b.
> > > 
> > > The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or greater of the two operands, respectively, while in case of equal arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the right-hand side to retain identity, as presently explained in this comment \<[https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;\](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C). Making them customization points of Comparable, we get to fix their behaviour in the presense of unorderable values (SR-1011 \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).
> > > 
> > > Most user types should only implement \<=\> and leave the other members of Equatable and Comparable to their default implementations. Note that even == has a sane default implementation if Self is made Comparable:
> > > 
> > > // Default implementations, which should be used for most Comparable types:  
> > > extension Comparable {  
> > > &nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
> > > &nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
> > > &nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
> > > &nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
> > > &nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
> > > }
> > > 
> > > // Unoverridable top-level operators and functions for Comparable:  
> > > public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }  
> > > public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }  
> > > public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }  
> > > public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling) of floating point comparisons
> > > 
> > > The following text is written in terms of Double but other floating-point types (Float, Float80) are proposed the same treatment.
> > > 
> > > The IEEE-754 floating point specification has two oddities when it comes to orderability: there are two zeros (0.0 and -0.0) which are considered equal to each other, and there are multiple not-a-number values x for which x.isNaN == true and x != y with any value of y, even x itself. (Remark: the most common NaN value is obtained by the static property Double.nan.)
> > > 
> > > The interface of Comparable is designed so that \<=\> alone is able to produce a total order among all possible Doublevalues, sorting negative NaNs less than any other values, and positive NaNs greater than any other. Otherwise, within the range of totally ordered floating point values, -Double.infinity ... Double.infinity, the result of a \<=\> b remains in full agreement with the laws of a \< b, a \<= b, and a == b.
> > > 
> > > The suggested implementation of Double : Comparable makes \<=\> distinguish between every different bitPatternof NaN:
> > > 
> > > extension Double : Comparable {  
> > > &nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
> > > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
> > > &nbsp;&nbsp;}  
> > > &nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
> > > &nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
> > > &nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
> > > &nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
> > > &nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
> > > }
> > > 
> > > // Likewise:  
> > > extension Float : Comparable { ... }  
> > > extension Float80 : Comparable { ... }  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples) and order reversal
> > > 
> > > Due to missing language support, tuples of Comparable elements cannot be Comparable themselves, but in the spirit of SE-0015 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;), such tuples are given their overloads of \<=\> up to a standard library defined maximum arity:
> > > 
> > > public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
> > > &nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
> > > &nbsp;&nbsp;if a != .equal { return a }  
> > > &nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
> > > &nbsp;&nbsp;if b != .equal { return b }  
> > > &nbsp;&nbsp;return .equal  
> > > }
> > > 
> > > // Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.  
> > > To simplify the reversal of a given ordering operation, two members of Ordering are provided in an extension:
> > > 
> > > extension Ordering {  
> > > &nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
> > > &nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
> > > &nbsp;&nbsp;{  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
> > > &nbsp;&nbsp;}
> > > 
> > > &nbsp;&nbsp;public var reversed: Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;switch self {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
> > > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > > &nbsp;&nbsp;}  
> > > }  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt;Foundation](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt;Foundation)
> > > 
> > > In addition, Foundation code will now bridge NSComparisonResult to Ordering allowing for a fluid, natural, and safe API.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact) on existing code
> > > 
> > > The biggest drawback of the proposed design is the large surface area of Comparable's interface, as well as the possibility of overriding the comparison operators by mistake. On the other hand, since the required \<=\> operator is new and affects all users porting their previously Comparable data types to Swift 3, we can use documentation to suggest removing the redundant (and possibly faulty) implementations of other comparison operators.
> > > 
> > > Existing Equatable but not Comparable types that define an equivalence relation with == will remain unchanged.
> > > 
> > > Existing Comparable types that define a total ordering with \< will need to implement \<=\> and should remove their existing implementation of any comparison operators, including ==. All other existing Comparable types should implement \<=\> that provides a total ordering, or should drop their Comparable conformance.
> > > 
> > > Before:
> > > 
> > > struct Date: Comparable {  
> > > &nbsp;&nbsp;let year: Int  
> > > &nbsp;&nbsp;let month: Int  
> > > &nbsp;&nbsp;let day: Int  
> > > }
> > > 
> > > func ==(lhs: Date, rhs: Date) -\> Bool {  
> > > &nbsp;&nbsp;return lhs.year == rhs.year  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
> > > }
> > > 
> > > func \<(lhs: Date, rhs: Date) -\> Bool {  
> > > &nbsp;&nbsp;if lhs.year != rhs.year {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
> > > &nbsp;&nbsp;} else if lhs.month != rhs.month {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
> > > &nbsp;&nbsp;} else {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
> > > &nbsp;&nbsp;}  
> > > }  
> > > After, using the tuple overload of \<=\>:
> > > 
> > > struct Date: Comparable {  
> > > &nbsp;&nbsp;let year: Int  
> > > &nbsp;&nbsp;let month: Int  
> > > &nbsp;&nbsp;let day: Int
> > > 
> > > &nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
> > > &nbsp;&nbsp;}
> > > 
> > > &nbsp;&nbsp;// // Explicit version:  
> > > &nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > > &nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
> > > &nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
> > > &nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
> > > &nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
> > > &nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
> > > &nbsp;&nbsp;// }  
> > > }  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives) considered
> > > 
> > > A previous design of this proposal suggested a strict total order upon Comparable. While that would make generic algorithms more correct, the definition ended up fighting against the expected behaviour of floating point numbers.
> > > 
> > > An alternative design that better matches the existing arithmetic-related protocols in Swift is one that uses a member function.
> > > 
> > > public protocol Comparable: Equatable {  
> > > &nbsp;&nbsp;func compare(to: Self) -\> Ordering  
> > > }  
> > > However, while this API does read better than an operator, we believe that this imposes a number of artificial restrictions (especially in light of SE-0091 \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;\](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt;%5C))
> > > 
> > > There is no way to use Comparable.compare as a higher-order function in a non-generic context.  
> > > If a member is desired, it can be provided in a protocol extension and defined in terms of the ordering operator; to each according to their need.  
> > > The existing tuple overloads cannot be expressed with a member function.  
> > > One other that Rust has adopted is the inclusion of PartialEquatable and PartialComparable as ancestors of their flavor of Equatable and Comparable . Having protocols to organize and catalogue types that can only guarantee partial equivalence and ordering relations is a good approach for modularity but clutters the standard library with two new protocols for which few useful algorithms could be written against.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future) directions
> > > 
> > > That the default sort() compares by \< and not \<=\> should be considered a bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved in the presense of NaN. However, given that the current behaviour is to produce an unspecified order, the fix is additive and can be slipped past Swift 3.
> > > 
> > > With \<=\> in place, several present and future standard library algorithms involving a \<T : Comparable\> requirement will possibly benefit from knowing the total ordering of two operands at once. This is a list of possible such functions (taking Array as example), to be proposed separately as an additive change:
> > > 
> > > extension Array {  
> > > &nbsp;&nbsp;// Sorting
> > > 
> > > &nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > > &nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
> > > &nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > > &nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]
> > > 
> > > &nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
> > > &nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
> > > &nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
> > > &nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
> > > &nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>
> > > 
> > > &nbsp;&nbsp;// Binary search
> > > 
> > > &nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
> > > &nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > > &nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > > &nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
> > > }
> > 
> > \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
> > swift-evolution mailing list  
> > swift-evolution@swift.org \<mailto:swift-evolution@swift.org\>  
> > [https://lists.swift.org/mailman/listinfo/swift-evolution](https://lists.swift.org/mailman/listinfo/swift-evolution)

---

<div class="post-metadata">

**Author:** ![Bjorn\_Forster](https://avatars.discourse-cdn.com/v4/letter/b/8c91f0/32.png) [@Bjorn\_Forster](https://forums.swift.org/u/Bjorn_Forster)\
**Post date:** [July 25, 2016, 3:51pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/5 "2016-07-25T15:51:34Z")

</div>

Hi Pyry,  
thanks for all the work you have put into this!  
Could you please explain for someone as simple minded as me why there is  
(or has to be) a difference in the implementation of \<, \<= and \>, \>=?  
Sorry, but I don't get into my head why there is/has to be a preference for  
one side. Could you or someone else point out (in the proposal) why there  
is a need/what is the reason for this?  
I assume that this might not be obvious to some other people on the first  
look, too.

Björn

> **···**
>
> On Mon, Jul 25, 2016 at 1:41 PM, Pyry Jahkola via swift-evolution \< swift-evolution@swift.org\> wrote:
> 
> > Since we're running short on time, and the previous discussion thread  
> > diverged, here's my attempt to fix the Comparable protocol.
> > 
> > \*Pull request:\* [https://github.com/apple/swift-evolution/pull/464](https://github.com/apple/swift-evolution/pull/464)
> > 
> > TL;DR:
> > 
> > 1. Equatable remains unchanged, while Comparable bloats a bit to support  
> > several use cases.  
> > 2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal to  
> > minus zero.  
> > 3. Types are not strictly required to become totally ordered, even if it's  
> > strongly recommended.
> > 
> > — — —
> > 
> > I simply can't see how a pure total order version of Comparable would fit  
> > the standard way floating point values are expected to behave. However, I  
> > think we can reach a satisfactory conclusion, one that involves no crashing  
> > in the standard library, which is what I previously suggested.
> > 
> > What I'm trying to fix is so that all operations listed in  
> > [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws  
> > for types without incomparable values, and that types with weaker order can  
> > still work in \*some\* well-defined way outside their totally ordered range.
> > 
> > PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for  
> > time is tight. I can pull back or revise the proposal if you don't want to  
> > be involved.
> > 
> > — Pyry
> > 
> > Formalized Ordering
> > 
> > &nbsp;&nbsp;&nbsp;- Proposal: SE-NNNN  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
> > &nbsp;&nbsp;&nbsp;- Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola  
> > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
> > &nbsp;&nbsp;&nbsp;- Status: Awaiting review  
> > &nbsp;&nbsp;&nbsp;- Review manager: TBD
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt);  
> > Introduction
> > 
> > This proposal cleans up the semantics of ordering relations in the  
> > standard library. Our goal is to formalize the total ordering semantics of  
> > the Comparable protocol and still provide accessible ordering definitions  
> > for types without total ordering semantics.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt);  
> > Motivation
> > 
> > The standard comparison operators have an intuitive meaning to  
> > programmers. Swift encourages encoding that in an implementation of  
> > Comparable that respects the rules of a total order  
> > \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes  
> > advantage of these rules to provide consistent implementations for sorting  
> > and searching generic collections of Comparable types.
> > 
> > Not all types behave so well in this framework, unfortunately. There are  
> > cases where the semantics of a total order cannot apply and still maintain  
> > the traditional definition of “comparison” over these types. Take, for  
> > example, sorting an array of Float s. Today, Float ‘s instance of  
> > Comparable follows IEEE-754 and returns false for all comparisons of NaN .  
> > In order to sort this array, NaN s are considered outside the domain of \< ,  
> > and the order of a “sorted” array containing them is undefined.
> > 
> > In addition, generic algorithms in the Swift Standard Library that make  
> > use of the current Comparable protocol may have to make twice as many  
> > comparisons to request the ordering of values with respect to each other  
> > than they should. Having a central operation to return information about  
> > the ordering of values once should provide a speedup for these operations.
> > 
> > In the interest of cleaning up the semantics of Comparable types of all  
> > shapes and sizes and their uses in the Swift Standard Library, this  
> > proposal is going to re-arrange the requirements of the Comparable and  
> > Equatable protocols.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed)  
> > solution  
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt);  
> > Equatable
> > 
> > The interface of Equatable remains unchanged under this proposal.  
> > Equatable types should still respect the equivalence laws of \*reflexivity\*  
> > (a == a), \*symmetry\* (a == b iff b == a), and \*transitivity\* (if a == b  
> > and b == c, then a == c). Further, != remains a top-level binary  
> > operator for which a != b iff !(a == b).
> > 
> > Types containing properties \*inessential to equality\*, however, are  
> > allowed to retain their notion of identity. For example Array's capacity isn't  
> > considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign  
> > != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
> > 
> > IEEE-754 floating point numbers are allowed to break the reflexivity law  
> > by defining that .nan != x for any value of x, which is the standard  
> > behaviour documented in IEEE-754 and implemented the same way in other  
> > programming languages.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt);  
> > Comparable
> > 
> > The Comparable protocol will now require (without default implementation  
> > provided) a single operator definition: \<=\> — the comparison operator.  
> > From this, all other comparison operators will be derived so as to respect  
> > the total order semantics of Comparable:
> > 
> > To maintain compatibility with IEEE-754, the interface of Comparable also  
> > contains as customization points the operators \<, \<=, and == (derived  
> > from Equatable) as well as the static binary functions \_min(\_:\_:) and  
> > \_max(\_:\_:). User-defined types are recommended against overriding the  
> > default implementations.
> > 
> > The uncustomizable top-level binary comparison operators a \> b and a \>= b are  
> > implemented as synonyms to b \< aand b \<= a, respectively.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard)  
> > Library
> > 
> > Unlike a previous revision of this proposal, standard library algorithms  
> > specific to FloatingPoint remain unchanged.
> > 
> > Overloads of \<=\> for tuples of Comparable elements are provided up to a  
> > library-defined arity.
> > 
> > The intent of this proposal is to later augment the standard library so  
> > that functions that take an ordering predicate by: (T, T) -\> Bool will  
> > have an overload ordering: (T, T) -\> Ordering that will provide a —  
> > potentially — more efficient implementation. A list of such functions is  
> > provided in Future directions.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed)  
> > design
> > 
> > The Comparable protocol will be amended by taking away \> and \>=, adding  
> > customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the  
> > ordering operator \<=\> that makes use of the Ordering enum defined below.
> > 
> > enum Ordering : Equatable {  
> > &nbsp;&nbsp;case ascending  
> > &nbsp;&nbsp;case equal  
> > &nbsp;&nbsp;case descending  
> > }  
> > infix operator \<=\> { associativity none precedence 130 }  
> > public protocol Comparable : Equatable {  
> > &nbsp;&nbsp;// Implementation required:  
> > &nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering
> > 
> > &nbsp;&nbsp;// Default implementations provided:  
> > &nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
> > &nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
> > &nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > &nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > }
> > 
> > The \<=\> operator defines a relationship between == and \<=\> such that a ==  
> > b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics in  
> > the way of IEEE-754. Likewise, it should hold that (a \<=\> b) == .ascending  
> > iff a \< b, and (a \<=\> b) != .descending iff a \<= b.
> > 
> > The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or  
> > greater of the two operands, respectively, while in case of equal  
> > arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the  
> > right-hand side to retain identity, as presently explained in this comment  
> > \<[https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;\](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C).  
> > Making them customization points of Comparable, we get to fix their  
> > behaviour in the presense of unorderable values (SR-1011  
> > \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).
> > 
> > Most user types should only implement \<=\> and leave the other members of  
> > Equatable and Comparable to their default implementations. Note that even  
> > == has a sane default implementation if Self is made Comparable:
> > 
> > // Default implementations, which should be used for most Comparable types:extension Comparable {  
> > &nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
> > &nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
> > &nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
> > &nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
> > &nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
> > }  
> > // Unoverridable top-level operators and functions for Comparable:public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling)  
> > of floating point comparisons
> > 
> > \*The following text is written in terms of Double but other floating-point  
> > types (Float, Float80) are proposed the same treatment.\*
> > 
> > The IEEE-754 floating point specification has two oddities when it comes  
> > to orderability: there are two zeros (0.0 and -0.0) which are considered  
> > equal to each other, and there are \*multiple\* not-a-number values x for  
> > which x.isNaN == true and x != y with any value of y, even x itself.  
> > (Remark: the most common NaN value is obtained by the static property  
> > Double.nan.)
> > 
> > The interface of Comparable is designed so that \<=\> alone is able to  
> > produce a total order among all possible Doublevalues, sorting negative  
> > NaNs less than any other values, and positive NaNs greater than any other.  
> > Otherwise, within the range of totally ordered floating point values, -Double.infinity  
> > ... Double.infinity, the result of a \<=\> b remains in full agreement with  
> > the laws of a \< b, a \<= b, and a == b.
> > 
> > The suggested implementation of Double : Comparable makes \<=\> distinguish  
> > between every different bitPatternof NaN:
> > 
> > extension Double : Comparable {  
> > &nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
> > &nbsp;&nbsp;}  
> > &nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
> > &nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
> > &nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
> > &nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
> > &nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
> > }  
> > // Likewise:extension Float : Comparable { ... }extension Float80 : Comparable { ... }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples)  
> > and order reversal
> > 
> > Due to missing language support, tuples of Comparable elements cannot be  
> > Comparable themselves, but in the spirit of SE-0015  
> > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;),  
> > such tuples are given their overloads of \<=\> up to a standard library  
> > defined maximum arity:
> > 
> > public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
> > &nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
> > &nbsp;&nbsp;if a != .equal { return a }  
> > &nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
> > &nbsp;&nbsp;if b != .equal { return b }  
> > &nbsp;&nbsp;return .equal  
> > }  
> > // Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.
> > 
> > To simplify the reversal of a given ordering operation, two members of  
> > Ordering are provided in an extension:
> > 
> > extension Ordering {  
> > &nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
> > &nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
> > &nbsp;&nbsp;{  
> > &nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;public var reversed: Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;switch self {  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
> > &nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;}  
> > }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt);  
> > Foundation
> > 
> > In addition, Foundation code will now bridge NSComparisonResult to  
> > Ordering allowing for a fluid, natural, and safe API.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact)  
> > on existing code
> > 
> > The biggest drawback of the proposed design is the large surface area of  
> > Comparable's interface, as well as the possibility of overriding the  
> > comparison operators by mistake. On the other hand, since the required \<=\> operator  
> > is new and affects all users porting their previously Comparable data  
> > types to Swift 3, we can use documentation to suggest removing the  
> > redundant (and possibly faulty) implementations of other comparison  
> > operators.
> > 
> > Existing Equatable but not Comparable types that define an equivalence  
> > relation with == will remain unchanged.
> > 
> > Existing Comparable types that define a total ordering with \< will need  
> > to implement \<=\> and should remove their existing implementation of any  
> > comparison operators, including ==. All other existing Comparable types  
> > should implement \<=\> that provides a total ordering, or should drop their  
> > Comparable conformance.
> > 
> > Before:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int  
> > }  
> > func ==(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;return lhs.year == rhs.year  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
> > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
> > }  
> > func \<(lhs: Date, rhs: Date) -\> Bool {  
> > &nbsp;&nbsp;if lhs.year != rhs.year {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
> > &nbsp;&nbsp;} else if lhs.month != rhs.month {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
> > &nbsp;&nbsp;} else {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
> > &nbsp;&nbsp;}  
> > }
> > 
> > After, using the tuple overload of \<=\>:
> > 
> > struct Date: Comparable {  
> > &nbsp;&nbsp;let year: Int  
> > &nbsp;&nbsp;let month: Int  
> > &nbsp;&nbsp;let day: Int
> > 
> > &nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
> > &nbsp;&nbsp;}
> > 
> > &nbsp;&nbsp;// // Explicit version:  
> > &nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > &nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
> > &nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
> > &nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
> > &nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
> > &nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
> > &nbsp;&nbsp;// }  
> > }
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives)  
> > considered
> > 
> > A previous design of this proposal suggested a strict total order upon  
> > Comparable. While that would make generic algorithms more correct, the  
> > definition ended up fighting against the expected behaviour of floating  
> > point numbers.
> > 
> > An alternative design that better matches the existing arithmetic-related  
> > protocols in Swift is one that uses a member function.
> > 
> > public protocol Comparable: Equatable {  
> > &nbsp;&nbsp;func compare(to: Self) -\> Ordering  
> > }
> > 
> > However, while this API does read better than an operator, we believe that  
> > this imposes a number of artificial restrictions (especially in light of  
> > SE-0091  
> > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt);  
> > )
> > 
> > &nbsp;&nbsp;&nbsp;1. There is no way to use Comparable.compare as a higher-order  
> > &nbsp;&nbsp;&nbsp;function in a non-generic context.  
> > &nbsp;&nbsp;&nbsp;2. If a member is desired, it can be provided in a protocol extension  
> > &nbsp;&nbsp;&nbsp;and defined in terms of the ordering operator; to each according to their  
> > &nbsp;&nbsp;&nbsp;need.  
> > &nbsp;&nbsp;&nbsp;3. The existing tuple overloads cannot be expressed with a member  
> > &nbsp;&nbsp;&nbsp;function.
> > 
> > One other that Rust has adopted is the inclusion of PartialEquatable and  
> > PartialComparable as ancestors of their flavor of Equatable and Comparable .  
> > Having protocols to organize and catalogue types that can only guarantee  
> > partial equivalence and ordering relations is a good approach for  
> > modularity but clutters the standard library with two new protocols for  
> > which few useful algorithms could be written against.
> > 
> > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future)  
> > directions
> > 
> > That the default sort() compares by \< and not \<=\> should be considered a  
> > bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved  
> > in the presense of NaN. However, given that the current behaviour is to  
> > produce an unspecified order, the fix is additive and can be slipped past  
> > Swift 3.
> > 
> > With \<=\> in place, several present and future standard library algorithms  
> > involving a \<T : Comparable\> requirement will possibly benefit from  
> > knowing the total ordering of two operands at once. This is a list of  
> > possible such functions (taking Array as example), to be proposed  
> > separately as an additive change:
> > 
> > extension Array {  
> > &nbsp;&nbsp;// Sorting
> > 
> > &nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
> > &nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > &nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]
> > 
> > &nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
> > &nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
> > &nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
> > &nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
> > &nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>
> > 
> > &nbsp;&nbsp;// Binary search
> > 
> > &nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
> > &nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > &nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
> > }
> > 
> > \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
> > swift-evolution mailing list  
> > swift-evolution@swift.org  
> > [https://lists.swift.org/mailman/listinfo/swift-evolution](https://lists.swift.org/mailman/listinfo/swift-evolution)

---

<div class="post-metadata">

**Author:** ![pyrtsa](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/pyrtsa/32/740_2.png) [@pyrtsa](https://forums.swift.org/u/pyrtsa)\
**Post date:** [July 25, 2016, 7:28pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/6 "2016-07-25T19:28:52Z")

</div>

To sort to ascending order, you'd still just call `.sort()` with no arguments.

To limit the scope of this proposal somewhat, I moved the introduction of new sorting functions into the Future directions section. All of those changes are additive in a way or another:

1. The default .sort() function would use `\<=\>` instead of `\<`.

(a) On the one hand, we'd get improved performance in cases like Array\<String\>.sort() where doing another `\<` comparison would be more costly.  
(b) On the other hand, we'd get well-defined behaviour when sorting Double arrays containing NaNs, because all non-NaN values would be sorted into one contiguous subrange of the result.

That's an additive change because (a) types implementing total order will still sort according to the same spec as `.sort(by: \<)`.

2. If I had it my way, the default .sort() would also become stable, and the programmer could opt in to using a faster unstable sort variant. There are cases where an unstable sort performs better, but a stable sort is a better default, not least because it's usually what people want when sorting a table by a given column.

3. Several functions (e.g. `.sort(by:)`) would be paired with a `frobnicate(ordering:)` variant where the block returns `Ordering` instead of `Bool`. For sorting to descending order, you'd call something like `someCollection.sort(ordering: Ordering.reversing(\<=\>))`. Or whatever naming we'll end up with.

— Pyry

> **···**
>
> > On 25 Jul 2016, at 21:23, Nevin Brackett-Rozinsky \<nevin.brackettrozinsky@gmail.com\> wrote:
> > 
> > My one question is, will I be able to write `someCollection.sort(.ascending)` and get the expected result? (This could be an additive future direction.)

---

<div class="post-metadata">

**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\
**Post date:** [July 25, 2016, 7:06pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/7 "2016-07-25T19:06:54Z")

</div>

> First, this is orthogonal to "adhering to the standard".  
> isTotallyOrdered( ) provides the total order predicate required by IEEE  
> 754. The standard has no opinion about whether or not `\<=\>` is bound to  
> that predicate.
> 
> Personally, I would be OK with using the `isTotallyOrdered` semantics for  
> `\<=\>`. However, it leads to some behavior that would be surprising for  
> novices: x is NaN, and a set S is { 1, 2, NaN }, but S does not contain x.  
> I am skeptical that the distinction between NaN payloads is salient \*for  
> generic code written on Comparable types\*. It \*is\* salient for some  
> (rare!) floating-point specific code, but `isTotallyOrdered` is available  
> for floating-point types.
> 
> There’s also the issue that if we want to be able to point at IEEE 754 and  
> say “\<=\> implements a total order on Level N”, distinguishing distinct NaNs  
> has consequences for other values. In particular, it means that a decimal  
> type should distinguish between 1e0 and 10e-1, because it would necessarily  
> be an ordering on level 3 or 4. For { 1, 20 } to not contain 2e1 seems  
> highly dubious to me.

Given your reasoning, I have to agree that ordering on level 2 is the only  
sensible option for generic code written on Comparable types.

With this resolution, I think Dave has largely convinced me that the design  
as originally proposed (shadowable but not overridable `==` forwards to  
`===`, etc.) should be workable for wisely chosen implementations of `===`  
and `\<=\>`.

– Steve

> **···**
>
> On Mon, Jul 25, 2016 at 1:52 PM, Stephen Canon via swift-evolution \< swift-evolution@swift.org\> wrote:
> 
> > On Jul 25, 2016, at 2:23 PM, Nevin Brackett-Rozinsky \< \> nevin.brackettrozinsky@gmail.com\> wrote:
> > 
> > Pyry, this proposal looks great to me. My one question is, will I be able  
> > to write `someCollection.sort(.ascending)` and get the expected  
> > result? (This could be an additive future direction.)
> > 
> > Stephen, what is your rationale for wanting `\<=\>` to identify NaN values  
> > with different payloads as `.equal`?
> > 
> > I believe the IEEE 754 total order specification uses the bit-pattern just  
> > as Pyry’s proposal does, and there is value is adhering to the standard.  
> > Besides, if someone intentionally wishes to consider all NaN values as  
> > equivalent they can use `.isNaN` (or even map them to .nan first for  
> > uniformity).
> > 
> > Nevin
> > 
> > On Mon, Jul 25, 2016 at 1:26 PM, Stephen Canon via swift-evolution \< \> swift-evolution@swift.org\> wrote:
> > 
> > > Hi Pyry —
> > > 
> > > Dave and I spent some time discussing the details of how this applies to  
> > > floating point earlier today. We’re now in agreement that \<=\> should treat  
> > > -0 and +0 as distinct, and treat all NaNs as .equal. There are three  
> > > motivating considerations:
> > > 
> > > 1. Although -0 and +0 are “IEEE 754 equal”, there is no computation that  
> > > can produce both of them. In the parlance of IEEE 754, for any rounding  
> > > mode, the sets of real values that round to them are disjoint. Because of  
> > > this, if -0 and +0 appear as members of a set, or as keys in a dictionary,  
> > > they necessarily are the result of distinct computations or data.
> > > 
> > > 2. Substitutability. Adopting these semantics means that if `x \<=\> y` is  
> > > `.equal`, `f(x) \<=\> f(y)` is also `.equal` for any computation `f(x)` that  
> > > depends on the represented value (as opposed to the encoding) of its  
> > > argument.
> > > 
> > > 3. 754 defines four “specification levels”, or models:
> > > 
> > > - Level 1: The two-point compactification of the reals, or “extended real  
> > > numbers”.  
> > > - Level 2: The set of representable floating-point data: {-inf … -0}  
> > > union { 0 … inf } union { NaN }.  
> > > - Level 3: The set of representations of floating-point data:  
> > > sign-exponent-significand triples, +/-inf, qNaN, sNaN.  
> > > - Level 4: Floating-point encodings (bit patterns).
> > > 
> > > The `\<=\>` semantics we propose constitute a total order on level 2, which  
> > > is the computable model closest to the (reasonably familiar) extended real  
> > > numbers. Treating -0 and +0 as .equal would put us in a bit of a no-man’s  
> > > land between levels 1 and 2.
> > > 
> > > Thanks,  
> > > – Steve
> > > 
> > > On Jul 25, 2016, at 7:41 AM, Pyry Jahkola \<pyry.jahkola@iki.fi\> wrote:
> > > 
> > > Since we're running short on time, and the previous discussion thread  
> > > diverged, here's my attempt to fix the Comparable protocol.
> > > 
> > > \*Pull request:\* [Formalized ordering by pyrtsa · Pull Request #464 · apple/swift-evolution · GitHub](https://github.com/apple/swift-evolution/pull/464)
> > > 
> > > TL;DR:
> > > 
> > > 1. Equatable remains unchanged, while Comparable bloats a bit to support  
> > > several use cases.  
> > > 2. `a \<=\> b` is well-defined even if either value is NaN. Zero is equal  
> > > to minus zero.  
> > > 3. Types are not strictly required to become totally ordered, even if  
> > > it's strongly recommended.
> > > 
> > > — — —
> > > 
> > > I simply can't see how a pure total order version of Comparable would fit  
> > > the standard way floating point values are expected to behave. However, I  
> > > think we can reach a satisfactory conclusion, one that involves no crashing  
> > > in the standard library, which is what I previously suggested.
> > > 
> > > What I'm trying to fix is so that all operations listed in  
> > > [https://dl.dropboxusercontent.com/u/217402/Comparable.pdf](https://dl.dropboxusercontent.com/u/217402/Comparable.pdf) abide to laws  
> > > for types without incomparable values, and that types with weaker order can  
> > > still work in \*some\* well-defined way outside their totally ordered  
> > > range.
> > > 
> > > PS. Forgive me Robert, Jaden, and Harlan for not syncing with you, for  
> > > time is tight. I can pull back or revise the proposal if you don't want to  
> > > be involved.
> > > 
> > > — Pyry
> > > 
> > > Formalized Ordering
> > > 
> > > &nbsp;&nbsp;&nbsp;- Proposal: SE-NNNN  
> > > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-filename.md&gt);  
> > > &nbsp;&nbsp;&nbsp;- Authors: Robert Widmann \<[https://github.com/codafi&gt;](https://github.com/codafi&gt;), Jaden Geller  
> > > &nbsp;&nbsp;&nbsp;\<[https://github.com/jadengeller&gt;](https://github.com/jadengeller&gt;), Harlan Haskins  
> > > &nbsp;&nbsp;&nbsp;\<[https://github.com/harlanhaskins&gt;](https://github.com/harlanhaskins&gt;), Pyry Jahkola  
> > > &nbsp;&nbsp;&nbsp;\<[https://github.com/pyrtsa&gt](https://github.com/pyrtsa&gt);  
> > > &nbsp;&nbsp;&nbsp;- Status: Awaiting review  
> > > &nbsp;&nbsp;&nbsp;- Review manager: TBD
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#introduction&gt);  
> > > Introduction
> > > 
> > > This proposal cleans up the semantics of ordering relations in the  
> > > standard library. Our goal is to formalize the total ordering semantics of  
> > > the Comparable protocol and still provide accessible ordering  
> > > definitions for types without total ordering semantics.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#motivation&gt);  
> > > Motivation
> > > 
> > > The standard comparison operators have an intuitive meaning to  
> > > programmers. Swift encourages encoding that in an implementation of  
> > > Comparable that respects the rules of a total order  
> > > \<[https://en.wikipedia.org/wiki/Total\_order&gt;\](https://en.wikipedia.org/wiki/Total_order&gt;%5C). The standard library takes  
> > > advantage of these rules to provide consistent implementations for sorting  
> > > and searching generic collections of Comparable types.
> > > 
> > > Not all types behave so well in this framework, unfortunately. There are  
> > > cases where the semantics of a total order cannot apply and still maintain  
> > > the traditional definition of “comparison” over these types. Take, for  
> > > example, sorting an array of Float s. Today, Float ‘s instance of  
> > > Comparable follows IEEE-754 and returns false for all comparisons of NaN .  
> > > In order to sort this array, NaN s are considered outside the domain of \< ,  
> > > and the order of a “sorted” array containing them is undefined.
> > > 
> > > In addition, generic algorithms in the Swift Standard Library that make  
> > > use of the current Comparable protocol may have to make twice as many  
> > > comparisons to request the ordering of values with respect to each other  
> > > than they should. Having a central operation to return information about  
> > > the ordering of values once should provide a speedup for these operations.
> > > 
> > > In the interest of cleaning up the semantics of Comparable types of all  
> > > shapes and sizes and their uses in the Swift Standard Library, this  
> > > proposal is going to re-arrange the requirements of the Comparable and  
> > > Equatable protocols.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#proposed-solution&gt;Proposed)  
> > > solution  
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#equatable&gt);  
> > > Equatable
> > > 
> > > The interface of Equatable remains unchanged under this proposal.  
> > > Equatable types should still respect the equivalence laws of  
> > > \*reflexivity\* (a == a), \*symmetry\* (a == b iff b == a), and  
> > > \*transitivity\* (if a == b and b == c, then a == c). Further, != remains  
> > > a top-level binary operator for which a != b iff !(a == b).
> > > 
> > > Types containing properties \*inessential to equality\*, however, are  
> > > allowed to retain their notion of identity. For example Array's capacity isn't  
> > > considered for equality; and -0.0 == 0.0 and "ä" == "a\u{308}", while (-0.0).sign  
> > > != (0.0).sign and "ä".utf8.count != "a\u{308}".utf8.count.
> > > 
> > > IEEE-754 floating point numbers are allowed to break the reflexivity law  
> > > by defining that .nan != x for any value of x, which is the standard  
> > > behaviour documented in IEEE-754 and implemented the same way in other  
> > > programming languages.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#comparable&gt);  
> > > Comparable
> > > 
> > > The Comparable protocol will now require (without default implementation  
> > > provided) a single operator definition: \<=\> — the comparison operator.  
> > > From this, all other comparison operators will be derived so as to respect  
> > > the total order semantics of Comparable:
> > > 
> > > To maintain compatibility with IEEE-754, the interface of Comparable also  
> > > contains as customization points the operators \<, \<=, and == (derived  
> > > from Equatable) as well as the static binary functions \_min(\_:\_:) and  
> > > \_max(\_:\_:). User-defined types are recommended against overriding the  
> > > default implementations.
> > > 
> > > The uncustomizable top-level binary comparison operators a \> b and a \>= b are  
> > > implemented as synonyms to b \< aand b \<= a, respectively.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#standard-library&gt;Standard)  
> > > Library
> > > 
> > > Unlike a previous revision of this proposal, standard library algorithms  
> > > specific to FloatingPoint remain unchanged.
> > > 
> > > Overloads of \<=\> for tuples of Comparable elements are provided up to a  
> > > library-defined arity.
> > > 
> > > The intent of this proposal is to later augment the standard library so  
> > > that functions that take an ordering predicate by: (T, T) -\> Bool will  
> > > have an overload ordering: (T, T) -\> Ordering that will provide a —  
> > > potentially — more efficient implementation. A list of such functions is  
> > > provided in Future directions.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#detailed-design&gt;Detailed)  
> > > design
> > > 
> > > The Comparable protocol will be amended by taking away \> and \>=, adding  
> > > customisation points \_min(\_:\_:), and \_max(\_:\_:), and introducing the  
> > > ordering operator \<=\> that makes use of the Ordering enum defined below.
> > > 
> > > enum Ordering : Equatable {  
> > > &nbsp;&nbsp;case ascending  
> > > &nbsp;&nbsp;case equal  
> > > &nbsp;&nbsp;case descending  
> > > }  
> > > infix operator \<=\> { associativity none precedence 130 }  
> > > public protocol Comparable : Equatable {  
> > > &nbsp;&nbsp;// Implementation required:  
> > > &nbsp;&nbsp;static func \<=\>(lhs: Self, rhs: Self) -\> Ordering
> > > 
> > > &nbsp;&nbsp;// Default implementations provided:  
> > > &nbsp;&nbsp;static func == (lhs: Self, rhs: Self) -\> Bool // derived from Equatable  
> > > &nbsp;&nbsp;static func \< (lhs: Self, rhs: Self) -\> Bool  
> > > &nbsp;&nbsp;static func \<= (lhs: Self, rhs: Self) -\> Bool  
> > > &nbsp;&nbsp;static func \_min(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > > &nbsp;&nbsp;static func \_max(\_ lhs: Self, \_ rhs: Self) -\> Self  
> > > }
> > > 
> > > The \<=\> operator defines a relationship between == and \<=\> such that a  
> > > == b iff (a \<=\> b) == .equal, unless Self chooses to break the semantics  
> > > in the way of IEEE-754. Likewise, it should hold that (a \<=\> b) ==  
> > > .ascending iff a \< b, and (a \<=\> b) != .descending iff a \<= b.
> > > 
> > > The \_min(\_:\_:) and \_max(\_:\_:) functions should return the lesser or  
> > > greater of the two operands, respectively, while in case of equal  
> > > arguments, \_min(\_:\_:) should favour the left-hand side and \_max(\_:\_:) the  
> > > right-hand side to retain identity, as presently explained in this  
> > > comment  
> > > \<[https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;\](https://github.com/apple/swift/blob/4614adc16168d612b6fc7e7a161dd5b6b34be704/stdlib/public/core/Algorithm.swift#L17-L20&gt;%5C).  
> > > Making them customization points of Comparable, we get to fix their  
> > > behaviour in the presense of unorderable values (SR-1011  
> > > \<[https://bugs.swift.org/browse/SR-1011&gt;\](https://bugs.swift.org/browse/SR-1011&gt;%5C)).
> > > 
> > > Most user types should only implement \<=\> and leave the other members of  
> > > Equatable and Comparable to their default implementations. Note that  
> > > even == has a sane default implementation if Self is made Comparable:
> > > 
> > > // Default implementations, which should be used for most Comparable types:extension Comparable {  
> > > &nbsp;&nbsp;static func == (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .equal }  
> > > &nbsp;&nbsp;static func \< (l: Self, r: Self) -\> Bool { return (l \<=\> r) == .ascending }  
> > > &nbsp;&nbsp;static func \<= (l: Self, r: Self) -\> Bool { return (l \<=\> r) != .descending }  
> > > &nbsp;&nbsp;static func \_min(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? r : l }  
> > > &nbsp;&nbsp;static func \_max(\_ l: Self, \_ r: Self) -\> Self { return r \< l ? l : r }  
> > > }  
> > > // Unoverridable top-level operators and functions for Comparable:public func \> \<T : Comparable\>(l: T, r: T) -\> Bool { return r \< l }public func \>= \<T : Comparable\>(l: T, r: T) -\> Bool { return r \<= l }public func min\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_min(l, r) }public func max\<T : Comparable\>(\_ l: T, \_ r: T) -\> T { return T.\_max(l, r) }
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#handling-of-floating-point-comparisons&gt;Handling)  
> > > of floating point comparisons
> > > 
> > > \*The following text is written in terms of Double but other  
> > > floating-point types (Float, Float80) are proposed the same treatment.\*
> > > 
> > > The IEEE-754 floating point specification has two oddities when it comes  
> > > to orderability: there are two zeros (0.0 and -0.0) which are considered  
> > > equal to each other, and there are \*multiple\* not-a-number values x for  
> > > which x.isNaN == true and x != y with any value of y, even x itself.  
> > > (Remark: the most common NaN value is obtained by the static property  
> > > Double.nan.)
> > > 
> > > The interface of Comparable is designed so that \<=\> alone is able to  
> > > produce a total order among all possible Doublevalues, sorting negative  
> > > NaNs less than any other values, and positive NaNs greater than any other.  
> > > Otherwise, within the range of totally ordered floating point values, -Double.infinity  
> > > ... Double.infinity, the result of a \<=\> b remains in full agreement  
> > > with the laws of a \< b, a \<= b, and a == b.
> > > 
> > > The suggested implementation of Double : Comparable makes \<=\> distinguish  
> > > between every different bitPatternof NaN:
> > > 
> > > extension Double : Comparable {  
> > > &nbsp;&nbsp;public static func \<=\> (l: Double, r: Double) -\> Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;func ordinal(\_ x: UInt64) -\> UInt64 {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return x \< 0x80000000\_00000000 ? x + 0x7fffffff\_ffffffff : ~x  
> > > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return ordinal(l.bitPattern) \<=\> ordinal(r.bitPattern)  
> > > &nbsp;&nbsp;}  
> > > &nbsp;&nbsp;public static func == (l: Double, r: Double) -\> Bool { return Builtin.eq(l, r) }  
> > > &nbsp;&nbsp;public static func \< (l: Double, r: Double) -\> Bool { return Builtin.lt(l, r) }  
> > > &nbsp;&nbsp;public static func \<= (l: Double, r: Double) -\> Bool { return Builtin.le(l, r) }  
> > > &nbsp;&nbsp;public static func \_min(l: Double, r: Double) -\> Double { return Builtin.fmin(l, r) }  
> > > &nbsp;&nbsp;public static func \_max(l: Double, r: Double) -\> Double { return Builtin.fmax(l, r) }  
> > > }  
> > > // Likewise:extension Float : Comparable { ... }extension Float80 : Comparable { ... }
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#tuples-and-order-reversal&gt;Tuples)  
> > > and order reversal
> > > 
> > > Due to missing language support, tuples of Comparable elements cannot be  
> > > Comparable themselves, but in the spirit of SE-0015  
> > > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;](https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md&gt;),  
> > > such tuples are given their overloads of \<=\> up to a standard library  
> > > defined maximum arity:
> > > 
> > > public func \<=\> \<A : Comparable, B : Comparable\>(lhs: (A, B), rhs: (A, B)) -\> Ordering {  
> > > &nbsp;&nbsp;let a = lhs.0 \<=\> rhs.0  
> > > &nbsp;&nbsp;if a != .equal { return a }  
> > > &nbsp;&nbsp;let b = lhs.1 \<=\> rhs.1  
> > > &nbsp;&nbsp;if b != .equal { return b }  
> > > &nbsp;&nbsp;return .equal  
> > > }  
> > > // Similarly for \<A : Comparable, B : Comparable, C : Comparable\>, etc.
> > > 
> > > To simplify the reversal of a given ordering operation, two members of  
> > > Ordering are provided in an extension:
> > > 
> > > extension Ordering {  
> > > &nbsp;&nbsp;public static func reversing\<T : Comparable\>(\_ ordering: (T, T) -\> Ordering)  
> > > &nbsp;&nbsp;&nbsp;&nbsp;-\> (T, T) -\> Ordering  
> > > &nbsp;&nbsp;{  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return { l, r in ordering(r, l) }  
> > > &nbsp;&nbsp;}
> > > 
> > > &nbsp;&nbsp;public var reversed: Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;switch self {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .ascending: return .descending  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .equal: return .equal  
> > > &nbsp;&nbsp;&nbsp;&nbsp;case .descending: return .ascending  
> > > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > > &nbsp;&nbsp;}  
> > > }
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#foundation&gt);  
> > > Foundation
> > > 
> > > In addition, Foundation code will now bridge NSComparisonResult to  
> > > Ordering allowing for a fluid, natural, and safe API.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#impact-on-existing-code&gt;Impact)  
> > > on existing code
> > > 
> > > The biggest drawback of the proposed design is the large surface area of  
> > > Comparable's interface, as well as the possibility of overriding the  
> > > comparison operators by mistake. On the other hand, since the required  
> > > \<=\> operator is new and affects all users porting their previously  
> > > Comparable data types to Swift 3, we can use documentation to suggest  
> > > removing the redundant (and possibly faulty) implementations of other  
> > > comparison operators.
> > > 
> > > Existing Equatable but not Comparable types that define an equivalence  
> > > relation with == will remain unchanged.
> > > 
> > > Existing Comparable types that define a total ordering with \< will need  
> > > to implement \<=\> and should remove their existing implementation of any  
> > > comparison operators, including ==. All other existing Comparable types  
> > > should implement \<=\> that provides a total ordering, or should drop  
> > > their Comparable conformance.
> > > 
> > > Before:
> > > 
> > > struct Date: Comparable {  
> > > &nbsp;&nbsp;let year: Int  
> > > &nbsp;&nbsp;let month: Int  
> > > &nbsp;&nbsp;let day: Int  
> > > }  
> > > func ==(lhs: Date, rhs: Date) -\> Bool {  
> > > &nbsp;&nbsp;return lhs.year == rhs.year  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.month == rhs.month  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&& lhs.day == rhs.day  
> > > }  
> > > func \<(lhs: Date, rhs: Date) -\> Bool {  
> > > &nbsp;&nbsp;if lhs.year != rhs.year {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.year \< rhs.year  
> > > &nbsp;&nbsp;} else if lhs.month != rhs.month {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.month \< rhs.month  
> > > &nbsp;&nbsp;} else {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return lhs.day \< rhs.day  
> > > &nbsp;&nbsp;}  
> > > }
> > > 
> > > After, using the tuple overload of \<=\>:
> > > 
> > > struct Date: Comparable {  
> > > &nbsp;&nbsp;let year: Int  
> > > &nbsp;&nbsp;let month: Int  
> > > &nbsp;&nbsp;let day: Int
> > > 
> > > &nbsp;&nbsp;static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > > &nbsp;&nbsp;&nbsp;&nbsp;return (lhs.year, lhs.month, lhs.day)  
> > > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\<=\> (rhs.year, rhs.month, rhs.day)  
> > > &nbsp;&nbsp;}
> > > 
> > > &nbsp;&nbsp;// // Explicit version:  
> > > &nbsp;&nbsp;// static func \<=\> (lhs: Date, rhs: Date) -\> Ordering {  
> > > &nbsp;&nbsp;// let yearResult = lhs.year \<=\> rhs.year  
> > > &nbsp;&nbsp;// guard case .equal = yearResult else { return yearResult }  
> > > &nbsp;&nbsp;// let monthResult = lhs.month \<=\> rhs.month  
> > > &nbsp;&nbsp;// guard case .equal = monthResult else { return monthResult }  
> > > &nbsp;&nbsp;// return lhs.day \<=\> rhs.day  
> > > &nbsp;&nbsp;// }  
> > > }
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#alternatives-considered&gt;Alternatives)  
> > > considered
> > > 
> > > A previous design of this proposal suggested a strict total order upon  
> > > Comparable. While that would make generic algorithms more correct, the  
> > > definition ended up fighting against the expected behaviour of floating  
> > > point numbers.
> > > 
> > > An alternative design that better matches the existing arithmetic-related  
> > > protocols in Swift is one that uses a member function.
> > > 
> > > public protocol Comparable: Equatable {  
> > > &nbsp;&nbsp;func compare(to: Self) -\> Ordering  
> > > }
> > > 
> > > However, while this API does read better than an operator, we believe  
> > > that this imposes a number of artificial restrictions (especially in light  
> > > of SE-0091  
> > > \<[https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt](https://github.com/apple/swift-evolution/blob/master/proposals/0091-improving-operators-in-protocols.md&gt);  
> > > )
> > > 
> > > &nbsp;&nbsp;&nbsp;1. There is no way to use Comparable.compare as a higher-order  
> > > &nbsp;&nbsp;&nbsp;function in a non-generic context.  
> > > &nbsp;&nbsp;&nbsp;2. If a member is desired, it can be provided in a protocol extension  
> > > &nbsp;&nbsp;&nbsp;and defined in terms of the ordering operator; to each according to their  
> > > &nbsp;&nbsp;&nbsp;need.  
> > > &nbsp;&nbsp;&nbsp;3. The existing tuple overloads cannot be expressed with a member  
> > > &nbsp;&nbsp;&nbsp;function.
> > > 
> > > One other that Rust has adopted is the inclusion of PartialEquatable and  
> > > PartialComparable as ancestors of their flavor of Equatable and  
> > > Comparable . Having protocols to organize and catalogue types that can  
> > > only guarantee partial equivalence and ordering relations is a good  
> > > approach for modularity but clutters the standard library with two new  
> > > protocols for which few useful algorithms could be written against.
> > > 
> > > \<[https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future](https://github.com/pyrtsa/swift-evolution/blob/ca89e7b3a1dffc99baa695a03544fcba75afd0f3/proposals/NNNN-formalized-ordering.md#future-directions&gt;Future)  
> > > directions
> > > 
> > > That the default sort() compares by \< and not \<=\> should be considered a  
> > > bug to be fixed in a future version of Swift. Using \<=\> will make sort() well-behaved  
> > > in the presense of NaN. However, given that the current behaviour is to  
> > > produce an unspecified order, the fix is additive and can be slipped past  
> > > Swift 3.
> > > 
> > > With \<=\> in place, several present and future standard library  
> > > algorithms involving a \<T : Comparable\> requirement will possibly  
> > > benefit from knowing the total ordering of two operands at once. This is a  
> > > list of possible such functions (taking Array as example), to be  
> > > proposed separately as an additive change:
> > > 
> > > extension Array {  
> > > &nbsp;&nbsp;// Sorting
> > > 
> > > &nbsp;&nbsp;mutating func sort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > > &nbsp;&nbsp;func sorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]  
> > > &nbsp;&nbsp;mutating func stableSort(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows  
> > > &nbsp;&nbsp;func stableSorted(ordering: @noescape (Element, Element) throws -\> Ordering) rethrows -\> [Element]
> > > 
> > > &nbsp;&nbsp;/// Reorders the elements of the collection such that all the elements  
> > > &nbsp;&nbsp;/// returning `.ascending` are moved to the start of the collection, and the  
> > > &nbsp;&nbsp;/// elements returning `.descending` are moved to the end of the collection.  
> > > &nbsp;&nbsp;/// - Returns: the range of elements for which `ordering(x) == .equal`.  
> > > &nbsp;&nbsp;mutating func partition(ordering: @noescape (Iterator.Element) throws -\> Ordering) rethrows -\> Range\<Index\>
> > > 
> > > &nbsp;&nbsp;// Binary search
> > > 
> > > &nbsp;&nbsp;func bisectedIndex(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index?  
> > > &nbsp;&nbsp;func lowerBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > > &nbsp;&nbsp;func upperBound(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Index  
> > > &nbsp;&nbsp;func equalRange(ordering: @noescape (Element) throws -\> Ordering) rethrows -\> Range\<Index\>  
> > > }
> > > 
> > > \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
> > > swift-evolution mailing list  
> > > swift-evolution@swift.org  
> > > [https://lists.swift.org/mailman/listinfo/swift-evolution](https://lists.swift.org/mailman/listinfo/swift-evolution)
> > 
> > \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
> > swift-evolution mailing list  
> > swift-evolution@swift.org  
> > [https://lists.swift.org/mailman/listinfo/swift-evolution](https://lists.swift.org/mailman/listinfo/swift-evolution)

---

<div class="post-metadata">

**Author:** ![David\_Sweeris](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/david_sweeris/32/31302_2.png) [@David\_Sweeris](https://forums.swift.org/u/David_Sweeris)\
**Post date:** [July 25, 2016, 9:02pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/8 "2016-07-25T21:02:43Z")

</div>

Two quick questions…  
1) What about adding an `isInvalid` case? That way types (such as Double/Float) which have “unordered” values can check for an invalid comparison.  
2) What about making `Ordering` a tuple instead of an enum? “typealias Ordering = (isLessThan: Bool, isEqual: Bool, isGreaterThan: Bool, isInvalid: Bool)”? It’d take up more space on the stack, but I think this:  
func \< (lhs: Int, rhs: Int) -\> Bool {  
&nbsp;&nbsp;&nbsp;&nbsp;return (lhs \<=\> rhs).isLessThan  
}  
or even this:  
func \< (lhs: Int, rhs: Int) -\> Bool {  
&nbsp;&nbsp;&nbsp;&nbsp;let ord = (lhs \<=\> rhs).isLessThan  
&nbsp;&nbsp;&nbsp;&nbsp;return ord.isLessThan && !ord.isInvalid  
}

would execute faster than this:  
func \< (lhs: Int, rhs: Int) -\> Bool {  
&nbsp;&nbsp;&nbsp;&nbsp;switch (lhs \<=\> rhs) {  
&nbsp;&nbsp;&nbsp;&nbsp;case lessThan: return true  
&nbsp;&nbsp;&nbsp;&nbsp;default: return false  
}

because there wouldn’t be any branching beyond what’s necessary to do the actual comparison.

- Dave Sweeris

> **···**
>
> > On Jul 25, 2016, at 2:28 PM, Pyry Jahkola via swift-evolution \<swift-evolution@swift.org\> wrote:
> > 
> > > On 25 Jul 2016, at 21:23, Nevin Brackett-Rozinsky \<nevin.brackettrozinsky@gmail.com \<mailto:nevin.brackettrozinsky@gmail.com\>\> wrote:
> > > 
> > > My one question is, will I be able to write `someCollection.sort(.ascending)` and get the expected result? (This could be an additive future direction.)
> > 
> > To sort to ascending order, you'd still just call `.sort()` with no arguments.
> > 
> > To limit the scope of this proposal somewhat, I moved the introduction of new sorting functions into the Future directions section. All of those changes are additive in a way or another:
> > 
> > 1. The default .sort() function would use `\<=\>` instead of `\<`.
> > 
> > (a) On the one hand, we'd get improved performance in cases like Array\<String\>.sort() where doing another `\<` comparison would be more costly.  
> > (b) On the other hand, we'd get well-defined behaviour when sorting Double arrays containing NaNs, because all non-NaN values would be sorted into one contiguous subrange of the result.

---

<div class="post-metadata">

**Author:** ![pyrtsa](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/pyrtsa/32/740_2.png) [@pyrtsa](https://forums.swift.org/u/pyrtsa)\
**Post date:** [July 25, 2016, 7:12pm UTC](https://forums.swift.org/t/proposal-formalized-ordering-take-2/3540/9 "2016-07-25T19:12:25Z")

</div>

The reason is two-fold:

Firstly, and most importantly, because we want the law of antisymmetry (that `a \< b` iff `b \> a`, and likewise for ≤ and ≥) to hold even in the presence of strange types. Turning only one operator of every such pair into customisation points makes it essentially impossible to break that law.

Secondly, because we want to minimise the surface area of Comparable to keep the API as simple as possible. The drawback of my design is that while it manages to alleviate many subtleties of IEEE-754, it also contains many member functions (essentially all but `\<=\>`) which should not be customised for most types in practice.

— Pyry

> **···**
>
> > On 25 Jul 2016, at 18:51, Björn Forster \<bjoern.forster@googlemail.com\> wrote:
> > 
> > Could you please explain for someone as simple minded as me why there is (or has to be) a difference in the implementation of \<, \<= and \>, \>=?  
> > Sorry, but I don't get into my head why there is/has to be a preference for one side. Could you or someone else point out (in the proposal) why there is a need/what is the reason for this?  
> > I assume that this might not be obvious to some other people on the first look, too.