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

[Dave Abrahams]

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... ;-)

> 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.  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) }`.

> 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