All the sequences and methods we have looked at so far this lesson have been eager, which means they perform their operations immediately, and filter, map, and flatMap return their results in arrays. But sometimes, we may want to delay operations until they are needed.
Say you have a very large array, and you want to first use map and then perform other operations. If done eagerly, map will create a new array with the same number of elements as the original one to store its results. But if we do it lazily, map will return a LazyMapSequence, which will perform each map operation directly when asked for, without using any intermediate storage.
Infinite sequences must be handled lazily, as they obviously cannot be stored.
Have a look at the preceding diagram that talks of lazy sequences. A lazy sequence is one that conforms to LazySequenceProtocol. The original sequence itself may or may not work lazily internally, but some further operations on the sequence are lazy, for example, filter, map, flatMap, drop(while:), and prefix(while:).
To make a sequence lazy, just use the lazy property:
let array = [1,2,3,4] let lazyArray = array.lazy
The actual type we get back depends on the type of the original sequence. For array, it is LazyRandomAccessCollection<Array<Element>>.
We can chain many operations together:
let complexType = lazyArray
.flatMap { -2..<$0 }
.map { $0*$0 }
.filter { $0<4 }Note that none of the operations have been performed yet. This won't happen until we turn the sequence into an array (Array(complexType)), use it in a for…in loop, or perform an operation that is not lazy:
let eager = complexType.dropFirst(4)
One thing you will notice about lazy sequences is that the types may become very long and complex. For example, the type signature for complexType mentioned previously is as follows:
LazyFilterCollection<LazyMapCollection<FlattenBidirectionalCollection<LazyMapBidirectionalCollection<[Int], CountableRange<Int>>>, Int>>
If a type signature threatens to get out of hand, we can shorten it with this:
let shorterTypeSignature = AnySequence(complexType).lazy // LazySequence<AnySequence<Int>>
Beware that this may prevent some optimizations, as the compiler no longer knows what types are at work.
Note
If they save memory, why not always use lazy sequences?
Because they are not necessarily faster. Lazy operations do not store their results, so every time they are called, they have to do the same operation again. You have to be careful which parts of your chain of operations are lazy to avoid redoing the same operations over and over.
The Sequence protocol looks like this (from the Swift source code, slightly simplified; see https://github.com/apple/swift/blob/master/stdlib/public/core/Sequence.swift):
public protocol Sequence {
/// A type representing the sequence's elements.
associatedtype Element
/// A type that provides the sequence's iteration interface and
/// encapsulates its iteration state.
associatedtype Iterator : IteratorProtocol where Iterator.Element == Element
/// Returns an iterator over the elements of this sequence.
func makeIterator() -> Iterator
}This, of course, begs the question: so what is IteratorProtocol?
public protocol IteratorProtocol {
/// The type of element traversed by the iterator.
associatedtype Element
/// The next element in the underlying sequence,
/// if a next element exists; otherwise, `nil`.
mutating func next() -> Element?
}Every time a sequence is used in a for…in loop, or when other methods go through its elements, it first returns an iterator from makeIterator, which in turn provides one element at a time from next, until it is empty and returns nil.
How do we create operations that work lazily? For more complex operations, including those that use recursion, it is often best to create a new type which implements the Sequence and IteratorProtocol protocols. But for simpler tasks, there are two very convenient functions the Standard Library provides.
Here is the function:
func sequence<T>(first: T, next: @escaping (T) -> T?) -> UnfoldSequence<T, (T?, Bool)>
This function creates the sequence first, next(first), next(previous element), next(previous element), and so on, until next returns nil (or, if it's infinite, the sequence will continue forever).
It is very useful for following references:
for view in sequence(first: someView, next: { $0.superview }) {
// someView, someView.superview, someView.superview.superview, ...
}It is also useful for some mathematical sequences:
let powersOf2 = sequence(first: 1) {
let result = $0.multipliedReportingOverflow(by: 2)
return result.overflow ? nil : result.partialValue
}Here is the function:
func sequence<T, State>(state: State, next: @escaping (inout State) -> T?) -> UnfoldSequence<T, State>
This creates a sequence by repeatedly passing mutable State to the next function. It is useful when there are changing values that are different than the output.
Here is the obligatory Fibonacci sequence example (where each element is the sum of the previous two elements):
let fibonacci = sequence(state: (0,1)) { numbers -> Int? in
numbers = (numbers.1, numbers.0 + numbers.1)
return numbers.0
}.prefix(91)This outputs 1, 1, 2, 3, 5, 8, and so on. We limit the sequence to the first 91 elements, because the 92nd is too large to fit in an Int type, and the program will crash.
For a slightly more complex example, this method returns the elements of the underlying sequence in groups of two, in tuples:
extension LazySequenceProtocol {
/// Group the elements of this sequence in tuples of 2.
/// If there is an odd number of elements, the last element is discarded.
func group2() -> LazySequence<UnfoldSequence<(Element, Element), Iterator>> {
return sequence(state: self.makeIterator()) { iterator in
let result = iterator.next().flatMap { a in
iterator.next().map { b in (a,b) }
}
return result
}.lazy
}
}Here, we use the iterator of the underlying sequence as the mutable state, and only return a value if both calls to iterator.next() are not nil. We use flatMap first, because the next line can also be nil.
The code from let result to return result does the same as this:
guard let a = iterator.next(),
let b = iterator.next()
else { return nil }
return (a,b)In this section, we have covered what lazy operations are and how they are useful. We'll end this section with an activity that allows us to implement the lazy version of a method.
We want to make the method use less memory, or be more efficient if we only need some of the ranges.
To use an Xcode playground to make a lazy version of the allRanges method from Lesson 5, Strings.
- Duplicate the
StringsExtraproject from Lesson 4, and name the duplicateStringsExtraLazy. - Open a new project, and go to
StringsExtra.swift. - First, it would be nice if both the current and the lazy version of the method could be used on both strings and substrings. To achieve this, we must move the current version from
StringtoStringProtocol(we can do this because the method we use inside,range(of:), is also available onStringProtocol). At the top of the file, change the lineextension String {toextension StringProtocol {. - We get an error message a couple of lines below, saying this:
Cannot convert value of type 'Range<Self.Index>' to expected argument type 'Range<String.Index>'
This is because even though only String and Substring conform to
StringProtocol, and they both useString.Indexas index type, this associated type has not been set onStringProtocol. We need to constrain our extension:extension StringProtocol where Index == String.Index { - There is still one error in
countLinguisticTokens. We won't deal with that now, but just move that method to the extension on String below. - Run unit tests, and verify that they pass.
- At the bottom of the file, add the following:
extension LazySequenceProtocol where Elements: StringProtocol, Elements.Index == String.Index { }Here, we are adding the same constraints as in the preceding extension, except we add them to
LazySequenceProtocol.Elements. - Paste a copy of the original
allRangesmethod into the new extension. Some errors appear:Use of unresolved identifier 'startIndex' Use of unresolved identifier 'endIndex'
This is because we are no longer in String. We are in
LazySequenceProtocol, and it does not have those properties. However, itselementsproperty is a string or a substring, thanks to the constraints we added to the extension. So, for every error that now appears, insertelements.in front of the identifier mentioned in the error message, for example:var searchRange = searchRange ?? startIndex..<endIndex
The preceding line of code becomes this:
var searchRange = searchRange ?? elements.startIndex..<elements.endIndex
- Verify that everything builds okay (⌘B).
- Now, let's look at the method and how to make it lazy. We will be returning a sequence of some kind, but we're not quite sure which yet. For now, we can just remove the return type from the function definition, and the
returnstatement at the end. We no longer need therangesvariable; remove the two lines it appears in. - We should now be left with this:
extension LazySequenceProtocol where Elements: StringProtocol, Elements.Index == String.Index { public func allRanges(of aString: String, options: String.CompareOptions = [], range searchRange: Range<String.Index>? = nil, locale: Locale? = nil) { var searchRange = searchRange ?? elements.startIndex ..< elements.endIndex while let foundRange = self.elements.range( of: aString, options: options, range: searchRange, locale: locale) { searchRange = options.contains(.backwards) ? searchRange.lowerBound ..< self.elements.index(before: foundRange.upperBound) : self.elements.index(after: foundRange.lowerBound) ..< searchRange.upperBound } } }The code inside the
whileloop is what will be run for each turn of the sequence we are creating. We need to identify what state is changing each time. In this case, it is easy to see, assearchRangeis the only variable left. - So, we have some state external to the loop; the
sequence(state:)function seems like a good fit. Insert this on the line above thewhileloop:let result =
- Begin to type
seq, and selectsequence(state:(and so on) from the auto completion pop-up menu. EntersearchRangein the first blue field, press Tab, and then press enter on the next blue field. You are left with this:let result = sequence(state: searchRange) { () -> T? in } - We can just call the input parameter to the closure
searchRangeas well, and the return type, the element type of the sequence we are now creating, isRange<String.Index>:let result = sequence(state: searchRange) { (searchRange) -> Range<String.Index>? in } - Move the closing brace down so the entire loop is inside the closure. Ignore the Missing return in a closure… error message.
- We need to know when to stop, and that is when
foundRangeisnil. Change thewhile letline and the next two ones to this:guard let foundRange = self.elements.range( of: aString, options: options, range: searchRange, locale: locale) else { return nil } - Now we can listen to the error message; insert this at the end of the closure:
return foundRange
- There should be a warning on the first line of the body of the method. Click on it, and then click on fix to change
var searchRangetolet searchRange. - Now all that is left is to actually return something from the method. Click on
resultto put the text marker inside it, and look in the Quick Help Inspector in the top-right corner of the window (if it is not already open, press ⌘⌥2). You should see the type of the sequence there. Click on UnfoldSequence to view the documentation:
- Go to the bottom of the documentation page, where it says this:
Conforms To IteratorProtocol, Sequence
UnfoldSequenceperforms its operations lazily and internally, but since it does not conform toLazySequenceProtocol, other operations on it likemapandfilterare not lazy. Since we are adding a method toLazySequenceProtocol, we need to make sure that any sequence we return also conforms to it. To do this, add.lazyright after the closing brace of the closure, on the line belowreturn foundRange. - Place the text marker inside
resultagain. In the top right corner, the type has changed to this:LazySequence<UnfoldSequence<Range<String.Index>, Range<String.Index>>>
Copy and paste it in as the return type of the method.
- Replace
let result =withreturn. - Verify that it builds.
- Go to the unit test file
StringsExtraTests.swift, and insert the following below the first unit test:func testAllRangesLazy() { let lazyString = string.lazy XCTAssertEqual(Array(lazyString.allRanges(of: "Line", options: .caseInsensitive)).count, 2) XCTAssertEqual(Array(lazyString.allRanges(of: "Line")).count, 1) XCTAssertEqual(Array(lazyString.allRanges(of: "hsf")).count, 0) XCTAssertEqual(Array("LineLineLine".lazy.allRanges(of: "Line")).count, 3) XCTAssertEqual(Array("lalalalalala".lazy.allRanges(of: "lala")).count, 5) XCTAssertEqual(Array("llllllll".lazy.allRanges(of: "ll")).count, 7) XCTAssertEqual(Array(lazyString.allRanges( of: "li", options: .caseInsensitive, locale: .current).map{string[$0]}).count, 2) XCTAssertEqual(Array(lazyString.allRanges( of: "li", options: [.caseInsensitive, .backwards], locale: .current)).count, 2) }Here, we extract all elements from the lazy sequences by wrapping them in arrays.
- Run all unit tests (⌘U) and verify that they all pass.
And that's it. Congratulations!