Add capability to sort on a custom mapping (e.g., on a particular member)

[xwu]

There seems to be broad appetite for sorting on, say, surnames or ages for a collection of Person values. This has been made even more ergonomic now that key path literals can be used where a function takes a closure as an argument.

I'd propose, therefore, to add the following sorted(on:by:) and sort(on:by:) additions:

extension Sequence {
    @inlinable
    public func sorted<T>(
        on transform: (Self.Element) throws -> T,
        by areInIncreasingOrder: (T, T) throws -> Bool
    ) rethrows -> [Element] {
        try sorted {
            try areInIncreasingOrder(transform($0), transform($1))
        }
    }

    @inlinable
    public func sorted<T: Comparable>(
        on transform: (Self.Element) throws -> T
    ) rethrows -> [Element] {
        try sorted { try transform($0) < transform($1) }
    }
}

extension MutableCollection where Self: RandomAccessCollection {
    @inlinable
    public mutating func sort<T>(
        on transform: (Self.Element) throws -> T,
        by areInIncreasingOrder: (T, T) throws -> Bool
    ) rethrows {
        try sort {
            try areInIncreasingOrder(transform($0), transform($1))
        }
    }

    @inlinable
    public mutating func sort<T: Comparable>(
        on transform: (Self.Element) throws -> T
    ) rethrows {
        try sort { try transform($0) < transform($1) }
    }
}

The use site would look like the following:

struct Person {
    var name: String
    var age: Int
}

let persons = [
    Person(name: "Alice", age: 56),
    Person(name: "Bob", age: 34)
]

let x = persons.sorted(on: \.name, by: >)
let y = persons.sorted(on: \.age)

Any interest in such a change?

[natecook1000]

@xwu Thanks for opening this issue! I definitely agree that this it would be nice to fill this hole — let's talk a bit about the different ways we could fill it.

My primary concern with this approach is that it requires a couple overloads for every method that takes one of the binary areInIncreasingOrder predicates. One approach that could reduce the overload overload would be to only add the on: version, and provide an adapter that reverses the direction of the type's Comparable conformance:

/// Wraps a transform's result in a type that reverses the direction of `Comparable` comparisons.
func descending<T, U: Comparable>(_ transform: @escaping (T) -> U) -> (T) -> DescendingComparisons<U> { ... }

let a = persons.sorted(on: descending(\.name))
let b = persons.sorted(on: \.age)

// We _might_ want to add a kind of no-op `ascending` function as well...

While this cuts the number of overloads in half, both approaches using on: don't extend to sorting on multiple properties well, because of the lack of variadic generics. We could think about manually adding overloads for higher arities, but those would also need to be implemented everywhere.

A different alternative would be to provide functions that convert the transforming closures/key paths that are most convenient into the binary predicates that the methods expect. If we define one for ascending and one for descending order, we end up with code like this:

func ascending<T, U: Comparable>(_ transform: @escaping (T) -> U) -> (T, T) -> Bool { ... }
func descending<T, U: Comparable>(_ transform: @escaping (T) -> U) -> (T, T) -> Bool { ... }

let c = persons.sorted(by: descending(\.name))
let d = persons.sorted(by: ascending(\.age))

These don't include the sort-targeting type in the resulting function type, so it's also possible to compose them without new language features. Of course, the "hero shot" isn't quite as nice this way. Sorting strikes me as the 90% usage case, so perhaps a combined approach, using (on:) overloads just for to help out sorting ergonomics…

What do you think? I'm not saying the approach in the PR is the wrong one — just want to explore the space a little more fully.

[kylemacomber]

@natecook1000 even though you've smuggled this into the existing API, it reads quite fluently:

let c = persons.sorted(by: descending(\.name))
let d = persons.sorted(by: ascending(\.age))

[xwu]

@natecook1000 I agree with @kylemacomber and actually quite like the latter option: it reads well and composes nicely with APIs we already have.

The drawbacks I can see are that ascending and descending would be less discoverable than a separate API, and it'd be most ergonomic if left as free functions but their independent significance outside of sorting is somewhat unclear to me.

I would say in support of the sort(on:by:) form I've given above that it explicitly accommodates sorting on arbitrary non-Comparable projections via the custom predicate. This would allow users to sort on tuples, for example (since the comparability of tuples is not currently implemented); and it would allow custom comparisons of, say, floating-point values based on strict order rather than the partial order defined by a type's Comparable conformance. These are features enabled by a second overload not subsumed by some other way of specifying ascending and descending sorts, and it's precedented by our existing standard library design which offers sort(by:) as the more customizable counterpart of sort().

[natecook1000]

The drawbacks I can see are that ascending and descending would be less discoverable than a separate API, and it'd be most ergonomic if left as free functions but their independent significance outside of sorting is somewhat unclear to me.

Agreed on this — you have to know they're there, and there's a risk of overlapping names with other domains. That said, you don't want to add more context to the name, since the goal is to have a nice, readable call-site. asc and desc are probably too terse; ascendingOrdering(on:) is certainly overlong.

I would say in support of the sort(on:by:) form I've given above that it explicitly accommodates sorting on arbitrary non-Comparable projections via the custom predicate. This would allow users to sort on tuples, for example (since the comparability of tuples is not currently implemented); and it would allow custom comparisons of, say, floating-point values based on strict order rather than the partial order defined by a type's Comparable conformance. These are features enabled by a second overload not subsumed by some other way of specifying ascending and descending sorts, and it's precedented by our existing standard library design which offers sort(by:) as the more customizable counterpart of sort().

I can see that, but here I think the brevity of the on: parameter is probably outweighed by the closure you end up providing. Tuples will be Comparable at some point soon, so the closure would almost always be actual code and not just an operator:

// With 'on:' parameter:
let e = persons.sorted(on: \.specificGravity, by: { !$1.isTotallyOrdered(belowOrEqualTo: $0) })
// Just using property-access syntax: 
let f = persons.sorted(by: { !$1.specificGravity.isTotallyOrdered(belowOrEqualTo: $0.specificGravity) })

If that's the only kind of use case we need it for, I don't think we're getting enough oomph out of the on: parameter to motivate adding it across all the API.

[kylemacomber]

I wonder if we can smuggle this into ascending:

let f = persons.sorted(by: ascending(\.specificGravity, { $0.isTotallyOrdered(belowOrEqualTo: $1) }))

Where:

func ascending<T, U: Comparable>(
  _ transform: @escaping (T) -> U,
  _ areInIncreasingOrder: @escaping (U, U) -> Bool = { $0 < $1 }
) -> (T, T) -> Bool {
  ...
}

[xwu]

@natecook1000 Sadly not so soon for tuple conformances I think, as the proposal has now expired, I believe.

Where the on: parameter really shines is in avoiding repetition when your projection is a little more complicated but ad hoc and not worth caching:

let g = persons.sorted {
  $0.specificGravity.squareRoot()
} by: {
  $0.isTotallyOrdered(belowOrEqualTo: $1)
}

// As compared to:

let g = persons.sorted {
  $0.specificGravity.squareRoot()
    .isTotallyOrdered(belowOrEqualTo: $1.specificGravity.squareRoot()))
}

(Since we are making contrived examples, ignore the illogic of sorting on the square root of the specific gravity; imagine another function in its place that wouldn't be redundant.)

[robb]

For presenting data to a user, it would be nice if there was a way to break a tie, e.g.

let c = persons.sorted(by: descending(\.yearOfBirth), ascending(\.name))

Though I realize this could be done by sorting on name first and relying on the sort being stable at the expense of some overhead.