Emulating variadic generics in Swift

Introduction

Swift does not have variadic generics. They are listed as a major item in the Generics Manifesto, but that is something for the future. Today, we cannot make a variadic list of generic parameters in Swift.

In this thread, we will be making a variadic list of generic parameters in Swift.

…okay, we won’t quite be doing that. But we *will* be making a variadic function where each argument has its own individual generic parameters. That’s basically the same thing, right?

Motivation: Variadic Sorting

Let’s begin with an example. Suppose we have a list of animals, and we want to sort them first by name, then by age, and so forth. We can imagine what a call-site might look like:

animals.sort(\.name, \.age, \.weight)

Of course, this won’t work. There are multiple problems with what we just wrote. The obvious one is that we don’t have a way to specify what sort-order we want for each parameter.

But the more fundamental problem is that key-paths are generic:
\.name is a KeyPath<Animal, String>
\.age is a KeyPath<Animal, Int>
\.weight is a KeyPath<Animal, Double>

Their second generic parameters are different, so if we attempt to write the sort function above, we’ll quickly find that we would need variadic generics to define its argument types.

• • •

We need a new type—a wrapper type—and it needs to erase the second generic parameter from KeyPath. Also, we’ll want it to store a predicate function so we can specify sort order. And we might as well give it a shorthand constructor for ease of use.

If we can write such a type, then the sort function could be called like this:

animals.sort(.by(\.name), .by(\.age), .by(\.weight))

Or this:

animals.sort(.by(\.name,   <),
             .by(\.age,    >),
             .by(\.weight, <))

That looks pretty useful, and reasonably compact.

So, is it possible to implement? Yes!

SortKey

Since our new type—let’s call it SortKey—must erase a generic parameter from KeyPath, we’ll want it to be a class with a private subclass that still has the parameter. However, we want SortKey to preserve the first generic parameter, since the key-paths all need to have the same root type when we sort.

Here is the core implementation of this class:

class SortKey<Root> {
  func areInIncreasingOrder(_ x: Root, _ y: Root) -> Bool {
    fatalError("Must override")
  }
}

All it has is a hook for sort to call, which doesn’t even do anything. Plus this class has no initializer, so to use it we’ll need some other way to construct one. That’s where the by() function comes in:

extension SortKey {
  static func by<Value: Comparable>(_ keyPath: KeyPath<Root, Value>) -> SortKey {
    return Impl(keyPath, <)
  }
  
  static func by<Value>(_ keyPath: KeyPath<Root, Value>,
                        _ areInIncreasingOrder: @escaping (Value, Value) -> Bool
    ) -> SortKey {
    return Impl(keyPath, areInIncreasingOrder)
  }
}

Notice we have two by() functions, which are both generic, and both take a KeyPath. One of them also takes a predicate, while the other (for Comparable types) instead uses the default “<” ordering. Also notice that these both return an instance of the Impl subclass.

SortKey.Impl

What should Impl look like? Well for starters, it must store a key-path and a sort predicate. Then it needs an initializer. And we want it to override the areInIncreasingOrder hook to evaluate the predicate through the key-path:

extension SortKey {
  private final class Impl<Value>: SortKey {
    var keyPath: KeyPath<Root, Value>
    var compare: (Value, Value) -> Bool
    
    init(_ keyPath: KeyPath<Root, Value>,
         _ compare: @escaping (Value, Value) -> Bool) {
      self.keyPath = keyPath
      self.compare = compare
    }
    
    override func areInIncreasingOrder(_ x: Root, _ y: Root) -> Bool {
      return compare(x[keyPath: keyPath], y[keyPath: keyPath])
    }
  }
}

There’s a lot going on here, but hopefully each piece makes sense on its own. This is actually a full working implementation of both SortKey and SortKey.Impl.

It is not entirely obvious at a glance, but Impl in fact has two generic parameters, Root and Value. If we moved Impl out of an extension and up to the file scope, we would have to list them both, and that it is a subclass of SortKey<Root>.

Variadic Sorting

Now that we have written our wrapper types, let’s see what the implementation of sort might look like. Actually, let’s start with sorted:

extension Sequence {
  func sorted(_ first: SortKey<Element>, _ others: SortKey<Element>...) -> [Element] {
    var result = Array(self)
    result.sort(first, others)
    return result
  }
}

Well that’s pretty straightforward, why did we even bother writing out? Because of that call it makes to sort with two arguments. That is not simply a call to the variadic sort we have been talking about, because it passes a whole array of SortKeys as a single argument.

If Swift had variadic “splatting”, then we could splat the array into the variadic call. But it doesn’t, so we can’t. Instead, we will write our implementation for this two-argument version, and call it from sort as well as sorted:

extension MutableCollection where Self: RandomAccessCollection {
  mutating func sort(_ first: SortKey<Element>, _ others: [SortKey<Element>]) {
    sort{ (x, y) -> Bool in
      if first.areInIncreasingOrder(x, y) { return true }
      if first.areInIncreasingOrder(y, x) { return false }
      for next in others {
        if next.areInIncreasingOrder(x, y) { return true }
        if next.areInIncreasingOrder(y, x) { return false }
      }
      return false
    }
  }
}

This method calls the standard library sort(by:) method, passing in a closure that uses the areInIncreasingOrder hook on SortKey, which is dynamically dispatched to the Impl subclass because that’s all we ever actually work with.

If the two elements being compared are seen as equivalent by one SortKey, then it checks the next SortKey and so on. This is exactly what we want to have happen when we sort first by one key then by another.

• • •

And now, finally, we can write the sort function that we originally wanted:

