cycled.md

Introducing a "cycled" method to the standard library

• Proposal: SE-TBD
• Author(s): Erica Sadun
• Review manager: TBD
• Status: Preliminary Implementation in Proposal

Introduction

This proposal introduces a cycled() method on Sequence, allowing the creation of an infinite sequence by recycling the members of the source sequence.

This proposal was requested in SR-6864

This proposal was discussed on-forum in the [Starter Pitch] Introducing a cycled method to Sequence thread and in 2015 in the Proposal: CollectionType.cycle property for an infinite sequence thread introduced by Lily Ballard.

Motivation

From SR-6864:

It is often useful to cycle over a sequence indefinitely. For example, just like you can write zip(repeatElement("foo", count: Int.max), myArray) and zip(1..., myArray), you could write zip([.grey,.white].cycle(), myArray).

The spelling of cycle has been changed to cycled for this proposal.

Detailed Design

Introducing a new SequenceCycle type enables you to store a sequence, reconstructing it each time its elements are exhausted.

/// A sequence containing the same elements as `BaseSequence`
/// repeated infinitely.
///
/// Construct using `sequence.cycled()`
public struct SequenceCycle<BaseSequence: Sequence> : Sequence, IteratorProtocol {
    
  public mutating func next() -> BaseSequence.Element? {
    if let nextElement = _iterator.next() {
      return nextElement
    }
    _iterator = _sequence.makeIterator(); 
    return _iterator.next()
  }
    
  /// Access only through `Sequence.cycled()`
  internal init(_ sequence: BaseSequence) {
    _sequence = sequence
    _iterator = sequence.makeIterator()
  }
    
  internal let _sequence: BaseSequence
  internal var _iterator: BaseSequence.Iterator
}

extension Sequence {
  /// Return a lazy sequence endlessly repeating the elements
  /// of `self` in an infinite cycle.
  ///
  /// For example:
  ///
  ///     Array(zip(0...4, ["even", "odd"].cycled()))
  ///
  /// returns
  ///
  ///     [(0, "even"), (1, "odd"), (2, "even"), (3, "odd"), (4, "even")]
  ///
  /// - SeeAlso: [SR-6864](https://bugs.swift.org/browse/SR-6864)
  ///
  /// - Caution: This returns an infinite sequence. Do not attempt
  ///   to `count` its members.
  ///
  /// - Caution: Make sure a cycled sequence supports multiple calls
  ///   to its `makeIterator()` method.
  public func cycled() -> SequenceCycle<Self> {
      return SequenceCycle(self)
  }
}

For example, you might zip a range of numbers with the words ["even", "odd"]:

Array(zip(0...4, ["even", "odd"].cycled()))
// returns [(0, "even"), (1, "odd"), (2, "even"), (3, "odd"), (4, "even")]

The single-element

repeatElement("foo", count: Int.max)

call evolves to

["foo"].cycled()
// or
CollectionOfOne("foo").cycled()

Although this forces you to place the string within square brackets or use CollectionOfOne, the results remain readable and the intent clear.

No special checks are made for empty sequences. The result of the following code is [].

Array(zip(myArray, Array<String>().cycled()))

Source compatibility

This proposal is strictly additive.

Effect on ABI stability

This proposal does not affect ABI stability.

Effect on API resilience

This proposal does not affect ABI resilience.

Alternatives Considered

• Swift may want to consider further adopting Python-inspired iteration tools from the itertools library. The scope for this proposal is limited to the single cycled infinite cycle.

• An earlier version of this proposal used a different algorithm to create its repeated sequences:

extension Sequence {
    public func cycled(count: Int = .max) -> FlattenSequence<Repeated<Self>> {
        guard let _ = self.first(where: { _ in true }) else {
            return repeatElement(self, count: 1).joined()
        }
        return repeatElement(self, count: count).joined()
    }

Benchmarks show that the current approach is slightly more performant and allows desired "infinite sequence" characteristics.

'-[Test2Tests.CycleBenchmark testCycledRepeated]' passed (3.526 seconds).
'-[Test2Tests.CycleBenchmark testSequenceCycle]' passed (2.360 seconds).
Starting Test: Using cycledSequenceCycle()
Ending Test : Using cycledSequenceCycle()
Elapsed time: 0.496450918028131
Starting Test: Using cycledRepeated()
Ending Test : Using cycledRepeated()
Elapsed time: 0.509369512787089

A third approach using the built-in sequence(first:,next:) function was discarded as it does not support the case that repeats an empty sequence.