- Proposal: SE-NNNN
- Authors: Anthony Latsis, Cal Stephens
- Review Manager: TBD
- Status: Awaiting Review
- Implementation: apple/swift#23156
This proposal presents an addition to the Standard Library in an effort to make map sorting and, eventually, closureless key-path sorting a functional prerequisite for Swift.
Swift-evolution thread: Discussion thread topic for that proposal
Today, the typical method for sorting arrays is to use an areInIncreasingOrder predicate. This closure takes the form (Element, Element) -> Bool, so it welds together both the accessing and comparison of values.
struct Person {
...
var age: Int
}
struct Chat {
...
var lastMsg: Message
}
var people: [Person] = ...
var chats: [Chat] = ...
people.sort { $0.age < $1.age }
chats.sort { $0.lastMsg.date > $1.lastMsg.date }In many circumstances, this syntax can cause issues:
- The
$0.property < $1.propertysyntax often leads to copy-and-paste bugs, since it requires duplicating the property accessor before and after the comparison operator. - For long property names, this syntax can be especially verbose since it requires repeating the property name twice.
- When the values are expensive to retrieve or calculate, this type of predicate becomes an obstacle for optimizations. It may be desirable to trade memory for speed such that each value is computed once per element rather than O(n logn) times. For an ϴ(n) operation, this optimization can theoretically speed up sorting by a factor of 10 for an array of 1000 elements. This is called the Schwartzian Transform.
Thereby, the goal of this proposal is to introduce an API that decouples the comparison of values from their retrieval, bringing ergonomic benefits for an ample range of cases, and opening the door for new optimizations.
The authors propose to add an overload for both the nonmutating sorted and in-place sort methods on Sequence and MutableCollection respectively. A mapping closure on Element will lead the argument list, followed by the well known areInIncreasingOrder predicate and, finally, a flag for opting into the already mentioned Schwartzian Transform optimization.
transformis deliberately positioned before the predicate to respect logical and type-checking order.- Following the precedent set by
sortandsorted, theareInIncreasingOrdercomparator has a default value of<when theValuetype being sorted on isComparable.
Here are some example usages:
chats.sort(on: { $0.lastMsg.date })
chats.sort(on: { $0.lastMsg.date }, by: >)
fileUnits.sort(
on: { $0.raw.count(of: "func") },
by: <,
isExpensiveTransform: true
)Following the acceptance of SE-0249, the examples above can also be written with a key-path:
chats.sort(on: \.lastMsg.date)
chats.sort(on: \.lastMsg.date, by: >)extension Sequence {
@inlinable
public func sorted<Value>(
on transform: (Element) throws -> Value,
by areInIncreasingOrder: (Value, Value) throws -> Bool,
isExpensiveTransform: Bool = false
) rethrows -> [Element] {
guard isExpensiveTransform else {
return try sorted {
try areInIncreasingOrder(transform($0), transform($1))
}
}
var pairs = try map {
try (element: $0, value: transform($0))
}
try pairs.sort {
try areInIncreasingOrder($0.value, $1.value)
}
return pairs.map { $0.element }
}
@inlinable
public func sorted<Value: Comparable>(
on transform: (Element) throws -> Value,
isExpensiveTransform: Bool = false
) rethrows -> [Element] {
return try self.sorted(on: transform, by: <, isExpensiveTransform: isExpensiveTransform)
}
}
extension MutableCollection where Self: RandomAccessCollection {
@inlinable
public mutating func sort<Value>(
on transform: (Element) throws -> Value,
by areInIncreasingOrder: (Value, Value) throws -> Bool,
isExpensiveTransform: Bool = false
) rethrows {
guard isExpensiveTransform else {
return try sort {
try areInIncreasingOrder(transform($0), transform($1))
}
}
var pairs = try map {
try (element: $0, value: transform($0))
}
try pairs.sort {
try areInIncreasingOrder($0.value, $1.value)
}
for (i, j) in zip(indices, pairs.indices) {
self[i] = pairs[j].element
}
}
@inlinable
public mutating func sort<Value: Comparable>(
on transform: (Element) throws -> Value,
isExpensiveTransform: Bool = false
) rethrows {
try self.sorted(on: transform, by: <, isExpensiveTransform: isExpensiveTransform)
}
}This is an ABI-compatible addition with no impact on source compatibility.
over has more of a mathematical flavor to it, where the transform argument is read as a set of values with an injective (one-to-one) relation to the elements of the sequence. For that matter, «map sorting» can be thought of as sorting the set of transformed values and permuting the elements of the original sequence accordingly. While this variant emphasizes the strong correlation of mathematics and computer science, Swift as a multi-paradigm language should strive to settle with generally understandable names that, ideally, can be easily recognized regardless of the user's background.
The by label is a perfect candidate to describe the metric used to sort the sequence. using, on its turn, is just as fitting for a predicate or an operator. The pair in question is perhaps the only one that always boils down to a proper
sentence - «Sort(ed) by a metric using a predicate». 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. With ABI Stability kicking in, we no longer have the opportunity for amendments to public API signatures and must be especially careful in this regard.