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

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

2 Likes

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

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.

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.

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)

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

1 Like

+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.).

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()
}

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.

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:

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

Indeed, it is possible to implement cycle(_:) using what's already in the standard library. What would be interesting to see is the performance difference between a custom type vs. the sequence-joined combination.

It would be an interesting micro-benchmark regardless, actually. Would you like to give it a shot?

This will hit the same problem of a potentially trapping count (although in this case it will only be trapping in some cases, when constructed with count: nil). Besides, as @benrimmington posted previously, sequence(element) { $0 } will achieve the same result. Admittedly a little more cryptic, but not too hard to write.

1 Like

I deleted my benchmarks here, as they were skewed by a silly typo. I fed an array version to one and a sequence to the other

2 Likes

That's annoying indeed, I don't think that many will hit the trapping count, but it's unfortunate that that is allowed at all. It would be great to come up with a way for Repeated to be possibly infinite, while not sacrificing much efficiency. The easiest way right now would be to make Repeated.count optional, but that would involve a few more checks against nil on every access. Alternatively, Repeated could be a type-erased thing that fed accessors from FiniteRepeated and InfiniteRepeated. These will still all have the constraint of having Int.max - 1 be the last possible index, trapping on Int.max, but that's because of the way Collection works, which I assume is not up for debate at this point :slight_smile:

Back to cycled: if we are going to consider the ?? .max trick here, I'd still argue for it being placed in repeatElement. The optional count argument is the API that I expected the function to have anyway, and I reckon that the benefits outweigh the costs.

Edit 1: Added sequence(state:next:) test.
Edit 2: Added XCTAssertEqual calls.
Edit 3: Added build configuration.

The custom type was faster than the other combinations.

Average times (seconds):

Swift 4.0.3 Swift 4.1 Swift 4.2
(Xcode 9.2) (Xcode 9.3) (Xcode 9.3)
testCustom() 0.227 0.587 0.417
testRepeat() 0.320 0.685 0.501
testUnfoldFirst() 0.318 0.677 0.510
testUnfoldState() 0.273 0.632 0.471

Using:

  • Xcode 9.2 (9C40b) with Swift 4.0.3
  • Xcode 9.3 beta 4 (9Q127n) with Swift 4.1
  • Trunk Development (master) March 17, 2018 snapshot.
  • "Debug" build configuration with no optimization [-Onone].

I added methods to Collection instead of Sequence.

import XCTest

extension Collection {

  public func cycledCustom() -> CycleSequence<Self> {
    return CycleSequence(self)
  }

  public func cycledRepeat() -> FlattenSequence<Repeated<Self>> {
    return repeatElement(self, count: self.isEmpty ? 0 : .max).joined()
  }

  public func cycledUnfoldFirst() -> FlattenSequence<UnfoldFirstSequence<Self>> {
    return sequence(first: self, next: { $0.isEmpty ? nil : $0 }).joined()
  }

  public func cycledUnfoldState() -> UnfoldSequence<Element, Iterator> {
    return sequence(state: makeIterator(), next: { iterator in
      if let nextElement = iterator.next() {
        return nextElement
      }
      iterator = self.makeIterator() // NOTE: captures `self`.
      return iterator.next()
    })
  }
}

public struct CycleSequence<C: Collection> : Sequence, IteratorProtocol {

  internal let _collection: C
  internal var _iterator: C.Iterator

  internal init(_ collection: C) {
    _collection = collection
    _iterator = collection.makeIterator()
  }

  public mutating func next() -> C.Element? {
    if let nextElement = _iterator.next() {
      return nextElement
    }
    _iterator = _collection.makeIterator();
    return _iterator.next()
  }
}

class CycleBenchmark: XCTestCase {

  let _prefix = 1_000_000
  let _source = 0 ... 999

  func testCustom() {
    self.measure {
      var count = 0
      for _ in _source.cycledCustom().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testRepeat() {
    self.measure {
      var count = 0
      for _ in _source.cycledRepeat().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testUnfoldFirst() {
    self.measure {
      var count = 0
      for _ in _source.cycledUnfoldFirst().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }

  func testUnfoldState() {
    self.measure {
      var count = 0
      for _ in _source.cycledUnfoldState().prefix(_prefix) {
        count += 1
      }
      XCTAssertEqual(count, _prefix)
    }
  }
}
4 Likes

Nice! Could you please show the test function? I assume you cycled over an array? Does array size have an impact?

@Alexandre_Lopoukhine, the tests are available at https://forums.swift.org/raw/11254/28, or by scrolling the above source code. I cycled over a CountableClosedRange, so it doesn't have an impact.

Using Xcode, you can create a cross-platform "Empty" project; add a macOS "Unit Testing Bundle" target; and paste the code into the target's source file.

1 Like

I'm a victim of the invisible scrollbar, didn't realise there was more :slight_smile:

1 Like

Ok, well if the results are so close, then we better choose the solution for other reasons. I'd go for the custom type, it lets us mutate the implementation if there's ever a reason, and swift's type system plays better with custom types than typealiases in general.

1 Like