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

[Pyry Jahkola]

Given all this, I propose a simpler model that makes `a <=> b` follow the expected behaviour of < and ==, with the tradeoff that `a <=> .nan` and `.nan <=> b` will abort with a precondition failure:

1) We keep the current Interface of Equatable  unchanged, with != defined in terms of ==.

2) Comparable would still refine Equatable, and include all the comparison operators, adding the new <=>:

    protocol Comparable : Equatable {
      static func <=>(lhs: Self, rhs: Self) -> Ordering
      static func <(lhs: Self, rhs: Self) -> Bool
      static func >(lhs: Self, rhs: Self) -> Bool
      static func <=(lhs: Self, rhs: Self) -> Bool
      static func >=(lhs: Self, rhs: Self) -> Bool
    }

The comparison operators are kept in the interface so that partially ordered types such as Double can be supported in generic code. However, the documentation should recommend against defining `<` manually.

3) Default implementations for <Self : Comparable> are provided for the following operators: ==, <, >, <=, and >=.

4) User-defined types will need to define just <=> to conform to Comparable. (Even == can be omitted!)

5) FloatingPoint types implement custom versions of ==, <, >, <=, and >= using the standard IEEE 754 definition (i.e. comparisons involving NaN return false). Zero is zero; `0.0 == -0.0 && !(-0.0 < 0.0)` holds.

6) FloatingPoint types implement <=> as:

    func <=> <T : FloatingPoint>(lhs: T, rhs: T) -> Ordering {
      if lhs < rhs { return .ascending }
      if rhs < lhs { return .descending }
      precondition(lhs == rhs)
      return .same
    }

7) Algorithms using <=> directly should mention so in their documentation as a precondition that they require total order between elements. Many generic algorithms can be defined in terms of == or <, and should.

If we took the oroginally planned route that distinguished between identities such as -0.0 vs. +0.0, or between the 2⁴⁹ - 2 ≈ 5.6 × 10¹⁴ possible NaN values that Double has, we'd also need to consider other oddballs like the difference and ordering between the Strings "ä" and "a\u{308}", which are considered equal but produce a different Unicode representation. I think it's best to hide those identities behind another interface than Equatable and Comparable, and let the protocols serve more mundane application logic.

— Pyry

> Dave Abrahams wrote:
> 
> 
>> on Sat Jul 23 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>> 
>> On Fri, Jul 22, 2016 at 11:34 PM, Stephen Canon <scanon at apple.com> wrote:
>> 
>>>> The point of this design is that `===` means identity and that `.same `
>>>> also means identity.
>>>> 
>>>> Since this is new territory I suppose we get to decide what identity
>>>> means for floating point.  Should +0 and -0 have the same identity or
>>>> not?  I’ll leave the answer to folks more knowledgable about numerics
>>>> than I.
>>> 
>>> Boy, I take my wife out for a movie and come back to 50 new messages on SE.
>>> 
>>> I need to read the entire thread more carefully, but off the top of my
>>> head, I think that `-0 === +0` is False.  If we’re going to have an
>>> `isSame` / `isIdentical` / whatever it's called, I would expect it to imply
>>> substitutability.  Although -0 == +0, they are not equivalent when
>>> substituted:
>>> 
>>> - 1/(-0) != 1/0
>>> - Float(-0).sign != Float(+0).sign
>>> - etc
>>> 
>>> This probably then implies that `<=>` is not `.same` either.  I’ll read
>>> the rest of this and respond more completely tomorrow.
>> 
>> Eagerly await your evaluation of the discussion. In the meantime:
>> 
>> I think Dave's view that `===` defines identity in terms of "essential"
>> qualities implies that two identical values can be
>> different/non-substitutable in "inessential" qualities. For generic
>> purposes, the sign of zero could be one such inessential quality.
> 
> Yes, and I think our view of how people work with numbers in swift (and
> their protocol conformances) reflect this approach.  
> 
> http://article.gmane.org/gmane.comp.lang.swift.evolution/16321
> 
> My sense is that we want to choose the default notions of identity and
> ordering so as to support the way people think about these numeric
> types, inexact though it may be.  Therefore, finding 0.0 in a sequence
> of floats should succeed when the sequence contains -0.0, and a stable
> sort on floating point keys should preserve the relative order of all
> elements having +0.0 and -0.0 keys.  
> 
> People that want to work with inessential qualities such as the sign of
> zero can always pass Float.totalOrdering (or whatever) to their
> closure-accepting algorithms.
> 
> [In order to support the user model, we still need to fix the semantics
> of the default identity and ordering operations so that things like
> sorting and searching work, which is why == and < won't cut it for these
> purposes]
> 
>> On the other hand, the stdlib stride algorithm is going to be borked if -0
>> < +0. Of course, as we already started to do there, we could specialize for
>> floating point and then adjust accordingly. However, it seems to me that
>> every generic algorithm that performs comparisons and can take floating
>> point arguments would have to be specialized to account for floating point
>> -0 != +0 (`index(of:)` being the previous example). This appears to defeat
>> the aim of trying to accommodate FP at all in this revised design for
>> Comparables.
> 
> Yes, that would be a disaster, generically speaking.
> 
>> The argument for `-0 === +0` is that -0 and +0 should be equivalent when
>> substituted for every comparison operation. For FP operations, you'd
>> continue to test (as you have to test now) `a == b && a.sign == b.sign` if
>> you cared about the sign of zero. For non-FP arithmetic operations, hmm,
>> not sure how to square that circle.
> 
> I followed all of this... except, what are you getting at with that last
> sentence?
> 
> --
> Dave
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution