A while ago, Paul Hudson posted a poll on Twitter, asking people what topic they found most difficult when they’d started learning Swift. An overwhelming number of responses were for generics, with a bunch of votes for optionals, closures, and some for the pattern matching techniques¹.

The thing that had me personally scratching my head for hours and hours on end was the whole suite of protocols included in the standard library backing common data structures such as Array, Set, Dictionary, and String.

I ran into the limitations or found a use case for all of the others, forcing me to spend some time studying them up, but the Sequence protocols offered had an escape hatch: The concrete types. The four aforementioned types covered about 99% of my use cases, and for a significant part of the remaining percent, building a wrapper around an Array was simple enough in a pinch. And for the rare case where I ended up with a Slice or a Substring, it was fairly easy to get back to familiar territory by just wrapping it in the appropriate type.

Since those days I’ve spent quite a bit of time understanding those protocols and so this post is an attempt to explain the functionality of some of the most important ones, and the reason for their existence.

Why So Many Protocols

Before going into the what and how, in this case I think it’s important to look at the why first. There are two largely interrelated reasons behind this elaborate structure we’re just about to dive into:

Designing API for minimum requirements

The extremely granular nature of the protocol hierarchy means that you can design your API to accept data that matches your functional and performance requirements, rather than just the one concrete type you had in mind at the time.

Aside from letting you provide an implementation that works with multiple concrete types that also meet those requirements, it also allows your API’s users to use their own custom types, ones that you couldn’t have even thought of — and because of this design, also don’t need to think about.

Because Swift isn’t widely used in Apple’s own frameworks so far there aren’t many first-party examples of this, but a good one is ForEach in SwiftUI. Rather than just an Array, the data argument can be of any type that conforms to RandomAccessCollection:

struct ForEach {
	init<Data, Content>(_ data: Data, content: @escaping (Data.Element) -> Content) 
		where Data: RandomAccessCollection, 
		      Data.Element: Identifiable,
		      Content: View {
	  // implementation
  }
}

At this time of writing RandomAccessCollection has 43 conforming types across all of Apple’s SDKs, all of which can now be used with ForEach because of this design choice.

Shared and specialised implementations

Just as you can use the exact protocol required to design your APIs, so does the standard library, offering a range of algorithms appropriate for the given protocol.

The first benefit of this approach is that the concrete types themselves can be lightweight as an adopter only needs to implement behaviour specific to the data structure they’re designing. Simply conforming to the appropriate protocols gives you access to a range of functions such as allSatisfy, map, filter, etc. with no extra cost. But what makes it especially worthwhile is being able to customise implementations as needed by overloading functions.

Swift doesn’t allow for overloading functions with the same name, arguments, and return value within the same type, however a type can overload a function from another type that it inherits from.

Written out in code, this is what it means:

protocol A {}
extension A {
	func display() { print("A") }
}

protocol B: A {}
extension B {
	func display() { print("B") }
}

struct C: B {}
C().display() // prints "B"

While C.display() can point to either implementation of the display function, because B inherits from A, the compiler will prefer the implementation from B².

Additionally, it is possible for overloaded implementations to have different return types, and the compiler will pick the correct implementation based on the context of the call site.

This is where the real magic happens. The lower levels of the protocol hierarchy offer little information, and so while certain algorithms can be offered, their implementations are necessarily constrained by this knowledge limitation. However, as we go move through the hierarchy and more information is made available, the implementations can be refined and made more performant, while remaining transparent to us Swift users, for the most part, thanks to overloaded implementations and type inference.

Sequences & Iterators

Sequences and Iterators are the foundation on top of which all the other protocols and concrete types are built.

IteratorProtocol is a protocol, as the name suggests³, and despite its rather fundamental nature, implementing one is fairly straightforward, with just one requirement:

protocol IteratorProtocol {
	associatedtype Element
	mutating func next() -> Element?
}

Every time next is called, the iterator can return an instance of the type Element, or nil. Once it returns nil, the iterator is considered to be finished, having exhausted all its elements. The function is marked as mutating because all of the state required to derive the next value is held by the iterator itself, and so any time a value is vended, the iterator can use that as an opportunity to update its internal state in preparation for the next call.

There’s no stipulation that you have to return nil; this is intentional, and allows you to create infinite iterators.

While you probably don’t often create iterators directly, you do use them indirectly. A for ... in loop, for example, works by creating an iterator under the hood. Essentially every eager operation on a sequence (more on this in a bit) relies on the creation of an iterator.

An iterator thus is a one-way ordered walk through a list of elements.

The Sequence protocol has a bunch of requirements, most of which have sensible default implementations, and so a simplified representation of the minimal requirements is as shown below:

protocol Sequence {
	associatedtype Element
	associatedtype Iterator: IteratorProtocol where Iterator.Element == Element
	func makeIterator() -> Iterator
}

In essence, a sequence’s sole job is to vend an iterator. There’s also an additional convenience built in, where an IteratorProtocol can also conform to Sequence with no extra code, by returning itself in the makeIterator function:

extension Sequence where Self.Iterator == Self {
	public func makeIterator() -> Self {
		return self
	}
}

While you don’t have to add much or any code on top of your IteratorProtocol conformance to get a sequence, you get a fair amount of power with it. Functions such as prefix, dropFirst/Last, reversed, contains, map, filter, and many more are made available at the sequence level. However because of the fairly low amount of knowledge available to us at this level, in that you can only ask for the next element one at a time, the implementations must do just that.

dropFirst(_:), for instance, gives you a new iterator, which iterates over the base iterator after eagerly executing and discarding as many values as specified.

dropLast(_:), meanwhile, traverses the whole sequence, adding every encountered value to an Array, thus having a time and space complexity of O(n).

Collection

While in practise it is often used that way, Sequence doesn’t make any promises regarding repeated access. To get the guarantee of repeated access, you need to conform to the Collection protocol.

Collection has a bunch more requirements, but a simplified representation of them is as below:

protocol Collection: Sequence {
	associatedtype Element
	associatedtype Index: Comparable
	associatedtype Indices: Collection
	associatedtype SubSequence: Collection
	
	var startIndex: Index { get }
	var endIndex: Index { get }
	var indices: Indices { get }
	
	func index(after i: Index) -> Index
	
	subscript(position: Index) -> Element { get }
	subscript(bounds: Range<Index>) -> SubSequence { get }
}

The fundamental improvement over Sequence is that a collection lets you access values at any given position, rather than just the one after the one you requested last.

Note here that the Index type isn’t Int, it can be any type that conforms to Comparable. Another important thing here is that you’re never supposed to alter or form indices yourself, you should always ask the collection instance you intend to subscript to do that for you. This ensures that the index you receive is valid, and in some cases it’s required to the point where you can’t even construct an index without querying the collection.

So to enable you to calculate indices, a collection of all of the collection’s valid indices is exposed, as are the starting and the ending indices (which is the index after the last valid one; i.e. it is the first invalid index). The index right after a particular one can also be calculated using the index(after:) function. There is also an index(_:offsetBy:) convenience function which lets you compute the index at some positive integral offset, along with two firstIndex(where:) and firstIndex(of:) functions which let you find the first index matching some condition, or containing some value, respectively.

You can use these indices to subscript values either individually or as a range. Going back to the point about always asking the collection to form an index for you: it is technically considered undefined behaviour to subscript a collection with an index that wasn’t derived from it.

Subscripting a single index returns a single value. Subscripting a range of indices doesn’t return an Array, however, but rather a SubSequence. A collection can use a custom subsequence type, but the standard library provides a good default with the Slice type. The requirements for using a custom SubSequence type are that it must be a collection itself having the same index and element types as the collection, and it must be its own subsequence, which means that if a subsequence is further subscripted, it shouldn’t generate another new type, but rather a new instance of itself.

Slices store the entirety of their backing collections and information regarding the subset of them to be used. Thanks to Swift’s copy-on-write behaviour for all of the standard library collections, this generally doesn’t involve creating an actual copy, but rather the compiler manages multiple references to the same underlying storage transparently, creating actual copies only as needed, when a mutation occurs. This retains value semantics from a Swift developer’s perspective, while optimising memory usage as well. This is where a lot of the power of collections comes into play, allowing you to subscript a range of values with little memory overhead.

Consider the dropLast(_:) algorithm from earlier. If your type conforms to Collection, in addition to the Sequence.dropLast(_:) function which returns an Array of elements, you’ll also have at your disposal an additional Collection.dropLast(_:) function which returns a subsequence of your collection, for example an ArraySlice for Arrays. The implementation is as below:

