Swift 3 comes with a new model for collections. This is a major change, and you should read the proposal. But for the purpose of this post, you only need to know that:

Collection has acquired an associated Indices type that is always iterable

Collection keeps its associated Index type, used for subscripting, but it doesn’t have the same requirements as before (I won’t expand on that).
Moreover, the type of the indices property is no longer Range<Index> but Indices.

Succinctly, what was:

/// Returns the range of valid index values. …
var indices: Range<Index> { get }

is now:

/// A collection type whose elements are the indices of `self` that
/// are valid for subscripting, in ascending order.
associatedtype Indices : IndexableBase, Sequence // …
/// The indices that are valid for subscripting `self`, in ascending order. …
var indices: Indices { get }

The Problem

Given the definition of indices, can you spot the mistake in this snippet?

func index <C: Collection where 
    C.Iterator.Element: Equatable
> (of element: C.Iterator.Element, in collection: C) -> C.Index? {
    for i in collection.indices {
        if collection[i] == element { return i }
    }
    return nil
}

In an ideal world, there wouldn’t be an issue. The documentation clearly states that the values of indices can be used for subscripting the collection.

However, notice that there are no type constraints on the elements of Indices. The compiler doesn’t know that Indices.Iterator.Element should be the same type as Index, resulting in this error message:

Cannot subscript a value of type 'C' with an index of 
type 'C.Indices.Iterator.Element'

Cannot convert return expression of type 
'C.Indices.Iterator.Element' to return type 'C.Index?'

And in order to remove the error, we need to add an additional constraint:

func index <C: Collection where 
    C.Iterator.Element: Equatable, 
    C.Indices.Iterator.Element == C.Index
> (of element: C.Iterator.Element, in collection: C) -> C.Index? {
    for i in collection.indices {
        if collection[i] == element { return i }
    }
    return nil
}

Even if you ignore the awful indentation, this feels wrong. After all, I want my function to work on any collection, and it does work on any properly designed collection.

So why do I need to add a constraint?

Arbitrary Requirements

Currently, associated type declarations cannot use the powerful where clause available to protocol extensions and generics. They can only use basic inheritance constraints.

Simply put, we can’t do this:

protocol Collection {
    // …
    associatedtype Indices: IndexableBase, Sequence where Indices.Iterator.Element == Index
}

which is needed to properly define Indices.

There is a proposal on swift-evolution that aims to allow these constraints but it is out-of-scope for Swift 3. So we will have to live with poorly defined protocols for at least a few more months.

Recursive Constraints

You might have noticed something a bit odd about the declaration of Indices.

/// A collection type whose elements are the indices of `self` that
/// are valid for subscripting, in ascending order.
associatedtype Indices : IndexableBase, Sequence // …

Even though the documentation states that Indices should be a collection, its declaration only asks that it conforms to IndexableBase and Sequence. This stems, again, from a limitation of the language.

Associated types cannot conform to their enclosing protocols. Therefore, this results in an error:

protocol Collection {
    // …
    associatedtype Indices: Collection // recursive protocol constraint -> compilation error
}

And the core team decided to work around this issue by using two less demanding protocols (Sequence and IndexableBase).

A Correct Collection Protocol

Indices is not the only associated type that suffers from these shortcomings. The standard library is filled with approximations, and it is a good exercise to imagine what a more precise definition of a given protocol might be.

In the case of Collection:

protocol Collection {
    // CURRENT
    associatedtype Indices: IndexableBase, Sequence
    associatedtype Subsequence: IndexableBase, Sequence

    // IDEAL
    associatedtype Indices: Collection where Indices.Iterator.Element == Index
    associatedtype SubSequence: Collection where 
        SubSequence.Iterator.Element == Iterator.Element,
        SubSequence.Index == Index
}

In practice, these constraints are pushed to every consumer of Indices and SubSequence. So the signature of a function using some of the capabilities of a collection will look like this:

func foo <C: Collection where 
    C.Indices: Collection, 
    C.Indices.Iterator.Element == C.Index,
    C.SubSequence: Collection,
    C.SubSequence.Iterator.Element == C.Iterator.Element,
    C.SubSequence.Index == C.Index
> (collection: C) {
    //…
}

Fortunately, few functions involve subsequences, and we rarely need Indices to be a collection. However, we do need these requirements for a few common operations:

  • iterating over the indices of a collection and using them for subscripting
  • comparing the element of a subcollection to the original one
  • using the index of a subcollection on the original one

and they all require a bit of unintuitive boilerplate. You can even see these long lists of requirements in the standard library:

public init<Subject, C : Collection where C.Iterator.Element == Child, 
C.SubSequence : Collection, C.SubSequence.Iterator.Element == Child, 
C.SubSequence.Index == C.Index, C.SubSequence.Indices : Collection, 
C.SubSequence.Indices.Iterator.Element == C.Index, C.SubSequence.Indices.Index == C.Index, 
C.SubSequence.Indices.SubSequence == C.SubSequence.Indices, C.SubSequence.SubSequence == C.SubSequence, 
C.Indices : Collection, C.Indices.Iterator.Element == C.Index, C.Indices.Index == C.Index, 
C.Indices.SubSequence == C.Indices>
(_ subject: Subject, children: C, displayStyle: Mirror.DisplayStyle? = default, ancestorRepresentation: Mirror.AncestorRepresentation = default)

Conclusion

Associated type requirements are a powerful concept, but they fail to encapsulate some essential properties of their protocols. In practice, this means that we must rely on documentation to understand how to use them.

The requirements that cannot be expressed directly inside protocol definitions need to be pushed to the consumers of these protocols. This creates long and unwieldy functions that look more specific than they really are.

Eventually, we will get a more complete generics system, and most of these problems will disappear. I just hope that people don’t become too frustrated and demand a completely dynamic language by then 🙃