Mastering Swift 4.1: Recursive Associated Types and Type Erasers Explained

1. Recursive Associated‑Type Constraints in Swift 4.1

Prior to Swift 4.1, trying to declare SubSequence : Sequence inside the Sequence protocol caused the compiler error Type may not reference itself as a requirement. The language therefore forced developers to write the constraint as a comment, which was both verbose and error‑prone.

Swift 4.1 introduces official support for recursive constraints, allowing the associated type to be defined in terms of the protocol itself.

2. Full Definition of the Updated Sequence Protocol

protocol Sequence {
    associatedtype Element
    associatedtype Iterator : IteratorProtocol where Iterator.Element == Element
    associatedtype SubSequence : Sequence = AnySequence<Element>
        where Element == SubSequence.Element,
              SubSequence.SubSequence == SubSequence
    // ... other requirements ...
}

The new definition adds three associated types ( Element, Iterator, SubSequence) and a series of where clauses that tie them together recursively.

3. What the Constraints Mean

Iterator must conform to IteratorProtocol .

Iterator.Element must be the same type as Sequence.Element , establishing a link between the iterator and the sequence.

SubSequence must itself be a Sequence , creating the recursive definition.

The Element of SubSequence must match the Element of the parent Sequence .

Because of the recursive constraints, SubSequence.Iterator.Element automatically aligns with the other Element types, so no extra declaration is needed.

SubSequence.SubSequence is the same type as SubSequence , reinforcing the recursion.

The default concrete type for SubSequence is AnySequence<Element> , which satisfies all the requirements, including the return type of dropFirst . For example, Array.SubSequence is ArraySlice , which also conforms.

4. Building a Minimal DummySequence

With the new constraints, a very simple sequence can be compiled:

struct DummySequence<Element>: Sequence {
    typealias Iterator = AnyIterator<Element>
    typealias SubSequence = AnySequence<Element>
    func makeIterator() -> AnyIterator<Element> {
        return AnyIterator { nil }
    }
}

The two typealias lines can even be omitted because the compiler can infer them from the default implementations.

5. Why AnySequence Matters

AnySequence

is a type‑erasing wrapper that hides the concrete sequence type while preserving the required interface. It is used throughout the standard library (e.g., AnyHashable, AnyIterator) to provide a uniform generic façade.

6. Implementing a Custom Type‑Eraser: AnyList

When a protocol like List is not generic itself, a type‑erasing wrapper is needed to store heterogeneous conforming types in a single collection.

struct AnyList<Element>: List {
    private let elementFunc: (Int) -> Element?
    init<L>(_ base: L) where Element == L.Element, L : List {
        elementFunc = base.element(at:)
    }
    func element(at index: Int) -> Element? {
        return elementFunc(index)
    }
}

This wrapper hides the concrete list type and lets us write:

let intLists = [AnyList(IntArrayList()), AnyList(IntLinkedList())]
for l in intLists { _ = l.element(at: 0) }

Similarly, a mixed collection of IntLinkedList and DoubleLinkedList can be built using AnyList.

7. Summary

The introduction of recursive associated‑type constraints in Swift 4.1 removes a long‑standing limitation, enabling protocols like Sequence to express their own sub‑sequence relationship directly. Combined with type‑erasing wrappers such as AnySequence and custom AnyList, developers can write concise, generic code and store heterogeneous collections without sacrificing type safety.