extension Collection {
	public func dropLast(_ k: Int = 1) -> SubSequence {
		_precondition(
		  k >= 0, "Can't drop a negative number of elements from a collection")
		let amount = Swift.max(0, count - k)
		let end = index(startIndex, 
			offsetBy: amount, limitedBy: endIndex) ?? endIndex
		return self[startIndex..<end]
	}
}

The Collection.dropLast(_:) algorithm computes a new end index by offsetting the startIndex n - k times, where n is the size of the collection, and k is the number of elements to be dropped, and then subscripts the collection over this new range. This still has a time complexity of O(n), as the index(_:offsetBy:) function itself needs to call index(after:) function count - k times, however the underlying storage is shared until there are any mutations, reducing storage complexity to O(1).

One thing to keep in mind when using them is that subsequences share indices with their parent collections. Consider the following snippet:

let list = [0, 1, 2, 3, 4]
let withoutFirst = list.dropFirst()
print(withoutFirst[0])

You might assume that it would print 1, but in fact it crashes, logging an out of bounds access fatal error. This is because the zeroth index isn’t part of the collection’s indices at all, since it has been dropped. The indices of the withoutFirst subsequence are 1 ..< 4. You can still request the first element using the first property, and you can fetch elements at an arbitrary offset by computing the index using the aforementioned index(_:offsetBy:) function.

BidirectionalCollection

BidirectionalCollection is one of those types where the name really tells you the whole story. It’s a collection that can also be traversed in the opposite direction, from back to front.

As such, conforming to BidirectionCollection is fairly straightforward. If your type conforms to Collection, you only need to add one single new function. As you specialise your collection further, you need to update the Indices and SubSequence types to also conform to the same protocols, and so in this case they must both be upgraded to be bidirectional collections as well.

protocol BidirectionalCollection: Collection {
	func index(before i: Index) -> Index
}

In addition to computing the index before a given one, this conformance also lets you pass in negative distances in the aforementioned index(_:offsetBy:) function (whereas Collection would crash if you did so), and exposes a convenient last property, mirroring the first available on all collections. Additionally, there are lastIndex(where:) and lastIndex(of:) functions to match the corresponding first... functions on Collection.

Going back to the dropLast(_:) algorithm from the earlier two examples, the implementation is further refined here. Rather than advancing the startIndex n - k times, it moves the endIndex backwards k times, further reducing time complexity down to O(k)⁴.

extension BidirectionalCollection {
	public func dropLast(_ k: Int) -> SubSequence {
		_precondition(
			k >= 0, "Can't drop a negative number of elements from a collection")
		let end = index(
			endIndex,
			offsetBy: -k,
			limitedBy: startIndex) ?? startIndex
		return self[startIndex..<end]
	}
}

suffix(_:) is also similarly faster, requiring only the traversal of the last k elements directly, rather than traversing the whole collection from start to end.

Another algorithm that gets a refined implementation is reversed(). Sequence has an implementation of reversed() as well, one which eagerly executes the whole sequence to form an Array, and then traverses it using two indices, one from the start and one from the end, swapping items until the indices meet in the middle. This approach has an O(n) hit in terms of both time and storage complexity.

Instead of an Array, calling reversed() on a BidirectionalCollection gets you a ReversedCollection which is generic over the type that you reversed i.e. Array.reversed() gives you a ReversedCollection<Array>.

Rather than eagerly iterating through the collection and manually reversing its contents, this ReversedCollection operates lazily, simply storing the whole collection, and converting indices as need be. Going back to the earlier point about copy-on-write semantics, if you’re reversing a standard library collection or a custom type that implements that behaviour, this also means that you don’t pay any cost for the storage either, reducing execution complexity across the board for the initial reversal to O(1).

It defines a custom Index type which wraps the index of the base collection being reversed, and this index type cannot be instantiated by you from the outside; you can only use the start and end indices combined with the index(after:), index(_:offsetBy:), and related functions to form new indices. Collection algorithms such as prefix(_:), suffix(_:), dropFirst(_:), etc. use the appropriate functions under the hood though, so you rarely need to compute indices directly.

At the same time, there are cases where you might actively want such the Sequence function’s behaviour — if, for instance, you have another function that requires an Array as a parameter, or if you really want the integer-based subscripting that Array provides — and you can always opt into it by manually spelling out your variable’s type as Array<Element>, which will make the compiler pick the eager Sequence implementation.

RandomAccessCollection

RandomAccessCollection is a bit of a weird protocol, in that it’s requirements aren’t really representable within the type system. It is purely a performance guarantee, and one that can’t be verified by the compiler.

