Protocol

LazySequenceProtocol

A sequence on which normally-eager operations such as map and filter are implemented lazily.

Declaration

protocol 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,

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

is a sequence containing { 2, 4, 6 }. Each time an element of the lazy sequence is accessed, an element of the underlying array is accessed and transformed by the closure.

Sequence operations taking closure arguments, such as map and filter, are normally eager: they use the closure immediately and return a new array. Using the lazy property gives the standard library explicit permission to store the closure and the sequence in the result, and defer computation until it is needed.

To add new lazy sequence operations, extend this protocol with methods that return lazy wrappers that are themselves LazySequenceProtocols. For example, given an eager scan method 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<ResultElement>(
    _ initial: ResultElement,
    _ nextPartialResult: (ResultElement, Element) -> ResultElement
  ) -> [ResultElement] {
    var result = [initial]
    for x in self {
      result.append(nextPartialResult(result.last!, x))
    }
    return result
  }
}

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

struct LazyScanIterator<Base : IteratorProtocol, ResultElement>
  : IteratorProtocol {
  mutating func next() -> ResultElement? {
    return nextElement.map { result in
      nextElement = base.next().map { nextPartialResult(result, $0) }
      return result
    }
  }
  private var nextElement: ResultElement? // The next result of next().
  private var base: Base                  // The underlying iterator.
  private let nextPartialResult: (ResultElement, Base.Element) -> ResultElement
}

struct LazyScanSequence<Base: Sequence, ResultElement>
  : LazySequenceProtocol // Chained operations on self are lazy, too
{
  func makeIterator() -> LazyScanIterator<Base.Iterator, ResultElement> {
    return LazyScanIterator(
      nextElement: initial, base: base.makeIterator(), nextPartialResult)
  }
  private let initial: ResultElement
  private let base: Base
  private let nextPartialResult:
    (ResultElement, Base.Element) -> ResultElement
}

and finally, we can give all lazy sequences a lazy scan method:

extension LazySequenceProtocol {
  /// Returns a sequence containing the results of
  ///
  ///   p.reduce(initial, nextPartialResult)
  ///
  /// for each prefix `p` of `self`, in order from shortest to
  /// longest.  For example:
  ///
  ///     Array((1..<6).lazy.scan(0, +)) // [0, 1, 3, 6, 10, 15]
  ///
  /// - Complexity: O(1)
  func scan<ResultElement>(
    _ initial: ResultElement,
    _ nextPartialResult: (ResultElement, Element) -> ResultElement
  ) -> LazyScanSequence<Self, ResultElement> {
    return LazyScanSequence(
      initial: initial, base: self, nextPartialResult)
  }
}
  • See also: LazySequence, LazyCollectionProtocol, LazyCollection

Topics

Associated Types

associatedtype Elements

A Sequence that can contain the same elements as this one, possibly with a simpler type.

Required.

Instance Properties

var elements: Self.Elements

A sequence containing the same elements as this one, possibly with a simpler type.

Required. Default implementation provided.

var lazy: Self.Elements

Instance Methods

func joined() -> LazySequence<FlattenSequence<Self.Elements>>

Returns a lazy sequence that concatenates the elements of this sequence of sequences.

Relationships

Inherits From

See Also

Lazy Collections

protocol LazyCollectionProtocol

A collection on which normally-eager operations such as map and filter are implemented lazily.