[Starter Pitch] Introducing a `cycled` method to `Sequence`

Evolution Pitches
1

Needed something to do while waiting for a child at an appointment. I'm curious as to what the reaction will be. This was tagged as a starter proposal on SR-6864

Gist here: cycled.md · GitHub

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 Kevin 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.

10 Likes
2

Hmm. This reminds me of iterators. Do we have that in Swift?

Another thing it reminds me of is sequences in general. You could maybe have a Sequence-like type that generates the next element on-demand:

  • 1, 2, 3, 4, 5 (naturals)
  • 1, 1, 2, 3, 5, 8, 13 (fibonacci)
  • 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 (naturals mod P; mod 5 in this case - it’s infinite, but it can be done with the proposal because it’s periodic. Still, for big P it might be better to generate it on-demand).

Anyway. My point is: I think this could be better addressed with iterators. That’d be more general.

Providing a CycledSequence wouldn’t be too hard, and the StdLib could even implement it with iterators behind the scenes.

I need to do some research to give you a Swifty model of how an Iterator would work (I’m assuming it doesn’t exist in Swift). I’ll be back tomorrow, I think this can work.

What do you think? Do iterators sound good?

— Félix

3

I believe the two sequence functions from SE-0094 do what you're looking for.

1 Like
4

Ah, then... I’m talking behind the times ^^.

Well, fwiw, I support the pitch. If iterators are already implemented, this is just a helper function for a use case that probably deserves it. I think it’s justified.

Edit: jesus I sounded very bad there. I’m sorry. I fixed it.

5

In support of the idea.
If we're adding an infinite cycled(), a finite cycled(times:) should be considered as well.

6

I'm curious as to how you're planning on using this. Does zip(_:_:) with a Range not cover your needs?

8

Has justification been provided for this to be in the core language vs a third party library?

It would be nice for the implementation to fail on endless traversal, or provide decent behavior for min/max, but currently custom implementations of Sequence methods are dropped by wrapping types like AnySequence.

1 Like
9

Really love this proposal. I needed it a few days ago, and ended up writing it myself. +1 from me!

I think your implementation still needs a func makeIterator() -> Iterator { return self }?

10

Actually in my face: if the sequence conforms to IteratorProtocol it automatically returns self for makeIterator(). You learn something new every day.

2 Likes
11

+1 this seems useful and is a nice thing. The standard library should be full of nice things.

2 Likes
12

Sequence.prefix(_:) should cover that, although that would wraps the SequenceCycle instance into an AnySequence, which might not be desirable...

13

This is a useful algorithm, and we should have it in some form. I'm a little bit concerned with the proposed implementation, though.

Currently Sequence does not guarantee that the iterator returned by makeIterator() will allow repeated traversals of the sequence.

14

It seems to me that it should be possible to make SequenceCycle conform to Collection, RandomAccessCollection even, if Base: RandomAccessCollection. In that case, it can use DefaultSlice as SubSequence and then limiting the number of iterations can be done as:

cycle([1,2,3])[..<42]

One downside of Collection conformance for this type, that is infinite by design, would be that count would have to be implemented as fatalError("count of an infinite collection"). On the other hand it's better than getting an OOM eventually, when trying to create an Array from SequenceCycle.

15

One more thought (and I'm sorry for a flood of random ideas).
I believe the major use-case for this new function would be something like: [1, 2, 3].cycled(), what we can do instead is have an overloaded free function:

func cycle<C: Collection>(_ source: C) -> SequenceCycle { ... }
func cycle<Element>(_ elements: T...) -> SequenceCycle { ... }

(I had to try it to make sure such overloading is allowed, and it is!)

The call site in this case can be either of the following:

cycle(someNumbers)
// or
cycle(1, 2, 3)
16

For context, @Lily_Ballard originally introduced this topic in December 2015 in the following thread:

1 Like
17

+1, though it ought to be named cycle() instead of cycled() (makes it more consistent with other Sequence operation names, like split for e.g.).

18

Would it be okay to use existing sequences for the return type?

public typealias CycleSequence<C: Collection> =
  FlattenSequence<UnfoldFirstSequence<C>>

public func cycle<C: Collection>(_ source: C) -> CycleSequence<C> {
  return sequence(first: source, next: { $0.isEmpty ? nil : $0 }).joined()
}
19

I would propose to implement this in two steps:

1: Let the count parameter of repeatElement(:count:) to be optional, with indefinite repetition on nil.
2: Implement a cycle function, probably as a method on RandomAccessCollection, that uses the repeatElement.

func _repeatElement<Element>(_ element: Element, count: Int? = nil) -> Repeated<Element> { 
    return repeatElement(element, count: count ?? .max) 
} 
extension RandomAccessCollection { 
    func cycled(count: Int? = nil) -> FlattenSequence<Repeated<Self>> { 
        return _repeatElement(self, count: count).joined() 
    } 
} 
Array([1, 2, 3].cycled().prefix(9))
Array([1, 2, 3].cycled(count: 3))

Helpers could be implemented to cache sequences that aren't guaranteed to repeat themselves.

20

As a side point, has there been a discussion on which functions of itertools to steal? Could do a bunch of these in one go, might be a bit more efficient :slight_smile:

21

I've added a link to Kevin's original pitch, mentioned itertools in alternatives considered, added warnings about count and the requirement for multiple calls to makeIterator. Refresh the gist in the first post to see the updates.

1 Like