Conditional Conformance in the Standard Library
The Swift 4.1 compiler brings the next phase of improvements from the roadmap for generics: conditional conformances.
This post will look at how this much-anticipated feature has been adopted in Swift’s standard library, and how it affects you and your code.
Equatable Containers
The most noticeable benefit of conditional conformance is the ability for types
that store other types, like Array
or Optional
, to conform to the
Equatable
protocol. This is the protocol that guarantees you can use ==
between two instances of a type. Let’s look at why conformance to this protocol
is so useful.
You have always been able to use ==
with two arrays of any equatable element:
[1,2,3] == [1,2,3] // true
[1,2,3] == [4,5] // false
Or two optionals that wrap an equatable type:
// The failable initializer from a String returns an Int?
Int("1") == Int("1") // true
Int("1") == Int("2") // false
Int("1") == Int("swift") // false, Int("swift") is nil
This was possible via overloads of the ==
operator, like this one for Array
:
extension Array where Element: Equatable {
public static func ==(lhs: [Element], rhs: [Element]) -> Bool {
return lhs.elementsEqual(rhs)
}
}
But just because they implemented ==
did not mean Array
or Optional
conformed to
Equatable
. Since these types can store non-equatable types, we needed to
be able to express that they are equatable only when storing an equatable
type.
This meant these ==
operators had a big limitation: they couldn’t be used two levels deep.
If you tried something like this in Swift 4.0:
// convert a [String] to [Int?]
let a = ["1","2","x"].map(Int.init)
a == [1,2,nil] // expecting 'true'
You’d get a compiler error:
Binary operator ‘==’ cannot be applied to two ‘[Int?]’ operands.
This is because the implementation of ==
for Array
, as shown above, required the array’s
elements were equatable, and Optional
wasn’t equatable.
With conditional conformance, we can now fix this. It allows us to write
that these types conform to Equatable
—using the already-defined ==
operator—if the types they are based on are equatable:
extension Array: Equatable where Element: Equatable {
// implementation of == for Array
}
extension Optional: Equatable where Wrapped: Equatable {
// implementation of == for Optional
}
Equatable
conformance brings other benefits beyond ==
. Having equatable
elements gives collections other helper functions for tasks like searching:
a.contains(nil) // true
[[1,2],[3,4],[]].index(of: []) // 2
Using conditional conformance, Swift 4.1’s Optional
, Array
, and
Dictionary
now conform to Equatable
and Hashable
whenever their values or
elements conform to those protocols.
This approach also works for Codable
. If you try and encode an array
of non-codable types, you’ll now get a compile-time error instead of the runtime
trap you used to get.
Collection Protocols
Conditional conformance also has benefits for building up capabilities for your
types incrementally, avoiding code duplication. To explore some of the changes
made possible in the Swift standard library via use of conditional conformance,
we’ll use an example of adding a new feature to Collection
: lazy splitting.
We’ll create a new type that serves up slices split from a collection, then see
how conditional conformance can be used to add bidirectional capabilities when
the base collection is bidirectional.
Eager vs Lazy Splitting
The Sequence
protocol in Swift has a split
method, which splits a sequence up into an
Array
of subsequences:
let numbers = "15,x,25,2"
let splits = numbers.split(separator: ",")
// splits == ["15","x","25","2"]
var sum = 0
for i in splits {
sum += Int(i) ?? 0
}
// sum == 42
We characterize this split
method as being “eager,” because it eagerly splits the
sequence up into subsequences and puts them into an array as soon as you call it.
But suppose you wanted just the first few subsequences? Say you had a giant text file, and you wanted to grab just the initial lines of it to display as a preview. You wouldn’t want to process the entire file just to use a handful of lines at the beginning.
This kind of problem also applies to operations like map
and filter
, which
are similarly eager by default in Swift. To avoid it, the standard library has
“lazy” sequences and collections. You access them via the lazy
property. These lazy
sequences and collections have implementations of operations like map
that don’t run
immediately. Instead, they perform the mapping or filtering on the fly when the elements
are accessed. For example:
// a huge collection
let giant = 0..<Int.max
// lazily map it: no work is done yet
let mapped = giant.lazy.map { $0 * 2 }
// sum the first few elements
let sum = mapped.prefix(10).reduce(0, +)
// sum == 90
When the mapped
collection is created, no mapping happens. In fact, you might notice
that if you performed the mapping operation on every element of giant
it would trap: it would overflow halfway through, when doubling the values
no longer fits in an Int
. But with a lazy map
, the mapping only happens when you access
the elements. So in this example, only the first ten values are computed, when the reduce
operation sums them up.
A Lazy Splitting Wrapper
The standard library doesn’t have a lazy split operation. Below is a sketch of how one could work. If you’re interested in making a contribution to Swift, this would make for a great first issue and evolution proposal.
First, we create a simple generic wrapper struct that can hold any base collection, and a closure to identify elements on which to split:
struct LazySplitCollection<Base: Collection> {
let base: Base
let isSeparator: (Base.Element) -> Bool
}
(we’ll ignore things like access control to keep the code simple for this post)
Next we conform to the Collection
protocol. To be a collection you
only need to provide four things: a startIndex
and endIndex
, a subscript
that gives the element for a given index, and an index(after:)
method to
advance the index by one.
The elements of this collection are the subsequences of the base collection
(the substring "one"
from "one,two,three"
). Subsequences of a collection
use the same index type as their parent collection, so we can reuse the
index of the base collection as our index too. The index will be the
start of the next subsequence in the base, or the end.
extension LazySplitCollection: Collection {
typealias Element = Base.SubSequence
typealias Index = Base.Index
var startIndex: Index { return base.startIndex }
var endIndex: Index { return base.endIndex }
subscript(i: Index) -> Element {
let separator = base[i...].index(where: isSeparator)
return base[i..<(separator ?? endIndex)]
}
func index(after i: Index) -> Index {
let separator = base[i...].index(where: isSeparator)
return separator.map(base.index(after:)) ?? endIndex
}
}
The work to find the next separator, and return the sequence between, is done
in the subscript
and index(after:)
methods. In both, we search the base
collection from the given index for the next separator. If there isn’t one,
index(where:)
returns nil
for not found, so we use ?? endIndex
to
substitute the end index in that case. The only fiddly part is skipping over
the separator in the index(after:)
implementation, which we do with an
optional map.
Extending lazy
Now that we have this wrapper, we want to extend all the lazy collection types
to use it in a lazy split method. All lazy collections conform to
LazyCollectionProtocol
, so that’s what we extend with our method:
extension LazyCollectionProtocol {
func split(
whereSeparator matches: @escaping (Element) -> Bool
) -> LazySplitCollection<Elements> {
return LazySplitCollection(base: elements, isSeparator: matches)
}
}
It’s also convention with methods like this to provide a version that takes a value instead of a closure when the elements are equatable:
extension LazyCollectionProtocol where Element: Equatable {
func split(separator: Element) -> LazySplitCollection<Elements> {
return LazySplitCollection(base: elements) { $0 == separator }
}
}
With this, we’ve added our lazy split method to the lazy subsystem:
let one = "one,two,three".lazy.split(separator: ",").first
// one == "one"
We also want to mark our lazy wrapper with the LazyCollectionProtocol
, so
that any further operations on it are also lazy, as users would expect:
extension LazySplitCollection: LazyCollectionProtocol { }
Conditionally Bidirectional
So now we can efficiently split the first few elements from a delimited
collection. What about reading the last few? BidirectionalCollection
adds an
index(before:)
method to move an index backwards from the end. This allows
bidirectional collections to support things like the last
property.
If the collection we’re splitting is bidirectional, we ought to be able to make
our splitting wrapper bidirectional too. In Swift 4.0, the way to do this was
pretty clunky. You had to add a whole new type,
LazySplitBidirectionalCollection
, which required Base:
BidirectionalCollection
and implemented BidirectionalCollection
. Then, you
overloaded the split
method to return it where Base:
BidirectionalCollection
.
Now, with conditional conformance, we have a much simpler solution: just make
LazySplitCollection
conform to BidirectionalCollection
when its base does.
extension LazySplitCollection: BidirectionalCollection
where Base: BidirectionalCollection {
func index(before i: Index) -> Index {
let reversed = base[..<base.index(before: i)].reversed()
let separator = reversed.index(where: isSeparator)
return separator?.base ?? startIndex
}
}
Here, we’ve used reversed()
, another lazy wrapper that reverses the order of
any bidirectional collection. This allows us to search backwards for the next
separator, then use the reversed collection index’s .base
property to get back to
the index in the underlying collection.
With this one new method, we’ve given our lazy collection access to
functionality of any bidirectional collection, like the .last
property, or reversed()
method:
let backwards = "one,two,three"
.lazy.split(separator: ",")
.reversed().joined(separator: ",")
// backwards == "three,two,one"
This kind of incremental conditional conformance really shines when you have to
combine multiple different independent conformances. Suppose we wanted to make
our lazy splitter conform to MutableCollection
whenever the base was mutable.
These two conformances are independent—mutable collections don’t have to be
bidirectional and vice versa—so we would need to create a specialized type
for every possible combination of the two.
But with conditional conformance, you would just add a second conditional conformance.
This feature is exactly what the standard library’s Slice
type needed. This
type provides default slicing capabilities to any collection type. You can see
it in use if you try slicing our lazy splitter:
// dropFirst() creates a slice without the first element of a collection
let slice = "a,b,c".lazy.split(separator: ",").dropFirst()
print(type(of: slice))
// prints: Slice<LazySplitCollection<String>>
In Swift 4, there needed to be a dozen different implementations, up to the
worst-case MutableRangeReplaceableRandomAccessSlice
. Now, with conditional
conformance, it can be just one Slice
type with 4 different conditional
conformances. This change alone resulted in a 5% reduction in the binary size
of the standard library.
Further experiments
If you’re familiar with the eager split
you’ll notice that our implementation
is missing some features, like coalescing empty subsequences. There are also
performance optimizations you could make, like giving the wrapper a custom
index of its own that caches the location of the next separator.
If you want to try writing your own lazy wrapper from scratch from you could
also consider a “chunking” wrapper that served up slices of length n at a time.
That case is interesting because you could make it a BidirectionalCollection
if the base were random access, but not if the base is bidirectional, because
you need to be able to calculate the length of the last element in constant
time.
Conditional conformance is available today on the Swift 4.1 development toolchain, so you can download the latest snapshot and try it out!