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

[Tony Allevato]

I like a lot of this, but the changes to Equatable are where I get stuck.
What are the scenarios where areSame is useful *outside* the context of the
proposed new Comparable interface?

I ask because changing the requirement for Equatable to areSame instead of
== seems like a backwards change to me. There are plenty of unorderable
types where == is the obvious thing you want to implement, and this makes
it less obvious. It also adds a named method to a protocol to serve the
purpose of an operator, which I've been fighting hard against in SE-0091
(even though you keep the global one and delegate to it).

There are two concepts at play here: comparability and orderability. 99.99%
of the time, they are identical. Your proposal mentions one place where
they're not: IEEE floating point numbers, because there exists an element
in that space, NaN, that doesn't satisfy an equivalence relation at all.
But it's still reasonable to want a stable ordering with those included.

In the proposal as it's written right now, the individual inequality
operators are implemented in terms of <=>. That won't work for
FloatingPoint, because (NaN < x) and (NaN >= x) should both be false but
the default implementations provided would make the latter true. So
FloatingPoint would still have to provide its own implementations of *all
of the (in)equality operators*, not just ==, in order to have the correct
definition w.r.t. to IEEE 754. I didn't see that called out anywhere in the
write-up.

That being said, don't get me wrong—there's still a lot about this proposal
that I like :)  Here's what I'm thinking (which is mostly what you have
written, with some tweaks):

1) Don't change Equatable. I don't see a need to distinguish between
equivalence and equality on its own (if there is one, please let me know!).
As it stands today, I think the proposal "leaks" ordering concepts into
Equatable when it shouldn't.
2) Comparable defines <=>, as proposed, but *also* defines <, >, <=, >=. A
protocol extension provides defaults for <, >, <=, >=, ==, and !=
implemented in terms of <=>. This lets most implementors of Comparable
implement <=> and get everything else for free, but it also lets types
replace individual operators with customized implementations (see #4 below)
easily *within* the type (SE-0091).
3) Comparable should be documented to imply that the default behavior is to
link the behavior of <=> to the individual comparisons, but that it can be
changed, meaning that only <=> must define a total ordering and the
individual comparison operators need not.
4) The very few types, like FloatingPoint, that need to provide
domain-specific behavior to do the obvious/intended thing for users can and
should override <, >, <=, >=, ==, and !=. This should be called out
explicitly, and it would *not* affect ordering. I think it's entirely
reasonable to have (NaN == NaN) return false and (NaN != NaN) return true
but (NaN <=> NaN) return .same without introducing another areSame concept,
because the former is demanded by IEEE 754.
5) Algorithms that rely on a total order, like sorts, must be implemented
in terms of <=>, not in terms of the individual operators, because of the
possibility that the definitions can be severed above.

As mentioned below, the one thing that a three-way comparison loses is the
easy ability to pass > instead of < to reverse the ordering, but it's
trivial to write a function that does this and I think it should be
included as part of the proposal. Something like this (may be typos, I'm
writing it in Gmail):

public func reverse<C: Comparable>(ordering: (C, C) -> Ordering) -> (C, C)
-> Ordering {
  return { lhs, rhs in
    switch ordering(lhs, rhs) {
    case .ascending: return .descending
    case .descending: return .ascending
    case .same: return .same
  }
}

(Comedy alternative: Add a second operator, >=<. But that might be pushing
it.)


On Thu, Jul 21, 2016 at 6:11 PM Robert Widmann via swift-evolution <
swift-evolution at swift.org> wrote:

> Hello Swift Community,
>
> 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.
> <https://gist.github.com/CodaFi/f0347bd37f1c407bf7ea0c429ead380e>  Any
> feedback you might have about this proposal helps - though please keeps
> your comments on Swift-Evolution and not on the gist.
>
> Cheers,
>
> ~Robert Widmann
>
>
>
>
> _______________________________________________
> 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/20160722/f51ebb40/attachment.html>