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

[Dave Abrahams]

on Fri Jul 22 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:

> On Fri, Jul 22, 2016 at 5:48 PM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> on Fri Jul 22 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:
>>
>> > On Fri, Jul 22, 2016 at 3:54 PM, Dave Abrahams <dabrahams at apple.com>
>> wrote:
>> >
>> >>
>> >> on Fri Jul 22 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>> >>
>> >> > On Fri, Jul 22, 2016 at 1:05 PM, Dave Abrahams via swift-evolution <
>> >> > swift-evolution at swift.org> wrote:
>> >> >
>> >> >>
>> >> >> on Thu Jul 21 2016, Duan <swift-evolution at swift.org> wrote:
>> >> >>
>> >> >> > Great proposal. I want to second that areSame may mislead user to
>> >> >> > think this is about identity.
>> >> >> >
>> >> >> > I like areEquivalent() but there may be better names.
>> >> >>
>> >> >> It really *is* about identity as I posted in a previous message.
>> >> >
>> >> > Correct me if I'm wrong:
>> >>
>> >> Not to put too fine a point on it, but... ;-)
>> >>
>> >
>> > Please do :) This discussion has been very edifying (for me), so thank
>> you
>> > for taking the time.
>> >
>> >> > Identity is an equality relation, and `==` is about just that.
>> >> > By contrast, `areSame()` is to define an *equivalence* relation
>> >>
>> >> The phrase “equality relation” has no commonly-understood formal or
>> >> informal meaning AFAIK.
>> >>
>> >> “Identity” is a slightly informal term IIUC, but for any
>> >> commonly-understood meaning of that word, the “is identical to” is
>> >> *always* an equivalence relation.
>> >>
>> >> > through which, by default, `==` is to be dispatched.
>> >> > Since this design specifically
>> >> > contemplates scenarios in which certain Equatables will override `==`
>> >> *not*
>> >> > to dispatch through `areSame()`,
>> >>
>> >> [Since `==` wouldn't be a protocol requirement (except in
>> FloatingPoint),
>> >> it's technically shadowing rather than overriding in the general case.
>> >> I imagine this detail doesn't matter to your point]
>> >>
>> >> > the latter function evaluates only *equivalence* with respect to an
>> >> > arbitrary equivalence relation, not identity.
>> >>
>> >> Saying that areSame is just any old arbitrary equivalence relation,
>> >> would complicate the system in undesirable ways.
>> >
>> > Ah, well, there goes my dream of using `{ return true }` as my
>> equivalence
>> > relation... :P
>> >
>> >> It's
>> >> a bit subtle but I'll try to walk you through the reasoning:
>> >>
>> >> 1. We had a choice about whether to document that Comparable requires
>> >>    that <=> be a total order or a strict weak order [A strict weak order
>> >>    is a total order over equivalence classes of elements that aren't
>> >>    ordered with respect to other members of the same class].  Either one
>> >>    will work for the standard algorithms.
>> >>
>> >> 2. Because the concept of total order is more accessible and requiring
>> >>    <=> to be a total order doesn't seem to reduce expressivity, we
>> >>    decided on a total order.
>> >>
>> >> 3. The only difference between these two orderings is that in a total
>> >>    order the equivalence classes have only a single element, **which
>> >>    means that the equivalence relation in play has to, in some sense,
>> >>    tell you whether two things are identical**.  This all comes down to
>> >>    how you measure “are a and b the same element?”
>> >>
>> >> The alternative is to say that <=> is just a strict weak ordering and
>> >> areSame is just any arbitrary equivalence relation, but that really
>> >> complicates everything (not just the definition of Comparable).  For
>> >> example, you can't document `a.firstIndex(of: b)` as the first index
>> where
>> >> `b` appears in `a`; you have to say it's the first index of an element
>> >> that satisfies `{ Element.areSame($0, b) }`.
>> >>
>> >
>> > I hadn't considered how closely yoked Equatable and Comparable have
>> > to be.  You can't have Comparable refine Equatable such that
>> > `Comparable.areSame(_:)` has stricter semantic requirements than
>> > plain Equatable?
>>
>> Not if you want algorithms requiring Equatable to make sense.  There's
>> just no use for anything weaker than an equivalence relation.
>>
>
> I'm assuming you mean:
> s/equivalence relation/identity/

No, meant what I wrote, but maybe I misunderstood your question.  I
guess you were suggesting that `Equatable.areSame` could define an
equivalence relation but that `<=>` might distinguish elements that
weren't distinguished by `Equatable.areSame`?

Personally I don't see a use for that.  Remember, `Equatable` and
`Comparable` just define the default comparisons that you get when you
don't explicitly supply a comparison closure to these algorithms.
You're always free to use an arbitrary equivalence relation or strict
weak ordering with the closure-accepting versions of the algorithms.

> In that case, I'd think collapsing `areSame(_:)` into `===` and furnishing
> some other way of comparing memory addresses for class types is the most
> sensible way to go.
>
>> >
>> >> > Put another way, the future `Equatable` is a contract that conforming
>> >> > types will supply a definition of equality *and* an equivalence
>> >> > relation, where the former by default is dispatched through the
>> >> > latter; but it is specifically envisioned that the two may be
>> >> > separated in domain-specific scenarios.
>> >>
>> >> That is correct.  However, the equivalence relation in question still
>> >> is, in some very real sense, an identity check.
>> >>
>> >> >> But
>> >> >> that doesn't change the fact that areEquivalent might be a better
>> name.
>> >> >> It's one of the things we considered; it just seemed long for no real
>> >> >> benefit.
>> >> >>
>> >> >> > Daniel Duan
>> >> >> > Sent from my iPhone
>> >> >> >
>> >> >> >> On Jul 21, 2016, at 6:32 PM, Robert Widmann via swift-evolution
>> >> >> >> <swift-evolution at swift.org> wrote:
>> >> >> >>
>> >> >> >>
>> >> >> >>> On Jul 21, 2016, at 6:19 PM, Xiaodi Wu <xiaodi.wu at gmail.com>
>> wrote:
>> >> >> >>>
>> >> >> >>> This is nice. Is `areSame()` being proposed because static `==`
>> is
>> >> >> >>> the status quo and you're trying to make the point that `==` in
>> the
>> >> >> >>> future need not guarantee the same semantics?
>> >> >> >>
>> >> >> >> Yep!  Equivalence and equality are strictly very different things.
>> >> >> >>
>> >> >> >>>
>> >> >> >>> Nit: I think the more common term in stdlib would be
>> >> >> >>> `areEquivalent()`. Do you think `same` in that context
>> (independent
>> >> >> >>> of the word "ordering") might erroneously suggest identity?
>> >> >> >>
>> >> >> >> There is room for improvement here.  Keep ‘em coming.
>> >> >> >>
>> >> >> >>>
>> >> >> >>>
>> >> >> >>>> On Thu, Jul 21, 2016 at 8: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.
>> >> >> >>>> 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
>> >> >> >>>>
>> >> >> >>>
>> >> >> >>
>> >> >> >> _______________________________________________
>> >> >> >> swift-evolution mailing list
>> >> >> >> swift-evolution at swift.org
>> >> >> >> https://lists.swift.org/mailman/listinfo/swift-evolution
>> >> >> > _______________________________________________
>> >> >> > swift-evolution mailing list
>> >> >> > swift-evolution at swift.org
>> >> >> > https://lists.swift.org/mailman/listinfo/swift-evolution
>> >> >> >
>> >> >>
>> >> >> --
>> >> >> Dave
>> >> >>
>> >> >> _______________________________________________
>> >> >> swift-evolution mailing list
>> >> >> swift-evolution at swift.org
>> >> >> https://lists.swift.org/mailman/listinfo/swift-evolution
>> >> >>
>> >>
>> >> --
>> >> Dave
>> >>
>> > _______________________________________________
>> > swift-evolution mailing list
>> > swift-evolution at swift.org
>> > https://lists.swift.org/mailman/listinfo/swift-evolution
>> >
>>
>> --
>> Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
Dave