Collection only requires that you be able to move forward, BidirectionalCollection requires the ability to move in either direction, and RandomAccessCollection requires that those moves be in constant time.

To conform to the protocol, you need to update your BidirectionalCollection’s Indices and SubSequence associated types to also conform to RandomAccessCollection, but that’s it in terms of new requirements.

protocol RandomAccessCollection: BidirectionalCollection {}

Just doing this will make your code compile, however it isn’t semantically correct at this point. You also need to make sure the index(_:offsetBy:) function we’d talked about earlier operates in constant time. If your Index type conforms to the Strideable protocol, you get this behaviour for free as well.

Unlike the previous protocols, RandomAccessCollection doesn’t really unlock any new functionality. Because its requirements are entirely performance-related, so are the gains. Forming an index at a given offset from another becomes a constant time operation, which means that algorithms such as dropFirst/Last(_:), prefix(_:), suffix(_:), all become constant time operations as well.

The primary benefit of this protocol thus is for API authors to communicate that their algorithms require this higher level of performance. As discussed above, SwiftUI’s ForEach is a great example of where this might be useful. SwiftUI automatically diffs and updates all your views as your state updates, and so especially for long lists, being able to calculate those diffs quickly thanks to the constant time guarantee is critical.

At this point you might be thinking that this sounds great, why would you ever not want to conform to this protocol? An example for this is String.

If you’re familiar with how Unicode strings work, you know that lots of characters are actually composed from multiple individual “scalars”. These scalars can be characters in their own right, and sometimes they need to be conjoined with others using to have valid meaning. Diacritics are a good example of this; “á” and “é” can both be formed by conjoining “a” and “e” with the same diacritic⁵. Similarly, lots of emoji are composed. All the various skin toned emoji like 👍🏽, 👎🏽, and 👋🏽 are formed by conjoining their default yellow forms with a skin tone modifier. Family emoji such as 👨‍👩‍👧‍👦 are also formed by composing the various standalone people emoji such as 👨, 👩, 👧, and 👦.

Because of this behaviour where a character doesn’t have a fixed sized, it isn’t possible to go to the any given position in a String without traversing every single position before it, and thus, String cannot conform to RandomAccessCollection.

Another example from the standard library is the LazyFilterCollection, which is what you obtain if you lazily filter a collection. Because of its lazy operation, it simply stores the whole base collection being filtered, and so must iterate through it every item in the base collection to check if it exists in the filtered version.

MutableCollection

So far in this post we have only discussed reading values from a collection, and seen nothing about writing to one.

Despite what the name might suggest, MutableCollection isn’t required to make collections mutable. Mutability is still enforced by let and var declarations and using value versus reference types, and you can implement custom mutating functions that don’t require this protocol. All the concrete standard library collections you’ve worked with such as String or Dictionary necessarily have to be mutable to be useful, but that doesn’t mean that they conform to MutableCollection; in fact, both of those types don’t.

MutableCollection has a very specific semantic requirement, in that it allows for specific positions of a collection to be mutated while maintaining its length. Additionally, it requires that any such mutations retain the positions they were made at. Like with RandomAccessCollection, there’s no way the compiler can guarantee this, so it is up to implementers to maintain this behaviour.

To conform to the MutableCollection protocol, you need to update your Collection’s subscripts to also be writeable:

protocol MutableCollection: Collection {
	subscript(position: Index) -> Element { get set }
	subscript(bounds: Range<Index>) -> SubSequence { get set }
}

This seems like a very limited set of mutations but it unlocks a whole range of functionality. The most simple of the bunch is the swapAt(_:_) operation, which, lets you swap the elements at two indices.

extension MutableCollection {
	public mutating func swapAt(_ i: Index, _ j: Index) {
		guard i != j else { return }
		let tmp = self[i]
		self[i] = self[j]
		self[j] = tmp
	}
}

You can also sort a mutable collection in place, and reverse or shuffle it as well, and you can partition it, making it so that elements matching a given predicate are all placed after elements that don’t.

Like with RandomAccessCollection, to understand why this protocol exists, you need to look not at conforming types, but types that don’t conform to it.

Going back to the example from that section, String also doesn’t conform to MutableCollection, and for the same reasons that it doesn’t conform to RandomAccessCollection. Because a String is made up of characters of variable size, replacing a character with another might change the length of the whole collection. String implements a custom Index type, which holds private information about the corresponding position in the underlying storage buffer. As such, replacing a character with one of a different length would invalidate all indices after it, making them point to invalid or incorrect data.