extension MutableCollection where Self: RandomAccessCollection {
  mutating func sort(_ first: SortKey<Element>, _ others: SortKey<Element>...) {
    sort(first, others)
  }
}

This is variadic, and each argument has its own hidden generic parameter, so the wrapped key-paths can point to different value types. That is, the arguments will always be SortKey.Impl instances. Thus we have achieved, at least in this particular case, an implementation of variadic generics, despite that feature not actually existing.

Throwing

Of course, we wrote everything here as non-throwing. And we can’t use rethrows since the predicates get stored to variables. In order to allow throwing predicates, we must add throws and try everywhere.

To emulate rethrows, we can copy-and-paste everything to make a new class, say SortKeyThrows, and just add the annotations there. And the same for sort and sorted. That way call-sites that use throwing predicates will get the throwing version and must write try, while call-sites that don’t, won’t.

Conclusion

This has been a summary of one possible workaround for the fact that Swift does not currently support variadic generics. I hope you found the ideas to be interesting and potentially useful.

In the future, if Swift gets variadic generics, then we can eliminate the subclass and make SortKey have two generic parameters. And if Swift also gets an ExpressibleByKeyPathLiteral protocol, then we can remove calls to the by() function when the default sort order is desired.

Alternatively, if Swift gets both ExpressibleByKeyPathLiteral and factory initializers (meaning the initializer can return a subclass), then even without variadic generics we could still eliminate calls to by().

But for now, the way things currently stand, we can at least emulate some of the behavior of variadic generics, as described.

15 Likes

I appreciate this post, thank you.

Implementing "Type Erasure" is an important skill for Swift developers. It can be achieved through different techniques. I discovered one I wasn't familiar with today: the private generic subclass.

And we now have a handy sorting method :-)

2 Likes

What this example also highlights is, that we still do tend to fake abstract classes in many scenarios. Sure fatalError and dynamic dispatch without the call to the super implementaion does the trick, but still abstract classes are very useful. Especially it would shine when the abstract class must be open.

3 Likes

As a follow-up, if Swift does get ExpressibleByKeyPathLiteral, even without any other new features beyond that, we can make a slight change that will let us eliminate .by() when using the default sort order, and achieve the originally desired syntax,

animals.sort(\.name, \.age, \.weight)

Again, this is a future direction and not currently possible, but here’s how it would work:

First we’d rename SortKey to _SortKey (and make it private). Then we’d make a new type named SortKey (which could be a struct or a final class) as a wrapper around _SortKey, that has an identical interface and just passes along calls to the wrapped instance.

Doing so might sound tedious and pointless, but there’s actually a good reason for it. This way we can write a proper initializer on SortKey, rather than needing to return a subclass. And that means it can conform to protocols which require an initializer, like the hypothetical ExpressibleByKeyPathLiteral.

Here’s how it might look (minus the protocol that doesn’t exist yet):

struct SortKey<Root> {
  private var wrapped: _SortKey<Root>
  
  private init(_ wrapped: _SortKey<Root>) {
    self.wrapped = wrapped
  }
  
  func areInIncreasingOrder(_ x: Root, _ y: Root) -> Bool {
    return wrapped.areInIncreasingOrder(x, y)
  }
  
  static func by<Value: Comparable>(_ keyPath: KeyPath<Root, Value>) -> SortKey {
    return SortKey(.by(keyPath, <))
  }
  
  static func by<Value>(_ keyPath: KeyPath<Root, Value>,
                        _ areInIncreasingOrder: @escaping (Value, Value) -> Bool
    ) -> SortKey {
    return SortKey(.by(keyPath, areInIncreasingOrder))
  }
}

In fact with this implementation, we can remove the one-argument by() function from _SortKey entirely, since we only ever call the two-argument version.

I don't get it. Why wouldn't this work?

struct SortKey<Root> {
    let areInIncreasingOrder: (Root, Root) -> Bool
}

extension SortKey {
    static func by<Value>(
        _ keyPath: KeyPath<Root, Value>,
        _ areInIncreasingOrder: @escaping (Value, Value) -> Bool
    ) -> SortKey {
        return SortKey { x, y in
            areInIncreasingOrder(x[keyPath: keyPath], y[keyPath: keyPath])
        }
    }
    static func by<Value: Comparable>(_ keyPath: KeyPath<Root, Value>) -> SortKey {
        return by(keyPath, <)
    }
}

Well, in fact, you could go further and just get rid of any additional structures and just use only closures.

extension Sequence {
  typealias Ordering = (Element, Element) -> Bool
  func sorted(_ predicate: Ordering,  _ predicates: Ordering...) -> [Element] {
    return sorted { a, b in
      if predicate(a, b) { return true }
      if predicate(b, a) { return false }
      for p in predicates {
        if p(a, b) { return true }
        if p(b, a) { return false }
      }
      return false
    }
  } 
}

func by<T: Comparable, R>(
  _ path: KeyPath<R, T>, 
  _ order: @escaping (T, T) -> Bool = (<)
) -> (R, R) -> Bool {
  return { a, b in
    return order(a[keyPath: path], b[keyPath: path])
  }
}

animals.sorted(by(\.name), by(\.age, >), by(\.mass))

But none the less some proper variadic generics will still be very nice to have. ExpressibleByKeyPathLiteral would also be very welcome IMO.

2 Likes

Yes, that was kinda my point. That this is just really a closure, and nothing more. I was just replicating the original syntax. Using a free function works just as well.

Using a private abstract base class with a concrete generic sub class, or using free functions (closures), in my opinion, are just 2 ways to implement type erasure.

The key point the author wants to say here, correct me if I'm wrong, is that variadic generics can help to avoid implementing type erasure in this particular case.

Terms of Service

Privacy Policy

Cookie Policy