[swift-evolution] Proposal: CollectionType.cycle property for an infinite sequence

[Dave Abrahams]

> On Dec 27, 2015, at 11:20 PM, Kevin Ballard via swift-evolution <swift-evolution at swift.org> wrote:
> 
> ## Introduction
> 
> Add a new property `cycle` to CollectionType that returns an infinite SequenceType that yields the elements of the collection in a loop.

The name should give an explicit indication that the result is infinite, e.g. “repeatedForever".  

> ## Motivation
> 
> It's sometimes useful to be able to have an infinite sequence. For example, `CollectionOfOne(x).cycle` could be used to have an infinite sequence of a single element (similar to Repeat but without a count). A common use for infinite sequences is zipping with a finite sequence. As far as I'm aware, the stdlib does not currently provide any way to create such an infinite sequence.

If this is, as I suspect, the primary use case, I would prefer a much clearer incantation than CollectionOfOne(x).repeatedForever.  The part before the parentheses is mostly irrelevant.  I suppose [x].repeatedForever could work, but needing an array allocation makes me sad.  I wish I had something better to suggest… This may in fact be the best we can do.

> ## Proposed solution
> 
> Extend CollectionType with a new property `cycle` that yields a type that conforms to SequenceType. This sequence yields each element of the collection in an infinite loop.
> 
> ## Detailed design
> 
> 2 new types would be added:
> 
> struct CycleSequence<Base : CollectionType> : LazySequenceType { ... }
> struct CycleGenerator<Base : CollectionType> : GeneratorType { ... }
> 
> CollectionType would be extended with a property:
> 
> extension CollectionType {
>    public var cycle: CycleSequence<Self> { get }
> }
> 
> This is an extension of CollectionType instead of SequenceType because it requires a multi-pass sequence (and SequenceType does not provide that guarantee).

You can copy the elements into an array in that case.  Whether or not we should provide that is an open question, but we do similar things for, e.g., reverse().

> The returned type conforms to SequenceType instead of CollectionType because there is no possible `endIndex` that satisfies the requirement of being reachable from `startIndex` by zero or more applications of `successor()`.

Yeah… I’m not sure we want to do so, but we should consider loosening that requirement.  After all, x.repeatedForever.prefix(1000) is in principle a perfectly cromulent collection that shouldn’t require copying x’s elements into new storage.

> Because the default eager versions of map and filter will execute forever on an infinite sequence, CycleSequence conforms to LazySequenceType instead of SequenceType in order to provide lazy versions of those functions.

It would arguably be more appropriate to only provide repeatedForever on instances of LazySequenceType.  The idea has always been that users are surprised when they see their map/filter closure’s side-effects happen multiple times, or at odd times, so we make them write “.lazy” to specifically opt into that behavior.  I’ve always had mixed feelings about this, thinking that maybe it would be better to educate people about laziness, but that’s what we currently do.  

We could weasel out of the “multiple side-effects” problem by declaring that since the result is not a collection you can only make one pass through any part of the result, so if your side-effect over-fires, it’s on you.  I wouldn’t be in favor of making this sequence *actually* single-pass though, and this doesn’t solve the “side-effects at odd times” issue.

> Additionally, it will provide implementations of the eager versions that simply trigger a fatalError(), as the alternative is an infinite loop that consumes more and more memory.

Why do this?  What would these eager APIs look like?

> 
> ## Impact on existing code
> 
> None
> 
> -Kevin Ballard
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution