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

Fri Jul 22 18:56:02 CDT 2016

Sorry, yeah, that's what I meant to ask. I can't see how it would make
anything unworkable, but I agree that it might not be very useful.
On Fri, Jul 22, 2016 at 18:50 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 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
>
> _______________________________________________
> 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/e744ce85/attachment.html>