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

[Xiaodi Wu]

On Mon, Jul 25, 2016 at 1:12 AM, Brent Royal-Gordon via swift-evolution <
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 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.
>

Agreed very much. Although, any "friendly" `<=>` can be derived from what
you call `<===>` and `==`.

I've been playing with a variation where I have a "friendly" equivalence
relation `==?` (returns `Bool?` so that it's `nil` when there's a argument
that doesn't make sense to compare) and a finer equivalence relation `===`
as protocol requirements on Equatable, with a generic `==` defined as `{
return (lhs ==? rhs) ?? (lhs === rhs) }`. In that model, traditional
comparison operators can be synthesized from a total ordering (which you
call `<===>` and the original proposal calls `<=>`) by first consulting the
value of the friendly `==?` to determine if two operands are the same.

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
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160725/4805633a/attachment.html>