# Sorting Collections with \`map\` closures and SortDescriptors

**URL:** <https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276>\
**Category:** Pitches\
**Created:** [September 18, 2018, 7:41pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276 "2018-09-18T19:41:09Z")\
**Posts on this page:** 15\
**Page:** 2

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [September 21, 2018, 5:26pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/21 "2018-09-21T17:26:19Z")

</div>

> [@mpangburn](#):
>
> Jordan just touched on this, but the goal here isn't to reduce the number of characters; it's to reduce repetition. The arguments here aren't specific to `their` and can be made analagously to those proposed with `Bool.toggle()` with respect to the value of removing repetition on opposite sides of an operator.

I agree – but the case was much stronger with `toggle`, because it's common in that case to have long chains to get to the boolean you want to toggle. I don't think it's quite the same here.

And unlike toggle, there is a loss of expressivity with a solution that just references the path to the element, not the comparison: you are now locked into only one comparison (less than), which then leads to the need for a descriptor type that can have a `reversed` or `caseless` property.

Maybe there are still neater solutions out there to be discovered that get the best of both worlds.

---

<div class="post-metadata">

**Author:** ![sveinhal](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/sveinhal/32/3992_2.png) [@sveinhal](https://forums.swift.org/u/sveinhal)\
**Post date:** [September 23, 2018, 12:04pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/22 "2018-09-23T12:04:38Z")

</div>

I’ve used this operator in some projects. I’m not thrilled about it though.

```swift
prefix operator ^
prefix func ^<A, B> (operand: KeyPath<A, B>) -> (A) -> B {
  return { $0[keyPath: operand] }
}

let keyPath = \Person.name // KeyPath<Person, String>
let closure = ^keyPath // (Person) -> String

let names = people.map(\.name) // does not compile
let names = people.map(^\.name) // ["Ben", "Jerry", "Adam"]

```

---

<div class="post-metadata">

**Author:** ![AliSoftware](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alisoftware/32/2764_2.png) [@AliSoftware](https://forums.swift.org/u/AliSoftware)\
**Post date:** [February 25, 2020, 7:13pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/23 "2020-02-25T19:13:47Z")

</div>

Hello fellow Swifters!

What do you think about reviving that discussion?

I think that it would be valuable to introduce this in the stdlib now that we have KeyPaths, that SE-249 has landed, and that all of this would allow providing a nice KeyPath-friendly API for sorting

I've tried my take at what the API would like in modern Swift 5.2 [here](https://twitter.com/aligatr/status/1232374019502092291?s=20) ([gist here](https://gist.github.com/AliSoftware/e03cda3c97d4adddce55026571a7145b)) if you want to take a look.

* * *

Having this in the stdlib would allow us to write things as beautiful as these:

```
// Sort by name, ascending
users.sorted(by: \.name)

// Sort by age, descending
users.sorted(by: \.age, .descending)
users.sorted(by: .descending(\.age))

// Sort by name ascending, then by age descending
users.sorted(by: .ascending(\.name), .descending(\.age))

```

What I like with this design is that it both allows a nice short call if we need the default ascending order and just a KeyPath, a more descriptive call site when we want to mix ascending and descending orders for various keys, and all that without polluting the global space with free functions.

Bonus: in [my implementation](https://gist.github.com/AliSoftware/e03cda3c97d4adddce55026571a7145b) I even took advantage of SE-0253 (`callAsFunction`) to also allow things like:

```
let sortByNameAndAge = SortDescriptor<User>(.ascending(\.name), .descending(\.age))
let sortedUsers = sortByNameAndAge(users)

```

---

<div class="post-metadata">

**Author:** ![cal](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cal/32/35557_2.png) [@cal](https://forums.swift.org/u/cal)\
**Post date:** [February 25, 2020, 7:16pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/24 "2020-02-25T19:16:49Z")

</div>

I think the up-thread feedback from @ben-cohen and @jrose still applies here:

> [@ben-cohen](#):
>
> I'm fairly skeptical of introducing a new `SortDescriptor` type for this purpose. The beauty of `sort` taking a closure is that closures are so flexible. They can cover any comparison – less than, greater than, caseless (localized or not), stringly or numerically, partial comparisons like ignoring prefixes. All by taking a single argument, a function from two elements to bool.

> [@jrose](#):
>
> To take a wild guess, I think a series of key paths / key functions would handle 90% of the custom sorts that are out there today, i.e. only 1 in every 10 custom sorts would need to fall back to the general comparator closure form. Having the sort-by-key form, even a single key, is something I always appreciated in Python and Ruby. We might not have the language tools to do it yet today, though, and I wouldn't want to jam something in to work around that.

I think the ideal long-term solution would use varadic generics instead of having to introduce a type-erased `SortDescriptor` wrapper:

> [@cal](#):
>
> ```swift
> // (4) An additional design for symmetry, that would require Variadic Generics. 
> // Not currently possible. 
> people.sort(by: [ 
> { $0.age }, 
> { $0.name } 
> ])
> 
> ```

---

<div class="post-metadata">

**Author:** ![AliSoftware](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alisoftware/32/2764_2.png) [@AliSoftware](https://forums.swift.org/u/AliSoftware)\
**Post date:** [February 25, 2020, 7:20pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/25 "2020-02-25T19:20:42Z")

</div>

Sure, though correct me if I'm wrong, but from what I understood from the reactions to @ben-cohen 's feedback, we were still missing the ability to avoid repeating the property key.

In other words, the main concern we want to address here is to avoid having to repeat the property name in `{ $0.firstname < $1.firstname }` closures that you currently have to pass to `sorted`, but instead just provide a `KeyPath` like `\.name` and avoid repeating the property, thus avoiding the potential for bugs.

I'd already be happy if we at least had a `sort(KeyPath)` and not just a `sort((Element, Element) -> Bool)`

---

<div class="post-metadata">

**Author:** ![suyashsrijan](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/suyashsrijan/32/5292_2.png) [@suyashsrijan](https://forums.swift.org/u/suyashsrijan)\
**Post date:** [February 25, 2020, 7:20pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/26 "2020-02-25T19:20:48Z")

</div>

I think it might also be nice to be able to do something like this:

```swift
users.sorted(<, by: \.name)

```

---

<div class="post-metadata">

**Author:** ![AliSoftware](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alisoftware/32/2764_2.png) [@AliSoftware](https://forums.swift.org/u/AliSoftware)\
**Post date:** [February 25, 2020, 7:24pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/27 "2020-02-25T19:24:43Z")

</div>

> I think the ideal long-term solution would use varadic generics instead of having to introduce a type-erased `SortDescriptor` wrapper:

@cal Also, note that in my implementation, the `SortDescriptor` type doesn't have to be type-erased, as it's only generic over the `Collection.Element`, not over the `Part` of the `KeyPath<Whole, Part>` used to build it.

Which is why I'm able –even in today's Swift without variadic generics– to pass an array of `SortDescriptor<User>` in my examples even if each one extract a different property type from the `Element` 🙂

---

<div class="post-metadata">

**Author:** ![cal](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cal/32/35557_2.png) [@cal](https://forums.swift.org/u/cal)\
**Post date:** [February 25, 2020, 7:26pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/28 "2020-02-25T19:26:00Z")

</div>

> [@suyashsrijan](#):
>
> I think it might also be nice to be able to do something like this:
> 
> ```swift
> users.sorted(<, by: \.name)
> 
> ```

We [pitched this design](https://forums.swift.org/t/map-sorting/21421) in May 2019 and the core team decided [not to move forward with it](https://forums.swift.org/t/map-sorting/21421/53).

---

<div class="post-metadata">

**Author:** ![cal](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cal/32/35557_2.png) [@cal](https://forums.swift.org/u/cal)\
**Post date:** [February 25, 2020, 7:27pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/29 "2020-02-25T19:27:21Z")

</div>

> [@AliSoftware](#):
>
> Also, note that in my implementation, the `SortDescriptor` type doesn't have to be type-erased, as it's only generic over the `Collection.Element` , not over the `Part` of the `KeyPath<Whole, Part>` used to build it.

This is the definition of type-erasure (you're erasing `<Whole, Part>` to just `<Whole>`)

---

<div class="post-metadata">

**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\
**Post date:** [February 25, 2020, 8:16pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/30 "2020-02-25T20:16:22Z")

</div>

Thanks for bringing this up again, @AliSoftware! It would be fantastic to expand the standard library's capabilities in this area. There are several moving parts to consider in this area:

- What does a `SortDescriptor` type provide that improves on using a simple `(Element) -> T` closure?
- How does this expanded notion of sorting interact with the design of a potential `SortedCollection` protocol and future concrete sorted collections?
- What kinds of optimizations are enabled by a proposed solution?
- What about persistence? For example, if I'm displaying a spreadsheet, I might want to sort on multiple columns, but have that be independent of the way my data is stored.
- What other sorting algorithms are we waiting for in the standard library? A partial sort, at minimum, would be valuable for finding the smallest or largest `n` items in a collection.
- Are there language features that would improve the experience of a particular solution? We can use key-path expressions in place of closures now; a `ExpressibleByKeyPathExpression` protocol could make it possible to use those expressions to form `SortDescriptor`s as well.
- Finally, there's also some research to do, in looking at the way other libraries have solved this problem (like `NSSortDescriptor`, of course).

I think we'll need to explore each of these questions to know when we have a stdlib addition that hits the right notes. Much of that exploration has already taken place on these forums, so part of the work is bringing that together. Would you like to take a look at that?

---

<div class="post-metadata">

**Author:** ![AliSoftware](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alisoftware/32/2764_2.png) [@AliSoftware](https://forums.swift.org/u/AliSoftware)\
**Post date:** [February 27, 2020, 5:12pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/31 "2020-02-27T17:12:26Z")

</div>

Thanks for the answer @nnnnnnnn

> "What does `SortDescriptor` provide that a `(Element) -> T` closure wouldn't

Mostly:

1. ability to reverse the sort (because `T` can be anything so unlike a `Bool` that you can just invert to revert the sort, if you pass a `KeyPath` (which would be turned into a closure as per SE-249) it's not enough to be able to revert the sort
2. ability to pass multiple sorting keys (KeyPaths) even if they are KeyPath to properties of different types

But tbh **I would already be happy with the stdlib just having a `sorted(by: (Element) -> T), using comparator: (T, T) -> Bool` with `comparator` defaulting to `<` when `T: Comparable`**. That would not support multiple-keys sorting, but that's a rather rare use case anyway so I'd be ok with this.

> - How does this expanded notion of sorting interact with the design of a potential `SortedCollection` protocol and future concrete sorted collections?

I missed that this was a thing in the works. Good point, if we consider having `SortedCollection` or other similar concepts in the future, let's wait for those to settle. Is there already some kind of Manifesto started about that?

> What kinds of optimizations are enabled by a proposed solution?

I haven't done any in-depth analysis of performance optimization but since `SortDescriptor` ends up being just a wrapper to construct a type-erased closure from a `KeyPath`, I'm assuming that with optimization enabled on the compiler it wouldn't be less performant that building the closure yourself.

The main point of the proposal is not about improving performance of the sorting algorithm but to improve the API of `Collection` by avoiding useless typing in the most common case where you want to sort by a property of `Element`, while avoid the risk of error that arise when repeating that property twice in the closure for the current statu-quo

> - What about persistence? For example, if I'm displaying a spreadsheet, I might want to sort on multiple columns, but have that be independent of the way my data is stored.

Sorry but I don't see how that question fits with the original topic proposed here? This is a different problem and question, that actually already applies to using closures with the current `sort(by:)` API and is not specific to the new API with `KeyPath` or `SortDescriptor`, is it?

> - What other sorting algorithms are we waiting for in the standard library? A partial sort, at minimum, would be valuable for finding the smallest or largest `n` items in a collection.

I see your point, but I'm not sure this is completely relevant to the problem we're trying to solve with this `sort(by: [SortDescriptor])` API here. Again, the point of the suggested new `sort(by: [SortDescriptor])` API is to be a convenience entry point for the existing `sort(by: (Element, Element) -> Bool)` that allows to construct that closure more easily by passing one or multiple `KeyPath` (wrapped in a `SortDescriptor`… or not if we abandon the `SortDescriptor` idea to support multiple-keys sorting and go straight to `KeyPath` with single-property sorts)

* * *

In the end, I'd agree to drop the `SortDescriptor` idea given how it's controversial to add that new type in the stdlib. But would it be acceptable to at least add the one with `KeyPath` to the stdlib?

```swift
extension Collection {
  func sorted<T>(by keyPath: KeyPath<Element, T>, using: (T, T) -> Bool) -> [Element] {
    sort(by: { using($0[keyPath: keyPath], $1[keyPath: keyPath]) })
  }
  func sort<T: Comparable>(by keyPath: KeyPath<Element, T>) -> Element {
    sort(by: keyPath, using: <)
  }
}

```

---

<div class="post-metadata">

**Author:** ![jenox](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jenox/32/5811_2.png) [@jenox](https://forums.swift.org/u/jenox)\
**Post date:** [February 27, 2020, 5:42pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/32 "2020-02-27T17:42:22Z")

</div>

Personally I would prefer the closure version `func sorted<T>(by transform: (Element) -> T, using areInIncreasingOrder: (T, T) -> Bool)` you mentioned above instead of restricting ourselves to key paths, especially since key paths can be used as closures in Swift 5.2.

---

<div class="post-metadata">

**Author:** ![AliSoftware](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alisoftware/32/2764_2.png) [@AliSoftware](https://forums.swift.org/u/AliSoftware)\
**Post date:** [February 27, 2020, 7:17pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/33 "2020-02-27T19:17:49Z")

</div>

I like that too 👍

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [February 27, 2020, 8:12pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/34 "2020-02-27T20:12:55Z")

</div>

For sorting with multiple predicates (sort by this, then by that, etc.), one option is a `SortKey` type with static `.by()` methods to enable code like this:

```swift
let list = people.sorted(
  .by(\.age, >),
  .by(\.name),
  .by(\.favoriteNumber, { abs($0 - .pi) < abs($1 - .pi) })
)

```

The implementation is pretty straightforward:

> **Basic SortKey type**
>
> ```swift
> struct SortKey<T> {
> var comparison: (T,T)->Bool
> }
> 
> ```

> **Static .by() methods**
>
> ```swift
> extension SortKey {
> // .by(\.key, >)
> static func by<U>(_ transform: @escaping (T)->U, _ areInIncreasingOrder: @escaping (U,U)->Bool) -> SortKey {
> return SortKey{ areInIncreasingOrder(transform($0), transform($1)) }
> }
> 
> // .by(\.key)
> static func by<U: Comparable>(_ transform: @escaping (T)->U) -> SortKey {
> return SortKey.by(transform, <)
> }
>   
> // .by(customComparison)
> static func by(_ areInIncreasingOrder: @escaping (T,T)->Bool) -> SortKey {
> return SortKey(comparison: areInIncreasingOrder)
> }
> }
> 
> ```

> **KeyPath versions for those not yet on Swift 5.2**
>
> ```swift
> extension SortKey {
> static func by<U>(_ path: KeyPath<T, U>, _ areInIncreasingOrder: @escaping (U,U)->Bool) -> SortKey {
> return SortKey.by({ $0[keyPath: path] }, areInIncreasingOrder)
> }
>   
> static func by<U: Comparable>(_ path: KeyPath<T, U>) -> SortKey {
> return SortKey.by(path, <)
> }
> }
> 
> ```

> **Combining multiple SortKeys**
>
> ```swift
> extension SortKey {
> static func merging(_ keys: [SortKey]) -> SortKey {
> return SortKey {
> for key in keys {
> if key.comparison($0, $1) { return true }
> if key.comparison($1, $0) { return false }
> }
> return false
> }
> }
> }
> 
> ```

> **Sorting**
>
> ```swift
> extension Sequence {
> func sorted(byKeys keys: [SortKey<Element>]) -> [Element] {
> return self.sorted(by: SortKey.merging(keys).comparison)
> }
>   
> func sorted(_ keys: SortKey<Element>...) -> [Element] {
> return self.sorted(byKeys: keys)
> }
> }
> 
> extension MutableCollection where Self: RandomAccessCollection {
> mutating func sort(byKeys keys: [SortKey<Element>]) {
> sort(by: SortKey.merging(keys).comparison)
> }
>   
> mutating func sort(_ keys: SortKey<Element>...) {
> sort(byKeys: keys)
> }
> }
> 
> ```

This is all possible today without any new language features (indeed the code here already works). It’s also possible to support `throws` as well, but not `rethrows`, so that’s a hypothetical future enhancement.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [February 28, 2020, 10:25pm UTC](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276/35 "2020-02-28T22:25:40Z")

</div>

For single predicates, I think it’s important to be able to specify the order (if desired). That is, if we have dedicated functions for the simple case, then all of the following should work:

```swift
people.sorted(by: \.age) // Youngest first
people.sorted(>, by: \.age) // Oldest first
people.sorted{ abs($0.age - 30) } // Closest to 30 first
people.sorted(>){ abs($0.age - 30) } // Furthest from 30 first

```

Note that the sort order is the first argument, which both aligns with the existing sort functions, and also leaves the trailing closure position for the more-likely-to-be-customized transform.

> **Implementation**
>
> ```swift
> extension Sequence {
> func sorted<T>(_ areInIncreasingOrder: (T,T)throws->Bool, by transform: (Element)throws->T) rethrows -> [Element] {
> return try self.sorted{ try areInIncreasingOrder(transform($0), transform($1)) }
> }
>   
> func sorted<T: Comparable>(by transform: (Element)throws->T) rethrows -> [Element] {
> return try self.sorted(<, by: transform)
> }
> }
> 
> extension MutableCollection where Self: RandomAccessCollection {
> mutating func sort<T>(_ areInIncreasingOrder: (T,T)throws->Bool, by transform: (Element)throws->T) rethrows {
> try self.sort{ try areInIncreasingOrder(transform($0), transform($1)) }
> }
>   
> mutating func sort<T: Comparable>(by transform: (Element)throws->T) rethrows {
> try self.sort(<, by: transform)
> }
> }
> 
> ```

> **KeyPath versions**
>
> ```swift
> extension Sequence {
> func sorted<T>(_ areInIncreasingOrder: (T,T)throws->Bool, by path: KeyPath<Element,T>) rethrows -> [Element] {
> return try self.sorted{ try areInIncreasingOrder($0[keyPath: path], $1[keyPath: path]) }
> }
>   
> func sorted<T: Comparable>(by path: KeyPath<Element,T>) -> [Element] {
> return self.sorted(<, by: path)
> }
> }
> 
> extension MutableCollection where Self: RandomAccessCollection {
> mutating func sort<T>(_ areInIncreasingOrder: (T,T)throws->Bool, by path: KeyPath<Element,T>) rethrows {
> try self.sort{ try areInIncreasingOrder($0[keyPath: path], $1[keyPath: path]) }
> }
>   
> mutating func sort<T: Comparable>(by path: KeyPath<Element,T>) {
> self.sort(<, by: path)
> }
> }
> 
> ```

[Previous page](https://forums.swift.org/t/sorting-collections-with-map-closures-and-sortdescriptors/16276.md?page=1)