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

Fri Jul 22 17:24:20 CDT 2016

On Fri, Jul 22, 2016 at 2:52 PM Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:

>
> on Fri Jul 22 2016, Tony Allevato <swift-evolution at swift.org> wrote:
>
> > 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.
>
> The concepts are “domain-specific semantics” vs “semantics that is
> useful in generic contexts.”  Yes, they are usually 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.
>
> It's not limited to NaN.  The +0/-0 distinction can be tricky as well.
>
> > But it's still reasonable to want a stable ordering with those
> > included.
>
> It's also reasonable to want to search for those in a collection or use
> them as hash keys.  I'm pointing this out because it goes to the
> definition of equality, which sorting in general does not.
>
> > 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's my error, actually. I wasn't thinking straight when I proposed a
> change to the proposal that I claimed dropped the need for the other
> operators.
>
> > 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!).
>
> There is, because for algorithms that require Equatable to have any kind
> of meaningful semantics the equivalence relation requirement must be
> fulfilled, and prominent types exist whose `==` operator is not an
> equivalence relation.
>

Thanks for the detailed reply, Dave—this and some of your earlier replies
to this thread have helped me understand the use cases for this
distinction. So the argument is that something like this:

    [ 1.0, -2.0, Double.NaN, 4.0 ].contains(Double.NaN)

should return true because the argument is in the same equivalence class as
the element, even though NaN == NaN currently returns false? That seems
totally reasonable, and I think it would be very helpful for the proposal
to specifically call out some of these scenarios—right now it focuses
mostly on ordering, which led to my confusion.

To take this further, let's say I have a data structure where the elements
are a type with multiple fields, and the ordering is determined by a single
one of those fields (the "key"). Would a reasonable definition of
equivalence in this model be one where a is equivalent to b if a.key ==
b.key, regardless of the values of the other fields, and equality is
implemented by comparing all the fields? This is similar to how C++ STL's
definition of equivalence for ordered collections falls out of the
expression !(a < b) && !(b < a), since you could conceivably implement <
and == with the same distinctions there.

I would be completely supportive of using `===` for this equivalence
instead of areSame, based on your argument about identity. Would we need an
escape hatch for people who absolutely need to know whether two instances
occupy the same address? If I had to choose equivalence vs. same-address as
the one to make more verbose, same-address seems like the obvious choice to
me.

> > As it stands today, I think the proposal "leaks" ordering concepts into
> > Equatable when it shouldn't.
>
> I don't see any evidence for that, and I don't even believe you've said
> anything here to support that point of view.
>
> > 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).
>
> Check
>
> > 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.
>
> Yes, the doc comments are missing from the proposal.
>
> > 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.
>
> Depends what you mean by “affect ordering.”  Clearly if you sort Floats
> using < explicitly, it will have an effect.
>
> > 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.
>
> But you're forgetting algorithms that require an equivalence relation,
> which is basically everything that's constrained to Equatable.
>
> > 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.)
>
> Agreed, we should do something about this use case.
>
> --
> Dave
>
> _______________________________________________
> 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/625a4165/attachment.html>