<div dir="ltr">This might be a radical suggestion ... or possibly a naive or unoriginal one, I'll find out once I suggest it.<div><br></div><div>Swift took the bold step of establishing optionals as a central type, rather than assigning dual meanings to 'default' values such as zero or false. Recognising the concept of not having a value, and safeguarding against that, is core to Swift.</div><div>Is it possible for Swift to recognise that there are values which simply aren't comparable, rather than forcing a choice between ascending, same, descending? Could we add a fourth: incomparable?</div><div><br></div><div>What if a sort operation didn't simply return an array of ordered values? What if it <i>partitioned</i> the values into comparable and incomparable values, and returned a sorted array of the former and an unordered collection of the latter?</div><div>Maybe, this being Swift, we could use some kind of 'sort!' exclamation mark to forcibly express that every value in the collection-to-be-sorted is implicitly comparable, if we're sure.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 10:37 PM, Xiaodi Wu via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="">On Sat, Jul 23, 2016 at 4:19 PM, Nevin Brackett-Rozinsky <span dir="ltr"><<a href="mailto:nevin.brackettrozinsky@gmail.com" target="_blank">nevin.brackettrozinsky@gmail.com</a>></span> wrote:<br></span><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Another option would be to leave the IEEE 754 NaN hijinks in Float and Double (as numerics people expect), and create a new type (with a nice approachable name) that “acts like” Double but does not model NaN. Then any operation which would ordinarily produce a NaN, instead traps for the new type. That way its comparison operators only have to worry about non-NaN values, which makes everything much cleaner.<div><br></div><div>Sorting Doubles would retain its present functionality, warts and all, which numerics people should be expected to handle. Whereas the new type (“Number” sounds good, especially if we can make it subsume NSNumber) would never have a NaN in the first place.</div></div></blockquote><div><br></div></span><div>The other comment I would make here is that, as mentioned earlier by Pyry, there are other types for which we'll need to reckon with domain-specific "hijinks" that don't offer easy notions of identity, Unicode being one example. I'd expect that many types that model an existing domain of human endeavor will run into something like this. Thus, carefully working through a design for fundamental protocols like Equatable and Comparable that don't fall down with FP will prove more broadly fruitful. I don't think that segregating all hijinks and modeling what we *wish* the world to be is as beneficial in terms of allowing generic algorithms to work meaningfully with types that people actually use in real-world scenarios.</div><div><div class="h5"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span><font color="#888888"><div><div></div><div>Nevin</div><div><br></div><div><br></div></div></font></span></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 4:57 PM, Xiaodi Wu via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Sorry to overwhelm with more emails. I'd like to show some work and further analysis for your consideration that refines the sketch I just wrote:<div><br></div><div>Two FP values a and b can be, with respect to each other:</div><div><br></div><div>* ordered or unordered (per IEEE, NaN compares unordered to everything, including itself)</div><div>* identical or not identical (for these purposes, we adopt Steve's proposed test for identity: substitutable for all operations; thus +0 is not identical to -0, but different binary representations of the same value are identical)</div><div>* equal or not equal (i.e. the behavior of the == operator today)</div><div><br></div><div>So, if a and b are, with respect to each other:</div><div><br></div><div>* ordered, identical, equal -- this is what happens ordinarily with two equal, non-NaN values</div><div>* ordered, identical, not equal -- this can never happen</div><div>* ordered, not identical, equal -- only +0 and -0</div><div>* ordered, not identical, not equal -- this is what happens ordinarily with two unequal, non-NaN values</div><div><br></div><div>* unordered, identical, equal -- this can never happen, but if NaNs are to be well-behaved (for a true equivalence relation), then we will need an equivalence relation in which NaN == NaN</div><div>* unordered, identical, not equal -- this is what always happens, but if NaNs are to be well-behaved, then such behavior will need to change</div><div>* unordered, not identical, equal -- this can never happen</div><div>* unordered, not identical, not equal -- this is what ordinarily happens with one NaN and one non-NaN value</div><div><br></div><div>Equatable can have === and my proposed ==? as part of its protocol; a generic ==, as originally proposed, would be defined outside the protocol.</div><div>A default implementation of ==? will forward to ===, and the generic == will be defined as `{ return (lhs ==? rhs) ?? (lhs === rhs) }`.</div><div>For floating point, ==? will be specialized and cease to forward to === so that +0 and -0 compare true and NaN and anything compare nil, and floating point == will be defined notionally as `{ return (lhs ==? rhs) ?? false }`.</div><div><div><div><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 3:09 PM, Xiaodi Wu <span dir="ltr"><<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Throwing out some more radical ideas here. Suppose we had instead (taking inspiration from IEEE notation):<div><br></div><div>[Pardon any errors; I'm writing freehand in Gmail]<br><div><br></div><div>infix operator ==? { /* figure out precedence later */ }</div><div><br></div><div>protocol Equatable {</div><div> static func ==? (lhs: Self, rhs: Self) -> Bool?</div><div> /* semantics:</div><div> this function returns nil if lhs and rhs are unordered with respect to each other</div><div> otherwise, evaluate by means of a legal equivalence relation */</div><div>}</div><div><br></div><div>func == <T: Equatable>(lhs: T, rhs: T) -> Bool {</div><div> return (lhs ==? rhs) ?? false</div><span><div>}</div><div><br></div><div>protocol Comparable : Equatable {</div><div> static func <=> (lhs: Self, rhs: Self) -> Ordering</div></span><div> /* semantics:</div><div> this is a total ordering; thus:</div><div> if `(a ==? b) == true`, then `(a <=> b) == .same`</div><div> if `(a ==? b) == false`, then `(a <=> b) != .same`</div><div> but, if `(a ==? b) == nil`, then `a <=> b` may yield any result</div><div> */</div><div><div><div>}</div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 23, 2016 at 2:35 PM, Pyry Jahkola <span dir="ltr"><<a href="mailto:pyry.jahkola@iki.fi" target="_blank">pyry.jahkola@iki.fi</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Given all this, I propose a simpler model that makes `a <=> b` follow the expected behaviour of < and ==, with the tradeoff that `a <=> .nan` and `.nan <=> b` will abort with a precondition failure:<br>
<br>
1) We keep the current Interface of Equatable unchanged, with != defined in terms of ==.<br>
<br>
2) Comparable would still refine Equatable, and include all the comparison operators, adding the new <=>:<br>
<br>
protocol Comparable : Equatable {<br>
static func <=>(lhs: Self, rhs: Self) -> Ordering<br>
<span> static func <(lhs: Self, rhs: Self) -> Bool<br>
static func >(lhs: Self, rhs: Self) -> Bool<br>
</span><span> static func <=(lhs: Self, rhs: Self) -> Bool<br>
static func >=(lhs: Self, rhs: Self) -> Bool<br>
}<br>
<br>
</span>The comparison operators are kept in the interface so that partially ordered types such as Double can be supported in generic code. However, the documentation should recommend against defining `<` manually.<br>
<br>
3) Default implementations for <Self : Comparable> are provided for the following operators: ==, <, >, <=, and >=.<br>
<br>
4) User-defined types will need to define just <=> to conform to Comparable. (Even == can be omitted!)<br>
<br>
5) FloatingPoint types implement custom versions of ==, <, >, <=, and >= using the standard IEEE 754 definition (i.e. comparisons involving NaN return false). Zero is zero; `0.0 == -0.0 && !(-0.0 < 0.0)` holds.<br>
<br>
6) FloatingPoint types implement <=> as:<br>
<br>
func <=> <T : FloatingPoint>(lhs: T, rhs: T) -> Ordering {<br>
if lhs < rhs { return .ascending }<br>
if rhs < lhs { return .descending }<br>
precondition(lhs == rhs)<br>
return .same<br>
}<br>
<br>
7) Algorithms using <=> directly should mention so in their documentation as a precondition that they require total order between elements. Many generic algorithms can be defined in terms of == or <, and should.<br>
<br>
If we took the oroginally planned route that distinguished between identities such as -0.0 vs. +0.0, or between the 2⁴⁹ - 2 ≈ 5.6 × 10¹⁴ possible NaN values that Double has, we'd also need to consider other oddballs like the difference and ordering between the Strings "ä" and "a\u{308}", which are considered equal but produce a different Unicode representation. I think it's best to hide those identities behind another interface than Equatable and Comparable, and let the protocols serve more mundane application logic.<br>
<span><font color="#888888"><br>
— Pyry<br>
</font></span><div><div><br>
> Dave Abrahams wrote:<br>
><br>
><br>
>> on Sat Jul 23 2016, Xiaodi Wu <<a href="http://xiaodi.wu-AT-gmail.com" rel="noreferrer" target="_blank">xiaodi.wu-AT-gmail.com</a>> wrote:<br>
>><br>
>> On Fri, Jul 22, 2016 at 11:34 PM, Stephen Canon <<a href="mailto:scanon@apple.com" target="_blank">scanon@apple.com</a>> wrote:<br>
>><br>
>>>> The point of this design is that `===` means identity and that `.same `<br>
>>>> also means identity.<br>
>>>><br>
>>>> Since this is new territory I suppose we get to decide what identity<br>
>>>> means for floating point. Should +0 and -0 have the same identity or<br>
>>>> not? I’ll leave the answer to folks more knowledgable about numerics<br>
>>>> than I.<br>
>>><br>
>>> Boy, I take my wife out for a movie and come back to 50 new messages on SE.<br>
>>><br>
>>> I need to read the entire thread more carefully, but off the top of my<br>
>>> head, I think that `-0 === +0` is False. If we’re going to have an<br>
>>> `isSame` / `isIdentical` / whatever it's called, I would expect it to imply<br>
>>> substitutability. Although -0 == +0, they are not equivalent when<br>
>>> substituted:<br>
>>><br>
>>> - 1/(-0) != 1/0<br>
>>> - Float(-0).sign != Float(+0).sign<br>
>>> - etc<br>
>>><br>
>>> This probably then implies that `<=>` is not `.same` either. I’ll read<br>
>>> the rest of this and respond more completely tomorrow.<br>
>><br>
>> Eagerly await your evaluation of the discussion. In the meantime:<br>
>><br>
>> I think Dave's view that `===` defines identity in terms of "essential"<br>
>> qualities implies that two identical values can be<br>
>> different/non-substitutable in "inessential" qualities. For generic<br>
>> purposes, the sign of zero could be one such inessential quality.<br>
><br>
> Yes, and I think our view of how people work with numbers in swift (and<br>
> their protocol conformances) reflect this approach.<br>
><br>
> <a href="http://article.gmane.org/gmane.comp.lang.swift.evolution/16321" rel="noreferrer" target="_blank">http://article.gmane.org/gmane.comp.lang.swift.evolution/16321</a><br>
><br>
> My sense is that we want to choose the default notions of identity and<br>
> ordering so as to support the way people think about these numeric<br>
> types, inexact though it may be. Therefore, finding 0.0 in a sequence<br>
> of floats should succeed when the sequence contains -0.0, and a stable<br>
> sort on floating point keys should preserve the relative order of all<br>
> elements having +0.0 and -0.0 keys.<br>
><br>
> People that want to work with inessential qualities such as the sign of<br>
> zero can always pass Float.totalOrdering (or whatever) to their<br>
> closure-accepting algorithms.<br>
><br>
> [In order to support the user model, we still need to fix the semantics<br>
> of the default identity and ordering operations so that things like<br>
> sorting and searching work, which is why == and < won't cut it for these<br>
> purposes]<br>
><br>
>> On the other hand, the stdlib stride algorithm is going to be borked if -0<br>
>> < +0. Of course, as we already started to do there, we could specialize for<br>
>> floating point and then adjust accordingly. However, it seems to me that<br>
>> every generic algorithm that performs comparisons and can take floating<br>
>> point arguments would have to be specialized to account for floating point<br>
>> -0 != +0 (`index(of:)` being the previous example). This appears to defeat<br>
>> the aim of trying to accommodate FP at all in this revised design for<br>
>> Comparables.<br>
><br>
> Yes, that would be a disaster, generically speaking.<br>
><br>
>> The argument for `-0 === +0` is that -0 and +0 should be equivalent when<br>
>> substituted for every comparison operation. For FP operations, you'd<br>
>> continue to test (as you have to test now) `a == b && a.sign == b.sign` if<br>
>> you cared about the sign of zero. For non-FP arithmetic operations, hmm,<br>
>> not sure how to square that circle.<br>
><br>
> I followed all of this... except, what are you getting at with that last<br>
> sentence?<br>
><br>
> --<br>
> Dave<br>
</div></div><div><div>> _______________________________________________<br>
> swift-evolution mailing list<br>
> <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</div></div></blockquote></div><br></div></div></div></div></div>
</blockquote></div><br></div></div></div></div></div>
<br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div></div></div><br></div></div>
<br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div>