Protocol ‘SequenceType’ can only be used as a generic constraint …

In Swift, a protocol can have an associated type, which is kinda like generics, except it isn’t. This is most often apparent when trying to use it as such. You’ve probably seen the compiler complain: Protocol 'SequenceType' can only be used as a generic constraint. In this post we explore why, and how to solve it.

Swift supports generic code. From the book Swift Programming Language we can read:

Generics are one of the most powerful features of Swift, and much of the Swift standard library is built with generic code. In fact, you’ve been using generics throughout the Language Guide, even if you didn’t realize it. For example, Swift’s Array and Dictionary types are both generic collections. You can create an array that holds Int values, or an array that holds String values, or indeed an array for any other type that can be created in Swift. Similarly, you can create a dictionary to store values of any specified type, and there are no limitations on what that type can be.

With generics, you don’t simply declare a variable to be an array, but also what kind of array! Whereas NSArray can hold any heterogenous collection of elements, with Swift’s strong type system we can guarantee that an array only holds a certain kind of elements.

var numbers: [Int]

The example above is just syntactic sugar for a more general language feature:

var numbers: Array<Int>

(Of course, a Swift array can hold AnyObject or NSObject as its elements, and in fact NSArray is bridged into Swift like that.)

Protocols and associated types

This works well for concrete types such as structs, classes and enums. But what about protocols? They can’t have generic types, but they have something similar: Associated types.

For instance, Array<Int> conforms to SequenceType, and any function that operates on a SequenceType (which may or may not be an array), needs to know about the kind of type it is a sequence of. Enter associated types. The SequenceType protocol declares an associated type, and when conforming to the protocol, the conforming type must declare (possibly implicitly) what its associated type is.

For generic structs that conform to a protocol with an associated type, these are often the same. But not always. Dictionary<Key, Value> also conforms to SequenceType, but the dictionary have two generic types, but the protocol only has one associated type. When iterating over a dictionary as a sequence, you may have noticed that you get tuples of both the key and the value? Hence, Dictionary declares the tuple type (Key, Value) as the associated type when conforming to SequenceType.

The problem

However, there is a problem: You cannot declare a variable to be of type SequenceType<Int>. If you do not care what kind of sequence you deal with, as long as its associated type are Ints, there is no way to do that, except as a constraint in a generic function signature.

You may have seen these errors:

let numberSequence: SequenceType<Int>
// ⛔️ Cannot specialize non-generic type 'SequenceType'
let numberSequence: SequenceType
// ⛔️ Protocol 'SequenceType' can only be used as a generic constraint because it has Self or associated type requirements.

Type erasure

The solution to this problem is a technique known as “type erasure”. By wrapping the protocol-conforming type (and its associated type) in a generic wrapper type, you loose type information, but you gain the option to store it as a typed value in a variable. The standard library offers a few of these concrete type erased wrappers, most notably AnySequence and AnyGenerator. It allow us to do this:

let numberSequence: AnySequence<Int> // ✅ compiler is happy

AnySequence itself conforms to SequenceType, and its generic type acts as the associated type for the protocol conformance. Let’s try to recreate the AnySequence object.

AnySequence

The type needs to conform to SequenceType, so we must implement its required methods. It also has to wrap any SequenceType-conforming type, so we need a constructor that takes a sequence as a parameter:

struct AnySequence<T>: SequenceType {
  init<S: SequenceType where S.Generator.Element == T>(_ seq: S)
  func generate() -> GeneratorType<T> // ⛔️ Protocol 'GeneratorType' can only be used as a generic constraint
  func underestimateCount() -> Int
}

We already get the same problem with our required generate() function, so we have to apply the same technique one more time. Down the rabbit hole we go!

struct AnySequence<T>: SequenceType {
  init<S: SequenceType where S.Generator.Element == T>(_ seq: S)
  func generate() -> AnyGenerator<T>
  func underestimateCount() -> Int
}
struct AnyGenerator<T>: GeneratorType {
  init<G: GeneratorType where G.Element == T>(_ gen: G)
  func next() -> T?
}

Ok, so we have our interface ready. Now, in our initializers we need to store enough information about our wrapped sequence/generators so that we can implement the required functions. However, we can’t simply store a reference to our wrapped sequence. This is exactly the problem we’re trying to solve, remember!

However, we do known the type of the next() function. It’s : () -> T?, and this type is usable as a type declaration in our AnyGenerator type:

struct AnyGenerator<T>: GeneratorType {
  private let _next: () -> T?

  init<G: GeneratorType where G.Element == T>(_ gen: G) {
    var gen = gen
    self._next = { gen.next() }
  }
  func next() -> T? {
    return _next()
  }
}

In our initializer, we simply store a function reference to the original next() and call that when our next() is called. Since our next() returns a T?, the compiler can infer that T acts as the associated type when conforming to GeneratorType. And since we restrict our initializer to only accept generator types with the same associated type T, we can now use this type to wrap any generator of any type T, and since our type is a concrete struct, we can store it in a variable if we want to.

We apply the same trick to our AnySequence and we’re done:

struct AnySequence<T>: SequenceType {
  private let _generate: () -> AnyGenerator<T>
  private let _underestimateCount: () -> Int

  init<S: SequenceType where S.Generator.Element == T>(_ seq: S) {
    self._generate = { AnyGenerator(seq.generate()) }
    self._underestimateCount = seq.underestimateCount
  }
  func generate() -> AnyGenerator<T> {
    return _generate()
  }
  func underestimateCount() -> Int {
    return _underestimateCount()
  }
}

Finally, we can now do this:

let numberSequence: AnySequence<Int>

Although this is already implemented (albeit in a slightly different way) in the Swift standard library, this technique is universally applicable. If you have a few types in your own app, that all conform to a certain protocol Foo with one or more associated types, you can similarly create an AnyFoo.