Chapters
Chapters

Chapters

Hide chapters

Expert Swift

Second Edition · iOS 18.5 · Swift 6.1 · Xcode 16.3

Before You Begin

Section 0: 5 chapters
Show chapters Hide chapters

Section I: Core Concepts

Section 1: 4 chapters
Show chapters Hide chapters

Section II: Standard Library

Section 2: 5 chapters
Show chapters Hide chapters

Section III: Techniques

Section 3: 6 chapters
Show chapters Hide chapters

6. Sequences, Collections & Algorithms
Written by Ray Fix

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Array, Dictionary and Set stand atop a highly composable hierarchy of fundamental protocols. These protocols, which include Sequence and Collection among others, capture the essence of these types. The Swift standard library design serves as a case study in Swift generics and protocol-oriented programming that you can learn from and leverage.

The concepts these protocols express are general enough that they appear where you might not expect. For example, the ranges and strides you looked at in the last chapter are sequences and collections, just like arrays are. Although a Range type doesn’t need to allocate memory for elements like an Array does, it shares many of the same capabilities and characteristics. In this chapter, you’ll learn about Sequence, Collection and other related protocols and see how to use them to write generic algorithms that operate across type families.

A Family of Protocols

By defining primitive notions of a sequence of values, a collection of values and other collection characteristics using protocols, you can write high-performance, generic algorithms. This lets the compiler deal with the specifics of the memory layout that concrete types use to adopt them.

In other languages, the number of implementations for data structures and their algorithms can face what is known as “the M by N problem”. Without a language feature like generics and protocols, the number of implementations for M data structures and N algorithms is the simple product of the two.

Non-generic, non protocol-orientated results in N+M implementations first sorted dropped chunked(by:) Set Array Dictionary Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code Custom code N M Custom code QuadTree Custom code Custom code Custom code
M by N implementations

Imagine having to maintain all this code. The above graphic shows just four collection types and four algorithms for a total of sixteen implementations. The truth is that Swift has tons of concrete sequence and collection types such as CollectionOfOne, JoinedSequence, DropWhileSequence and many more.

Thanks to protocols and generics, the number of implementations is only M + N. And that means you never repeat yourself.

sorted first Generic code Generic code dropped Generic code chunked(by:) Generic code Set Array Dictionary QuadTree Generic, protocol-orientated results in only N+M implementations
M plus N implementations

In this world, any type that conforms to the required protocols gets all the algorithm implementations generated on-demand for free. The compiler uses the protocol witness table of protocol declaration to implement function definitions. It can also create specializations for particular concrete types as an optimization. Although there’s programmer complexity cost in knowing about these fundamental protocol types, this knowledge pays for itself handily, as you’ll see.

Sequences and Collections

To take full advantage of the system, you need to become familiar with the protocols involved with sequences and collections. Here’s what the hierarchy looks like:

Nah mitfepi ivikeqlp Waguehce Awmuqj pq idrig Yajciwcoip Oropumuib xvije OgoxesejTzeyisup Jnotzu icumufjf QewerreXeknewjiac Nillufv, hapwhurg lzowobgik QegevepceuzicZatcecxoog Nzuxyi cemhafmen CasvaPaxyateowhiVozxiwduah Ewith Fkdezg ubp Sikzywolk YttevdVlopigif Mizmuh ujqayk lladozpen MunxusEzquqcRepnedgieb rixyj
Haheevse ffxom mluzihus vuivufhyd

Iterators and Sequences

Create a custom type that counts down to zero when you loop over it with a for statement. Open the Countdown starter playground for this chapter and add the following:

StrideThrough and StrideTo

The previous section might have seemed like a lot of code for the job. Yes, there are simpler ways of accomplishing the countdown task. For example, you could have used a simple StrideThrough type, which you create by calling the stride function you saw in the last chapter. Add this to the playground:

UnfoldFirstSequence and UnfoldSequence

The Swift standard library functions sequence(first:next:) and sequence(state:next:) let you define custom sequences without needing to define a new sequence type (and iterator). Try it out by adding this to the end of your playground:

Type Erasure with AnySequence

To keep your codebase maintainable and hide unnecessary details, you’ll often want to hide type details of a sequence from users (and yourself). It would be ideal to return an opaque return type, such as some Sequence, from your function. However, opaque return types don’t currently let you constrain associated types, such as the Element, so unfortunately this doesn’t work. But there’s still a way. Hide these unimportant type details and keep your interface clean with the type erasure AnySequence.

