[swift-evolution] [Draft][Proposal] Formalized Ordering

[Brent Royal-Gordon]

> On Jul 24, 2016, at 9:06 PM, Pyry Jahkola via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Another possible choice would be to return .descending whenever either of the comparands were NaN, while also making <, >, <=, and >= return false in such cases. Then we wouldn't see preconditionFailures but instead produced bogus results from sort, partition etc. That's the tradeoff Haskell has chosen for its `compare` function over Double, FWIW.

That's essentially what we currently have. I think we'd like to fix it.

Honestly, I think the most natural result is that calls like `sort()` and `max()` ignore NaNs—for instance, an Array<Double> might have fewer elements if you sort it. That seems to be the behavior implied by `FloatingPoint.maximum/minimum(_:_:)`. However, it is still possible to access and use the total ordering if you need it.

This sort of suggests we should have two levels of comparisons:

* `===` and `<===>` are total.

* `==` and `<=>` may not work on, or may conflate, some values.

How to actually accomplish this is a more difficult question. The simplest solution might be something like:

	protocol Equatable {
		static func === (…) -> Bool
		static func == (…) -> Bool
	}
	extension Equatable {
		static func == (…) -> Bool {
			return lhs === rhs
		}
	}

	protocol Comparable: Equatable {
		/// Total ordering which works on and distinguishes between all values of the type.
		static func <===> (…) -> Ordering
		
		/// "Friendly" ordering which may conflate or not work on some values of the type.
		/// 
		/// - Precondition: Neither `lhs` nor `rhs` returns `true` from `isAberration`.
		static func <=> (…) -> Ordering
		
		/// If true, this instance should be ignored when using the <=> operator.
		var isAberration: Bool { get }
	}
	extension Comparable {
		static func === (…) -> Bool {
			return (lhs <===> rhs) == .same
		}
		static func == (…) -> Bool {
			return (lhs <=> rhs) == .same
		}
		static func <=> (…) -> Ordering {
			return lhs <===> rhs
		}
		var isAberration: Bool {
			return true
		}
	}

However, this means that sorting requires two functions, not one (or that, when using a custom sorting function, you must separately pre-filter the aberrations from your data set). An alternative would be to introduce a PartialOrdering type:


	enum PartialOrdering {
		case ordered (Ordering)
		case leftUnordered
		case bothUnordered
		case rightUnordered
	}
	// As above, except...
	protocol Comparable: Equatable {
		...
		
		/// "Friendly" ordering which may not work on some values of the type.
		/// 
		/// - Precondition: Neither `lhs` nor `rhs` returns `true` from `isAberration`.
		static func <=> (…) -> PartialOrdering
	}

This wouldn't necessarily handle the `-0.0 == +0.0` case well, though. That *could* be handled with extra cases meaning "equal but ordered", but this is looking messier and messier.

-- 
Brent Royal-Gordon
Architechies