It’s worth noting though that MutableCollection isn’t just a requirement on fixed sized elements.

While subscripting a Dictionary using the Key produces a value of type Element?, these aren’t actually the Dictionary’s Index and Element types. These subscripts are overloads on the regular collection ones. Dictionary’s Index type is a custom Index like with String, and its Element type is a tuple of the type (Key, Value)⁶. As such, replacing a given element would make it possible to potentially create multiple entries with the same key, and any attempt to remove that duplication would require removing all but one value, thereby altering the collection’s length, and so Dictionary also doesn’t conform to RandomAccessCollection.

RangeReplaceableCollection

We’re back to familiar territory with the protocol doing exactly what it says on the tin: RangeReplaceableCollection lets you replace all elements within a given range with elements from another collection.

Conforming to the protocol is fairly simple. You need to define an initialiser to create an empty collection, and one other function:

protocol RangeReplaceableCollection: Collection {
	
	init()
	
	mutating func replaceSubrange<C>(
		_ subrange: Range<Index>,
		with newElements: C
	) where C: Collection, C.Element == Element
}

While it may appear similar to the settable range subscript from MutableCollection, not only can ‌replaceSubrange(_:with:) accept any arbitrary collection, it is also allowed to change the length of the collection. It is perfectly legal to replace a range with a collection that is shorter or longer, whereas that would be incorrect behaviour for MutableCollection, and would even crash if you attempted to do so using the default implementation.

This one simple function opens the door to a lot of functionality. You can for instance remove a range of values, by passing in an empty collection as the replacement. You can also insert values at any arbitrary index, which is accomplished by making it so that the range to be replaced is index ..< index. And you can append values to a collection by making it so that the index at which values are inserted is the endIndex.

One thing to note is that while MutableCollection and RangeReplaceableCollection may appear interrelated, they both extend Collection, and can be implemented individually.

We saw that String for instance cannot implement MutableCollection, but it does however conform to RangeReplaceableCollection. Inserting, removing, or performing any other mutations on a String could change the length and invalidate indices, however this is legal behaviour for RangeReplaceableCollection, and so String can safely conform to the protocol.

Dictionary, however, does not conform to RangeReplaceableCollection, since it is a requirement that any replaced items should remain at the same indices they were placed in, and this wouldn’t be possible to achieve for dictionaries while retaining their core functionality of only having a single value for any given key: If a duplicate key was inserted, it would need to remove either the new or old one, which would necessarily break other indices.

Conclusion

That about covers all of the public types making the standard library’s Collection protocol hierarchy⁷.

While they can seem a bit daunting at first and take some time to imbibe, I hope this article helped in explaining why the various protocols exist, and the kinds of refinements they enable.

At the same time, it’s worth considering some of the drawbacks of this approach too.

You could argue that the granularity of the protocols is too fine and creating too complex a structure that isn’t well understood and thus underused in the community at large. It’s really common for instance to see sequence algorithms being written as extensions on Array or some other concrete type, when you can often generalise them out to one or some combination of these protocols, allowing them to also be used by any other conformances without writing a single extra line of code, and also allowing you to use them on subsequences as well.

At the same time you could also argue that the granularity isn’t fine enough. While you rarely interact with them directly, it does feel a bit off for unordered types such as Dictionary and Set to have a firstIndex and a lastIndex. Both of those types also have mutation implemented using custom-designed, bespoke functions not belonging to any of the protocols we’ve seen.

This one is more of an issue with protocols in general rather than the hierarchy as it is, but consider also the fact that types can only conform to a protocol in one way. The standard library doesn’t currently have one, but it isn’t too outrageous to imagine it having a collection to represent binary trees. Generally these can be traversed in a pre-order, in-order, and post-order fashion, with none being more valid than the other. How would such a behaviour fit with the Collection or Sequence protocols, which require one single implementation? Like with Dictionary and Set, you would probably need some custom logic and code here, as it doesn’t really neatly fit in with the model at hand.

For further reading, I’d highly recommend diving into the source code. While Swift itself is written in C++, the standard library is (mostly) written in idiomatic Swift, and the directory containing sources for public API can be found here. A great place to start is with the source for the Sequence and Collection types. Additionally, I’d recommend watching Dave Abrahams’s excellent Embracing Algorithms session from WWDC 2018, which was what inspired me to dive into this subject in the first place.