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

[Dave Abrahams]

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

>> 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 would be deeply surprising and would create a programming model
that was almost impossible to work with.  I could not support a result
like that.

> That seems to be the behavior implied by
> `FloatingPoint.maximum/minimum(_:_:)`. 

That elements are dropped from a collection when it is sorted?  How do
you figure?

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

This has really gone off the rails, guys.  There are no generic
algorithms that rely on an under-all-circumstances-substitutability
property, so we shouldn't encode it into a protocol.

Also, think about what “under all circumstances” really means: it means
that there are no implementation details, because it is possible for
code with access rights to inspect them.  It means that no class
instances can ever be substitutable for other instances, because of
ObjectIdentity.  It becomes absurd really quickly.

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