On Mon, Apr 24, 2017 at 7:16 PM, Dave Abrahams <[email protected]> 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 <[email protected]> > 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 <[email protected]> > >> 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 < > [email protected]> > >> >> 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...
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
