Map Sorting

Following the precedent set by sort and sorted , the areInIncreasingOrder comparator has a default value of < when the Value type being sorted on is Comparable .

By the way, the convenience overloads are optimal without a comparison predicate - for >, the non-Comparable overload is there to help you out.

I haven't lead a lot of proposals, but did learn it's reasonable to have them as lightweight as possible, especially when it comes to these orthogonal additions. This is a universal rule.
The more you propose, the more responsibility and maintenance follows. We might want to make corrections as the review runs and we must implement these overloads to begin with. Sadly, the performance of my laptop doesn't make small tooling changes to Swift a lot easier - I might not have the time but I want to save it regardless. The overloads have a pretty good chance of success, but I would rather have them implemented as an amendment to the accepted proposal than complicating changes during the review having at least some odds they (or the proposal altogether) might still be excluded.
I like though how you mention the overloads as a side note in the gist, without drawing extra attention.

2 Likes

I've opened a PR with my updated edits against your fork:

1 Like

@cal and I have updated the proposal to the state at which we believe it is ready for review.

1 Like

I understand the desire to keep things minimal, but I think that the overload defaulting to < should be included in the proposal. When talking about choosing argument labels you say:

Nevertheless, the author is convinced in the superior importance of preserving API uniformity and consistency with existing API the Standard Library developers have worked so hard to keep.

which applies equally to this matter, in my mind. It is also much easier for reviewers or the core team to say “this overload doesn't pull its weight” and remove it from the accepted proposal than it would be to make everyone involved go through a second proposal to make this very minor addition in future.

This is about the importance of avoiding discrepancy in API uniformity in a resilient library when introducing changes. The overloads are a uniform but peripheral addition.

I will make sure to inform the core team to consider and include the overloads to the accepted proposal in case of a positive outcome. Again, we excluded them from the main proposal not because we are opposed, but to save time. Let's get the proposal accepted to begin with. If that happens and everyone agrees on the overloads as well, they will be accepted with the rest and implemented.

@cal Though, if you are still willing to include and implement the overloads now, feel free to.

That's one way to think about it. To me you would be creating discrepancy because I think of the current sort/sorted and their overloads as a single thing (and indeed they presumably would be if there was some sort of “conditional default argument” feature in Swift). I'm a little confused about the time argument, because the overloads seem very simple to write (they can just call your current implementations with < like the current sort/sorted do). And it seems strange to me procedurally to have something in “Future Directions” that you half expect to be accepted in the current proposal.

1 Like

I was talking relative to ABI stability rather than subjective opinions.

FWIW, it is not as simple as the implementation itself. It takes some time to shape a well-written documentation section. Right now, I don't need a clean build for all the tooling, but it already takes a ridiculous amount of time to build the stdlib with my resources. We are talking about a couple of hours.

Fair enough, I will clarify and rename that section to «Considerations». Thanks!

2 Likes

Oh, okay, but the text I quoted from the proposal is about API uniformity and consistency, which isn't ABI related. If you don't have time to write the overloads and their documentation then that's fair (though these kind of additive APIs can be developed outside of the standard library entirely to avoid the compile time issue) but I'll be arguing strongly for their inclusion in the proposal review. Thanks for your work here, and I hope this proposal will be accepted.

2 Likes

I’m bumping this thread because I just looked through one of my projects and found that, although it has only a small number of sort calls, every single one of them would benefit from this proposal.

My feedback on the proposal is that I strongly prefer to have the comparison predicate first and the transform second. That is, the call site should look like this:

items.sorted(by: >){ $0.foo(bar) }

The comparison will almost always be either “<” or “>”, whereas the transform will often be a trailing closure, and putting them in this order enables that.

Having the default of “<” when the transformed values are Comparable is a basic and obvious thing to include. Sorting is frequently done in increasing order, and Swift’s existing sort functions all use “<” as a default, so these new ones should match that.

The spelling looks great as well:

items.sorted{ $0.foo(bar) }

• • •

If it weren’t for the fact that tuples cannot conform to protocols, I would almost say that the transform should be *required* to return a Comparable result. After all, it is mapping elements for the express purpose of sorting.

I mention tuples because, with this proposal, it will be quite easy to sort on multiple keys, provided they go in the same order:

items.sorted(by: <){ ($0.size, $0.color, $0.price) }

For numeric keys, the individual fields can have their sort orders independently reversed by unary negation, but that does not work for strings or enums and so forth. Perhaps a future pitch will introduce a better way of sorting on multiple keys. Something as simple as an order-reversing wrapper would work:

Order-reversing wrapper
struct Reversed<T: Comparable>: Comparable {
  var value: T
  init(_ value: T) { self.value = value }
  
  static func < (lhs: Self, rhs: Self) -> Bool {
    return rhs.value < lhs.value
  }
}

Of course, sorting on multiple keys via tuples is just a neat thing that can be done, it is not the driving impetus here.

• • •

Regarding the argument labels, I agree that “by” is correct for the comparison predicate, matching Swift’s existing sort functions. For the transform, there are several acceptable options, such as “on”, “via”, and “using”. These are grammatical as shown:

“Sort by a predicate, on a key”
“Sort by a predicate, via a map”
“Sort by a predicate, using a transform”

The word “via” might be too obscure, “on” is nice and short, and “using” reads well but takes up a lot of space. In practice, with the argument order allowing the transform to be a trailing closure, this label will rarely be seen.

The existing map function has no label for its transform argument, so that might be worth considering. It reads like “by” applies to both arguments, which in a way it does. We are sorting by a predicate, and also by a key. When using a keypath, we thus have:

items.sorted(by: >, \.name)

Then if the default ordering is used, the call site is extremely tidy:

items.sorted(\.name)

Now that I see it written out, I actually like that a lot.

• • •

I’m not sure how to feel about the isExpensiveTransform flag. I expect the transforms will be quite cheap in the vast majority of cases, so I don’t know if it’s worth complicating the API surface. I don’t have a strong opinion either way on this right now.

Thanks for the input on this! The Core Team decided not to move forward with this specific
proposal. @Ben_Cohen listed a good rationale in this thread:

Ben did mention potential future directions for work in this space, which I agree with:

1 Like

Yeah, Ben was right to stall this. I think we need a Sorting Manifesto before we move on to incremental review.

1 Like

Great idea! I missed this topic but I think min(by:) max(by:) methods can also be applied, and I wrote about this idea here:

From my perspective max and min needs this method even more than sort, because it's really unclear what { $0.age < $1.age } means to min or max.