Implementing Sequence with AnySequence and AnyIterator

In the example above, you defined a sequence and then type-erased it, but AnySequence also gives you an initializer to do both in one go. Add this:

Exercises

Answers to exercises, as always, are in the download materials, inside the “exercises” folder. For best results, don’t peek — try it yourself first.

Collections

Collections build on top of sequences and feature an additional guarantee that you can revisit elements. To visit an element, all you need is an index that can access an element in constant time O(1). This complexity guarantee is important because many other algorithms rely on this base level of performance to guarantee their own performance.

A FizzBuzz Collection

Like sequences, an excellent way to learn about collections is to create a simple one yourself. Looking at all the protocol requirements of Collection makes creating one seem a daunting task. However, because most of the API has good default protocol implementations, it’s pretty straightforward. In some ways, it’s easier to create a collection than to create a sequence from scratch. What’s more, because Collection is-a Sequence, you get all the sequence functionality for free. You’ll use FizzBuzz to see this in action.

BidirectionalCollection

Because you only implemented Collection conformance, the standard library algorithms only know how to walk forward through your collection. To see this, add some debug printing to your previous implementation of index(after:):

RandomAccessCollection

You can eliminate all the extra traversing calls by making FizzBuzz a random access collection. Add this to your playground:

MutableCollection

Because FizzBuzz is not mutable by definition, change gears with another example. Mutable collections allow you to change elements with a subscript setter. MutableCollection implies that items can be swapped and reordered. This operation doesn’t imply a change in the size of the collection.

The Rules of Conway’s Life

As a so-called “zero-player” game, the rules of Conway’s Life are simple:

Duztuf'g Hopa ipl jlmiugtkul
Sukvay'z Qibu abf nbmaidbjum

Make Bitmap a Collection

Open the file Bitmap+Collection.swift and add the following:

Creating the Simulation

Implement the simulation using the Bitmap collection. Open LifeSimulation.swift. The model object has three observed properties — isRunning, generation and cells — that redraw the user interface every time they change. Add this statement to the end of LifeSimulation’s initializer:

Dashal'l Mawe omc yrjiovpgel
Davget'w Wumo ajk mysiewqpey

RangeReplaceableCollection and Others

Range replaceable collections allow you to add and remove values from a collection. Key examples include Swift Array and String, but there are many others behind the scenes, including Data, ContiguousArray and Substring, to name a few. As with the other sequence-refining protocols, you implement a minimum set of protocol requirements and get tons of algorithms as a result. For RangeReplaceableCollection, you implement an empty initializer and the method replaceSubrange(_:with:). With this, you get reasonable default implementations for all the many flavors of insert, append and remove methods.

Subsequences and Slices

It’s common to want to deal with a subset of a sequence or collection. The Collection protocol defines a default associated type this way:

Memory Management

Slices don’t allocate new memory but reference the memory of the original collection. This reference means they’re cheap O(1) to create because they don’t copy elements and can be used to construct efficient, generic algorithms.

The World of Lazy Evaluation

Collections use slice types to control the timing of allocations and copies into new collections. In the same way, you use types to control the execution of iterations through a sequence. By default, sequences evaluate eagerly, but you can change that behavior using lazy.

Generic Algorithms

The Swift standard library contains a bevy of algorithms that automatically apply to sequences and collections that meet the appropriate requirements. For example, first, forEach, map, reduce, sort and zip are standard library algorithms.

Key Points

The Swift standard library’s sequence and collection protocols fully leverage the generic system to make a consistent and predictable (and incredible) programming model. Here are some key points to take away:

Where to Go From Here?

Swift Algorithms (https://github.com/apple/swift-algorithms) project focused on sequence and collection algorithms. This GitHub repository contains an implementation of chunks(ofCount:). Although your implementation in this chapter returned an array of subsequences that requires a heap allocation, the Swift Algorithm version returns a custom collection requiring no heap allocations. This optimization makes it significantly faster and enables lazy chunking. Although the implementation there is much lengthier and more involved than the ones presented here, you now should have all the knowledge you need to read and understand the clever things the authors have done.

5. Numerics and Ranges
7. Strings
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now