Swift Generics, Constraints, and KeyPaths

Question

I'm aware of the limitations of generics in Swift and why they exist so this is not a question about compiler errors. Rather, I occasionally run into situations that seem as though they should be possible with some combination of the resources available in (i.e. generics, associatedTypes/protocols, etc) but can't seem to work out a solution.

In this example, I'm trying to come up with a Swift replacement for NSSortDescriptor (just for fun). It works perfect when you only have one descriptor but, as is often done with the NS version, it would be nice to create an array of SortDescriptors to sort on multiple keys.

The other trial here is using Swift KeyPaths. Because those require a Value type and the comparison requires a Comparable value, I'm running into trouble figuring out where/how to define the types to satisfy everything.

Is this possible? Here is one of the closest solutions I've come up with, but, as you can see at the bottom, it falls short when building an array.

Again, I understand why this doesn't work as is, but am curious if there is a way to achieve the desired functionality.

struct Person {
    let name : String
    let age : Int

}
struct SortDescriptor<T, V:Comparable> {
    let keyPath: KeyPath<T,V>
    let ascending : Bool
    init(_ keyPath: KeyPath<T,V>, ascending:Bool = true) {
        self.keyPath = keyPath
        self.ascending = ascending
    }
    func compare(obj:T, other:T) -> Bool {
        let v1 = obj[keyPath: keyPath]
        let v2 = other[keyPath: keyPath]
        return ascending ? v1 < v2 : v2 < v1
    }
}

let jim = Person(name: "Jim", age: 30)
let bob = Person(name: "Bob", age: 35)
let older = SortDescriptor(\Person.age).compare(obj: jim, other: bob) // true

// Heterogeneous collection literal could only be inferred to '[Any]'; add explicit type annotation if this is intentional
var descriptors = [SortDescriptor(\Person.age), SortDescriptor(\Person.name)]

Guernica

Answer 1

The problem here is that SortDescriptor is generic on both T and V, but you only want it to be generic on T. That is, you want a SortDescriptor<Person>, because you care that it compares Person. You don't want a SortDescriptor<Person, String>, because once it's created, you don't care that it's comparing on some String property of Person.

Probably the easiest way to “hide” the V is by using a closure to wrap the key path:

struct SortDescriptor<T> {
    var ascending: Bool

    var primitiveCompare: (T, T) -> Bool

    init<V: Comparable>(keyPath: KeyPath<T, V>, ascending: Bool = true) {
        primitiveCompare = { $0[keyPath: keyPath] < $1[keyPath: keyPath] }
        self.ascending = ascending
    }

    func compare(_ a: T, _ b: T) -> Bool {
        return ascending ? primitiveCompare(a, b) : primitiveCompare(b, a)
    }
}

var descriptors = [SortDescriptor(keyPath: \Person.name), SortDescriptor(keyPath: \.age)]
// Inferred type: [SortDescriptor<Person>]

After that, you may want a convenient way to use a sequence of SortDescriptor to compare to objects. For that, we'll need a protocol:

protocol Comparer {
    associatedtype Compared
    func compare(_ a: Compared, _ b: Compared) -> Bool
}

extension SortDescriptor: Comparer { }

And then we can extend Sequence with a compare method:

extension Sequence where Element: Comparer {

    func compare(_ a: Element.Compared, _ b: Element.Compared) -> Bool {
        for comparer in self {
            if comparer.compare(a, b) { return true }
            if comparer.compare(b, a) { return false }
        }
        return false
    }

}

descriptors.compare(jim, bob)
// false

If you're using a newer version of Swift with conditional conformances, you should be able to conditionally conform Sequence to Comparer by changing the first line of the extension to this:

extension Sequence: Comparer where Element: Comparer {

Benfield

Nice! I had played with closures as the sort descriptor (typealias). but it lacked the clarity I was looking for and the ascending option. – Guernica

Any suggestions for handling optional values as well? – Guernica

Seems like a second initializer for V? would do it, obviously creating a different closure. – Guernica

Answer 2

Expanding on @Rob Mayoff's answer, here's a full sorting solution

enum SortDescriptorComparison {
    case equal
    case greaterThan
    case lessThan
}

struct SortDescriptor<T> {
    private let compare: (T, T) -> SortDescriptorComparison
    let ascending : Bool

    init<V: Comparable>(_ keyPath: KeyPath<T,V>, ascending:Bool = true) {
        self.compare = {
            let v1 = $0[keyPath: keyPath]
            let v2 = $1[keyPath: keyPath]
            if v1 == v2 {
                return .equal
            } else if v1 > v2 {
                return .greaterThan
            } else {
                return .lessThan
            }
        }
        self.ascending = ascending
    }

    func compare(v1:T, v2:T) -> SortDescriptorComparison {
        return compare(v1, v2)
    }
}

extension Array {

    mutating func sort(sortDescriptor: SortDescriptor<Element>) {
        self.sort(sortDescriptors: [sortDescriptor])
    }

    mutating func sort(sortDescriptors: [SortDescriptor<Element>]) {
        self.sort() {
            for sortDescriptor in sortDescriptors {
                switch sortDescriptor.compare(v1: $0, v2: $1) {
                case .equal:
                    break
                case .greaterThan:
                    return !sortDescriptor.ascending
                case .lessThan:
                    return sortDescriptor.ascending
                }
            }
            return false
        }
    }
}

extension Sequence {

    func sorted(sortDescriptor: SortDescriptor<Element>) -> [Element] {
        return self.sorted(sortDescriptors: [sortDescriptor])
    }

    func sorted(sortDescriptors: [SortDescriptor<Element>]) -> [Element] {
        return self.sorted() {
            for sortDescriptor in sortDescriptors {
                switch sortDescriptor.compare(v1: $0, v2: $1) {
                case .equal:
                    break
                case .greaterThan:
                    return !sortDescriptor.ascending
                case .lessThan:
                    return sortDescriptor.ascending
                }
            }
            return false
        }
    }
}

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

let jim = Person(name: "Jim", age: 25)
let bob = Person(name: "Bob", age: 30)
let tim = Person(name: "Tim", age: 25)
let abe = Person(name: "Abe", age: 20)

let people = [tim, jim, bob, abe]
let sorted = people.sorted(sortDescriptors: [SortDescriptor(\Person.age), SortDescriptor(\Person.name)])

print(sorted) //Abe, Jim, Time, Bob

Mathildemathis

I did not expect the Swift solution as tiny, clear and readable as its Objective-C counterpart. – Adamant

I'd mark both correct if I could, +1 for the sort additional extensions. – Guernica

Answer 3

Here's an almost purely functional solution:

// let's add some semantics
typealias SortDescriptor<T> = (T, T) -> Bool

// type constructor for SortDescriptor
func sortDescriptor<T, U: Comparable>(keyPath: KeyPath<T, U>, ascending: Bool) -> SortDescriptor<T> {
    return { ascending == ($0[keyPath: keyPath] < $1[keyPath: keyPath]) }
}

// returns a function that can sort any two element of type T, based on
// the provided list of descriptors
func compare<T>(with descriptors: [SortDescriptor<T>]) -> (T, T) -> Bool {
    func innerCompare(descriptors: ArraySlice<SortDescriptor<T>>, a: T, b: T) -> Bool {
        guard let descriptor = descriptors.first else { return false }
        if descriptor(a, b) { return true }
        else if descriptor(b, a) { return false }
        else { return innerCompare(descriptors: descriptors.dropFirst(1), a: a, b: b) }
    }
    return { a, b in innerCompare(descriptors: descriptors[0...], a: a, b: b) }
}

// back to imperative, extend Sequence to allow sorting with descriptors
extension Sequence {
    func sorted(by descriptors: [SortDescriptor<Element>]) -> [Element] {
        return sorted(by: compare(with: descriptors))
    }
}

It's based on small, reusable functions, like compare(), that can be easily reused in other scopes.

Usage example:

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

let jim = Person(name: "Jim", age: 30)
let bob = Person(name: "Bob", age: 35)
let alice = Person(name: "Alice", age: 35)
let aly = Person(name: "Aly", age: 32)

let descriptors = [sortDescriptor(keyPath: \Person.age, ascending: false),
                   sortDescriptor(keyPath: \Person.name, ascending: true)]
let persons = [jim, bob, alice, aly]
print(persons.sorted(by: descriptors))

Kareem