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.
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.
StringsExtra
project from Lesson 4, and name the duplicate StringsExtraLazy
.StringsExtra.swift
.String
to StringProtocol
(we can do this because the method we use inside, range(of:)
, is also available on StringProtocol
). At the top of the file, change the line extension String {
to extension StringProtocol {
.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 use String.Index
as index type, this associated type has not been set on StringProtocol
. We need to constrain our extension:
extension StringProtocol where Index == String.Index {
countLinguisticTokens
. We won't deal with that now, but just move that method to the extension on String below.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
.
allRanges
method 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, its elements
property is a string or a substring, thanks to the constraints we added to the extension. So, for every error that now appears, insert elements.
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
return
statement at the end. We no longer need the ranges
variable; remove the two lines it appears in.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 while
loop 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, as searchRange
is the only variable left.
sequence(state:)
function seems like a good fit. Insert this on the line above the while
loop:let result =
seq
, and select sequence(state:
(and so on) from the auto completion pop-up menu. Enter searchRange
in 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 }
searchRange
as well, and the return type, the element type of the sequence we are now creating, is Range<String.Index>
:let result = sequence(state: searchRange) { (searchRange) -> Range<String.Index>? in }
foundRange
is nil
. Change the while let
line and the next two ones to this:guard let foundRange = self.elements.range( of: aString, options: options, range: searchRange, locale: locale) else { return nil }
return foundRange
var searchRange
to let searchRange
.result
to 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:Conforms To IteratorProtocol, Sequence
UnfoldSequence
performs its operations lazily and internally, but since it does not conform to LazySequenceProtocol
, other operations on it like map
and filter
are not lazy. Since we are adding a method to LazySequenceProtocol
, we need to make sure that any sequence we return also conforms to it. To do this, add .lazy
right after the closing brace of the closure, on the line below return foundRange
.
result
again. 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.
let result =
with return
.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.
And that's it. Congratulations!