+1 this seems useful and is a nice thing. The standard library should be full of nice things.
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, 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
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.
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.
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
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
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)
}
}
}
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.
I'm a victim of the invisible scrollbar, didn't realise there was more
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.