LazySequenceProtocol

Overview

Lazy sequences can be used to avoid needless storage allocation and computation, because they use an underlying sequence for storage and compute their elements on demand. For example, doubled in this code sample is a sequence containing the values 2, 4, and 6.

let doubled = [1, 2, 3].lazy.map { $0 * 2 }

Each time an element of the lazy sequence doubled is accessed, the closure accesses and transforms an element of the underlying array.

Sequence operations that take closure arguments, such as map(_:) and filter(_:), are normally eager: They use the closure immediately and return a new array. When you use the lazy property, you give the standard library explicit permission to store the closure and the sequence in the result, and defer computation until it is needed.

Adding New Lazy Operations

To add a new lazy sequence operation, extend this protocol with a method that returns a lazy wrapper that itself conforms to LazySequenceProtocol. For example, an eager scan(_:_:) method is defined as follows:

extension Sequence {
    /// Returns an array containing the results of
    ///
    ///   p.reduce(initial, nextPartialResult)
    ///
    /// for each prefix `p` of `self`, in order from shortest to
    /// longest. For example:
    ///
    ///     (1..<6).scan(0, +) // [0, 1, 3, 6, 10, 15]
    ///
    /// - Complexity: O(n)
    func scan<Result>(
        _ initial: Result,
        _ nextPartialResult: (Result, Element) -> Result
    ) -> [Result] {
        var result = [initial]
        for x in self {
            result.append(nextPartialResult(result.last!, x))
        }
        return result
    }
}

You can build a sequence type that lazily computes the elements in the result of a scan:

struct LazyScanSequence<Base: Sequence, Result>
    : LazySequenceProtocol
{
    let initial: Result
    let base: Base
    let nextPartialResult:
        (Result, Base.Element) -> Result

    struct Iterator: IteratorProtocol {
        var base: Base.Iterator
        var nextElement: Result?
        let nextPartialResult:
            (Result, Base.Element) -> Result
        
        mutating func next() -> Result? {
            return nextElement.map { result in
                nextElement = base.next().map {
                    nextPartialResult(result, $0)
                }
                return result
            }
        }
    }
    
    func makeIterator() -> Iterator {
        return Iterator(
            base: base.makeIterator(),
            nextElement: initial as Result?,
            nextPartialResult: nextPartialResult)
    }
}

Finally, you can give all lazy sequences a lazy scan(_:_:) method:

extension LazySequenceProtocol {
    func scan<Result>(
        _ initial: Result,
        _ nextPartialResult: @escaping (Result, Element) -> Result
    ) -> LazyScanSequence<Self, Result> {
        return LazyScanSequence(
            initial: initial, base: self, nextPartialResult: nextPartialResult)
    }
}

With this type and extension method, you can call .lazy.scan(_:_:) on any sequence to create a lazily computed scan. The resulting LazyScanSequence is itself lazy, too, so further sequence operations also defer computation.

The explicit permission to implement operations lazily applies only in contexts where the sequence is statically known to conform to LazySequenceProtocol. In the following example, because the extension applies only to Sequence, side-effects such as the accumulation of result are never unexpectedly dropped or deferred:

extension Sequence where Element == Int {
    func sum() -> Int {
        var result = 0
        _ = self.map { result += $0 }
        return result
    }
}

Don’t actually use map for this purpose, however, because it creates and discards the resulting array. Instead, use reduce for summing operations, or forEach or a for-in loop for operations with side effects.