[swift-evolution] [pitch] Comparison Reform

[Xiaodi Wu]

On Mon, Apr 24, 2017 at 7:16 PM, Dave Abrahams <dabrahams at apple.com> wrote:

>
> on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>
> > On Sun, Apr 23, 2017 at 4:32 PM, Dave Abrahams <dabrahams at apple.com>
> wrote:
> >
> >>
> >> on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
> >>
> >> > On Sun, Apr 23, 2017 at 7:54 AM, Dave Abrahams <dabrahams at apple.com>
> >> wrote:
> >> >
> >> >>
> >> >> on Sun Apr 23 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
> >> >>
> >> >> > On Sat, Apr 22, 2017 at 11:00 PM, Dave Abrahams <
> dabrahams at apple.com>
> >> >> wrote:
> >> >> >
> >> >> >>
> >> >> >> >> > That is to say, I would expect the standard library to
> supply an
> >> >> >> >> > alternative implementation of equality for Array<T where T :
> >> >> >> >> > FloatingPoint>.
> >> >> >> >>
> >> >> >> >> And also for Dictionary?  What do you expect to happen when
> >> Double is
> >> >> >> >> used as a dictionary key and it happens to be NaN?
> >> >> >> >
> >> >> >> > The proposal is very clear that `Dictionary` and `sort` will
> always
> >> >> use
> >> >> >> > level 2 comparison.
> >> >> >>
> >> >> >> Yes, but I'm not asking about my own proposal :-).  My question
> is,
> >> what
> >> >> >> are *your* expectations for dictionaries or sets, specifically for
> >> the
> >> >> >> insertion of NaN keys and for comparison of whole collections?
> >> >> >
> >> >> > My expectations for comparison of collections clearly differ from
> >> >> > yours.
> >> >>
> >> >> Maybe, in that you *have* strong expectations when it comes to FP.
> I'm
> >> >> still trying to figure out what mine should be.
> >> >>
> >> >> > For me, I think it is a reasonable expectation that, for all `x`
> and
> >> >> > `y` where `x == y`, `[x] == `[y]`, `[[x]] == [[y]]`, `[x, x, x] ==
> [y,
> >> >> > y, y]`, etc.
> >> >>
> >> >> It seems pretty obvious when you put it that way.  Here's an
> interesting
> >> >> question: how much of that is because of the way array literals let
> you
> >> >> “see through” the value being compared to its elements?
> >> >>
> >> >
> >> > I don't think it's the visual representation. More to do with
> >> expectations
> >> > as to what an array is.
> >> >
> >> > If `a == b`, then `thingWrappingA == thingWrappingB`, for values of
> >> "thing"
> >> > that are "wrapper-like" (I will blithely leave the term undefined)
> rather
> >> > than, say, stateful class instances.
> >>
> >> wrapper-like probably means "Monad"
> >>
> >> >> Also, does the same go for != ? That's telling w.r.t. NaN.
> >> >
> >> > Yes, I think so. I'd have to think harder to be more sure of that.
> >>
> >> Well, that's the hard one, so please do.  We can easily shift the
> >> proposal so -0.0 == +0.0, but NaNs are harder to account for.
> >>
> >>
> > Right, more thought is necessary. It was obviated when I was writing my
> > proposed design, because NaN != NaN simply traps, and [NaN] != [NaN]
> would
> > too.
>
> More thought was obviated?  That's a neat trick! ;-)
>
> >> > Hmm, not an expert, but I don't see that definition. MathWorld <
> >> > http://mathworld.wolfram.com/ComparableElements.html> confirms that
> the
> >> > Wikipedia formulation is correct:
> >> >
> >> > x is incomparable to y if neither x ***>=*** y nor x ***<=*** y.
> >>
> >> Ah, right.  But this is where it gets tricky to interpret, because IIUC
> >> in orderings in general, there is no concept of equality; there's just
> >> "x precedes y or it doesn't."  So when these articles use <= or <, it is
> >> a stand-in for "the ordering predicate".  In ancient times, I wrote an
> >> article exploring some of this
> >> (http://web.archive.org/web/20120422220137/http://cpp-
> >> next.com/archive/2010/02/order-i-say/).
> >> I always go back to that when I need to ground myself, though using your
> >> own article for that has its perils.  Please check that out and let me
> >> know if you think I'm off-base, because the notion of incomparability in
> >> that article is central to my understanding (and is, I believe,
> >> consistent with https://en.wikipedia.org/wiki/Weak_ordering, FWIW).
> >
> > IIUC, you're talking about a _strict_ partial order, which is
> > _irreflexive_.
>
> That may be another name for the same thing.  The terminology in this
> area is... problematic.  But look for “incomparable” at
> https://en.wikipedia.org/wiki/Weak_ordering and you'll see that I'm
> consistent with that.
>
> > Such a relation is totally silent, however, as to whether x and y are
> > equivalent if `x !<> y`.
>
> Correct; that's what I meant by “in orderings in general, there's no
> concept of equality.”  However, if `x !<> y` in a strict weak ordering,
> `x` and `y` are part of an equivalence class, each element of which has
> the same relationships with all the other elements of the set.
>
> > As a standalone predicate, it isn't sufficient to order a set which
> > contains a pair of incomparable values in the way that you and Ben
> > propose. For instance, suppose I'm trying to sort an array with 42 and
> > NaN using a generic algorithm that can't just test `isNaN`.
> > So, to the algorithm, these values are an opaque `a` and `b`.  Since
> > !(a < b) and !(b < a), there's no information I can get from the
> > predicate to tell me which one is the "problem value" (is it a, or is
> > it b: which one is NaN?).
>
> I'm sorry, I don't follow.  Your statement that our ordering of
> incomparable
> values is insufficient seems to lack context, so I can't evaluate it.
> I'll note that in a strict weak ordering, incomparable values are not
> problematic, but Floating Point doesn't have a strict weak ordering.
>
> > In the context of set theory, I'm reading that comparability is defined
> in
> > terms of _weak_ partial orders (which are reflexive).
>
> Where are you reading that?
>
> As my article notes, trying to analyze the space can be really
> confusing, because *strict weak* partial orders are *not* reflexive.
>
> > I guess I've just assumed we're using this definition of comparability
> > because IEEE floating point appears to adopt it.
>
> What makes you say that?
>
> > With a _weak_ partial order as a predicate, you *can* order a set
> > which contains a pair of incomparable values:
> >
> > * Given: 42 ("a") and NaN ("b").
> > * First, we note that !(a <= b) && !(b <= a). So, we have a pair of
> > incomparable values.
> > * Then, we ask which value is not a member of the partially ordered set
> on
> > which the <= relation is defined.
> > * We find that (a <= a) == true but (b <= b) == false.
> > * We conclude that b is the "problem value" (NaN) which is not a member
> of
> > the partially ordered set.
> > * We decide to send it to the back of the line.
>
> Yes, I understand that.  But I don't think I get the point yet.
>
> >> > I am not suggesting this particular name, but
> >> > `array1.elementsIndistinguishable(from: array2)` expresses something
> of
> >> the
> >> > idea.
> >>
> >> I'm very skeptical of introducing a notion of indistinguishability
> >> that's distinct from equality.
> >
> > I think this goes back to the above about what we want equality to be. If
> > equality is to be distinguished from incomparability (as it is in
> floating
> > point), then we must have some notion of what happens when two values
> > cannot be compared.
>
> That two elements are incomparable doesn't mean you can't compare them.
> It means that when you do compare them, you'll find they have no
> relative ordering, like siblings in a DAG.  See
> https://en.wikipedia.org/wiki/Comparability
>
> More later, if I can find time...
>

Yeah, I'll try to get to this at some point, but now that the weekend is
over I think I'm running out of steam as well...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170424/c9d7de53/attachment.html>