[swift-evolution] [pitch] Comparison Reform
Xiaodi Wu
xiaodi.wu at gmail.com
Mon Apr 17 14:49:54 CDT 2017
Sorting a collection will not use `<` as the default predicate.
In the Gist, I've outlined a design for `[Double].sorted()` which would
exhibit identical behavior to what is proposed in this thread, but the
design would be different under the hood. In brief, the "go-to" overload
for sorting a collection of comparable elements would be:
sorted(_ sortOrder: SortOrder = .ascending, by comparison:
(Iterator.Element, Iterator.Element) -> Comparison? = `<=>`) ->
[Iterator.Element]
which would notionally use the following for the predicate known today as
`areInIncreasingOrder`:
{
switch sortOrder {
case .ascending:
return comparison($0, $1) == .some(.less) || comparison($1, $1) == .none
case .descending:
return comparison($1, $0) == .some(.less) || comparison($0, $0) == .none
}
}
(We would add an enum `SortOrder` distinct from `Comparison` for reasons
spelled out in the Gist--not really germane to your question, though. And,
although the compiler may or may not do it today, there ought to be no
reason why it cannot optimize away checks for `comparison(a, b) == .none`
if values of the concrete type never compare unordered--i.e. if the
function passed as the second argument to `sorted` returns `Comparison`
instead of `Comparison?`.)
(The `Comparison` instead of `Comparison?` thing, incidentally, is for me
the crux of my alternative design. I'm quite proud of it. It allows us to
recover most (all?) the benefits of knowing at compile time which types are
"partially" comparable and which are not, but *without* having a distinct
protocol named PartiallyComparable. That is, the one protocol `Comparable`
would require a comparison method that returns an instance of type
`Comparison?`. Conforming types that never compare unordered can fulfill
that requirement with a method that returns `Comparison` (non-optional).
Both the compiler and readers can gain something meaningful from that.
Meanwhile, we avoid the disaster of generic algorithms having two different
protocols to choose from and potentially not supporting floating point.)
With this design, each generic function would decide how to handle
unordered comparisons. I believe this to be superior because ordering NaN
greater than all other values produces an acceptable result for `sort` but
a rather unintuitive one for `max`, and there is no reason why we should
have to tolerate that.
Using `sort(by: <)` explicitly with a collection of elements that may
compare unordered will give a compiler warning, as `<` would not satisfy
the semantic requirements for a sort predicate. Nothing will forbid the
user from passing an arbitrary function as a predicate, though, just as we
do not stop someone from writing `sort(by: ==)` today. The warning about
using `<` will be silenced by writing `sort { $0 < $1 }`.
For perfect migration of existing code, `sort(by: <)` can be migrated to
the proposed spelling `sort(by: &<)` and retain Swift 3 behavior in every
way, including the same wonky results with NaN. Otherwise,
`sort(.ascending)` and `sort(.descending)` would be the preferred way to
write the same thing, with more sensible results when sorting NaN.
On Mon, Apr 17, 2017 at 11:40 Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:
>
> on Sun Apr 16 2017, Xiaodi Wu <swift-evolution at swift.org> wrote:
>
> > On Sun, Apr 16, 2017 at 1:13 AM, Dave Abrahams via swift-evolution <
> > swift-evolution at swift.org> wrote:
> >
> >> <snip>
> >>
> >>> > I have an incipient idea. It begins with:
> >> >> >
> >> >> > enum ComparisonResult {
> >> >> > case orderedAscending, orderedSame, orderedDescending, unordered
> >> >> > }
> >> >> >
> >> >> > I am sure there is something I am missing which makes this design a
> >> >> > horrible idea, but I'm interested in hearing them.
> >> >>
> >> >> It's not a horrible idea, but to be fair it's not really a design
> yet,
> >> >> either. You haven't said anything about what it's supposed to mean,
> how
> >> >> it is supposed to be used, how people write, use, and compose generic
> >> >> algorithms with it, how it deals with floating point, etc.
> >> >>
> >> >
> >> > I've evolved my thinking based on the discussion. Let's see:
> >> >
> >> > ```
> >> > public enum ComparisonResult : Equatable {
> >> > case orderedAscending, equivalent, orderedDescending, unordered
> >> > // I have renamed one case, in the hopes of emphasizing that two
> values
> >> > // that compare `equivalent` are not merely ordered the same, but
> >> should
> >> > // satisfy the three conditions of an equivalence relation.
> >> > }
> >> > // I will have to leave the question of how to bridge from Obj-C
> >> > // NSComparisonResult up to more capable hands.
> >> >
> >> > public protocol Comparable : Equatable {
> >> > func compared(to other: Self) -> ComparisonResult
> >> > }
> >> > // This will have to be modified as necessarily to support compiler
> magic
> >> > // necessary for source-compatibility with Swift 3
> >> >
> >> > extension Comparable {
> >> > public static func == (lhs: Self, rhs: Self) -> Bool {
> >> > let comparison = lhs.compared(to: rhs)
> >> > precondition(comparison != .unordered)
> >> > return comparison == .equivalent
> >> > }
> >> >
> >> > public static func < (lhs: Self, rhs: Self) -> Bool {
> >> > let comparison = lhs.compared(to: rhs)
> >> > precondition(comparison != .unordered)
> >> > return comparison == .orderedAscending
> >> > }
> >> > // etc.
> >> >
> >> > // Something I thought I'd never want to see, but on reflection not
> >> > terrible:
> >> > public static func &== (lhs: Self, rhs: Self) -> Bool {
> >> > return lhs.compared(to: rhs) == .equivalent
> >> > }
> >> >
> >> > public static func &< (lhs: Self, rhs: Self) -> Bool {
> >> > return lhs.compared(to: rhs) == .orderedAscending
> >> > }
> >> > // etc.
> >> > }
> >> >
> >> > extension FloatingPoint : Comparable {
> >> > public func compared(to other: Self) -> ComparisonResult {
> >> > if isNaN || other.isNaN { return .unordered }
> >> > if isLess(than: other) { return .orderedAscending }
> >> > if other.isLess(than: self) { return .orderedDescending }
> >> >
> >> > // On reconsideration, probably actually least surprising if +0.0
> ==
> >> > -0.0
> >> > // no matter what. It does not matter that division can give
> >> different
> >> > // results for two equivalent values, only that the three rules
> of an
> >> > // equivalence relation will hold, and it does.
> >> > //
> >> > // If a user is really savvy to the sign of zero, there is
> >> > FloatingPoint.sign,
> >> > // which is necessary in any case for working with FP operations
> that
> >> > // distinguish between +0 and -0. I can't think of a generic
> >> algorithm
> >> > over
> >> > // all Comparable types that could make use of the distinction
> >> between
> >> > +0
> >> > // and -0.
> >> > return .equivalent
> >> > }
> >> > }
> >> > ```
> >> >
> >> > In this design, `==`, `<`, etc. correspond to IEEE "signaling"
> operators,
> >> > while `&==`, `&<`, etc. correspond to C-style operators, which IEEE
> calls
> >> > "quiet" and actually notates using "?==", "?<", etc.
> >>
> >> It's interesting, but what's missing here is a description of the user
> >> model. How do users program with this design? What should my
> >> expectations be w.r.t. generic algorithms like sort() and floating point
> >> numbers, particularly NaN? If, as I suspect, sorting a collection
> >> containing NaN is going to trap (unless the collection has only one
> >> element?), why is that the right behavior?
> >
> > I've spent some time fleshing out this idea:
> > https://gist.github.com/xwu/e864ffdf343160a8a26839388f677768
>
> More interesting still, but you still failed to answer the final
> question above.
>
> --
> -Dave
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170417/e3d71152/attachment.html>
More information about the swift-evolution
mailing list