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