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

Pyry Jahkola pyry.jahkola at iki.fi
Fri Jul 22 04:13:23 CDT 2016


> On 22 Jul 2016, at 04:11, Robert Widmann via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Harlan Haskins, Jaden Geller, and I have been working on a proposal to clean up the semantics of ordering relations in the standard library.  We have a draft that you can get as a gist.  Any feedback you might have about this proposal helps - though please keeps your comments on Swift-Evolution and not on the gist.

Bravo! It would be great to have Comparable defined in terms of a full comparison. I'd specifically call out String as a concrete example in the Motivation section, as this proposal is likely to give a performance boost on sorting String arrays, which is a pretty common thing to do.

----

I think the Detailed design section should explicitly show as source code:

1. What is the updated Equatable protocol?

2. What are all the updated operators? (I.e. show the new default implementations of `==` and `!=` too.)

3. In code comments, what are the updated rules or laws that should hold for Equatable and Comparable (and FloatingPoint, if any)?

4. What are the new "by: (Self, Self) -> Ordering" functions that the proposal is about to introduce to the stdlib?

----

On the topic of partial orderings (e.g. floating-point types), starting with the more important questions first:

5. Will it be considered "ok" to define a type for which `T.areSame(a, b) == true` but `a != b`? An obvious example would be Double.nan, so I assume the answer is a resounding yes.

6. Similarly, will it be "ok" to define a type for which `T.areSame(a, b) == false` but `a == b`? One possible example could be the comparison of `-0.0 <=> +0.0`. Should those be `.same` or not?

7. What, in fact, is the proposed total order for the stdlib's floating-point types?

(For an example, here is one possible way of defining `<=>` for Double, using `Double.bitPattern`. It distinguishes between +0.0 and -0.0, and even the various patterns of NaN! But do we want this for our `<=>` or something else?

    func <=> (lhs: Double, rhs: Double) -> Ordering {
      func f(_ x: UInt64) -> UInt64 {
        return x < 0x80000000_00000000 ? x + 0x80000000_00000000 : ~x
      }
      return f(lhs.bitPattern) <=> f(rhs.bitPattern)
    }
    print(            -0.0 <=> 0.0)         // ascending
    print(             1.0 <=> 0.0)         // descending
    print( Double.infinity <=> Double.nan)  // ascending
    print(-Double.infinity <=> -Double.nan) // descending
    print(      Double.nan <=> Double.nan)  // same

See http://swiftlang.ng.bluemix.net/#/repl/5791db33719d5d045b4d430c for a running example.)

----

A general idea:

8. I wouldn't mind if the proposal also covered including generated definitions for `tuple1 <=> tuple2` of tuples from zero arity through to 6 or whatever the gyb's upper limit may be.

That would simplify the example implementation of Date down to:

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

9. Some of us were not satisfied with the name of `.areSame(_:_:)`. Let me just point out that it would be nice if the name aligned with whatever `Ordering.same` will be called.

-- Pyry



More information about the swift-evolution mailing list