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.

Lazy Sequences

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:

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:

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:

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:

If a type signature threatens to get out of hand, we can shorten it with this:

Beware that this may prevent some optimizations, as the compiler no longer knows what types are at work.

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:

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):

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:

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:

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.

  1. Duplicate the StringsExtra project from Lesson 4, and name the duplicate StringsExtraLazy.
  2. Open a new project, and go to StringsExtra.swift.
  3. 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 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 {.
  4. 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 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 {
  5. 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.
  6. Run unit tests, and verify that they pass.
  7. 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.

  8. Paste a copy of the original 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
  9. Verify that everything builds okay (B).
  10. 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 return statement at the end. We no longer need the ranges variable; remove the two lines it appears in.
  11. 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 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.

  12. So, we have some state external to the loop; the sequence(state:) function seems like a good fit. Insert this on the line above the while loop:
        let result =
  13. Begin to type 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
    
        }
  14. We can just call the input parameter to the closure 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
        }
  15. Move the closing brace down so the entire loop is inside the closure. Ignore the Missing return in a closure… error message.
  16. We need to know when to stop, and that is when 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 }
  17. Now we can listen to the error message; insert this at the end of the closure:
        return foundRange
  18. 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 searchRange to let searchRange.
  19. Now all that is left is to actually return something from the method. Click on 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:
    Activity B: Implementing a Lazy Version of a Method
  20. Go to the bottom of the documentation page, where it says this:
    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.

  21. Place the text marker inside result again. In the top right corner, the type has changed to this:
    LazySequence<UnfoldSequence<Range<String.Index>, Range<String.Index>>>
    Activity B: Implementing a Lazy Version of a Method

    Copy and paste it in as the return type of the method.

  22. Replace let result = with return.
  23. Verify that it builds.
  24. 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.

  25. Run all unit tests (U) and verify that they all pass.

    And that's it. Congratulations!