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

[Andrew Bennett]

+1 looks good, I had a go at implementing it and I think it may require
changes not discussed in the proposal.

You've covered the potential issues fairly well, to be a little more
explicit these are the issues I've found:

 1) LazySequenceType's property array cannot be defined without an infinite
sized array.
 2) what should [1,2,3].cycle.suffix(4) return? [3,1,2,3] probably has the
least surprises, but it's like asking what's the number before infinity.

 3) dropLast should return AnySequence(self), but requires specialisation,
this may have to also be a fatalError (see below).


One issue I don't think you've mentioned, and I don't seem to be able to
resolve is this:

let mySequence = [1,2,3].cycle.dropLast(1)

mySequence.suffix(7)


This could have well defined behaviour (see part 2 above), however the
implementation has some issues.

In this case mySequence is an AnySequence<Int>, mySequence.suffix(7) uses
AnySequence's specialisation and so tries to iterate over the entire
sequence to find the suffix. AnySequence<Int> is type-erased so there's no
way to specialise when the underlying sequence is infinite (to get a valid
implementation of suffix).

Potential solutions:
 * Replace erased Any* types with a more flexible alternative that doesn't
remove type information (higher kinded types perhaps).
 * Replace SequenceType with two protocols FiniteSequenceType and
InfiniteSequenceType, have type erased versions of each, duplicate all the
things.
 * Add a property to SequenceType to indicate if it's definitely finite
(undefined?), AnySequence uses a different backing implementation depending
on this boolean.

Here's the implementation I used in a playground to toy with this:

public struct CycleSequence<Base : CollectionType> : LazySequenceType {

    private let base: Base

    private init(_ collection: Base) {

        self.base = collection

    }

    @warn_unused_result

    public func generate() -> CycleGenerator<Base> {

        return CycleGenerator<Base>(base.generate)

    }

    public var array: [Base.Generator.Element] {

        fatalError("This is undefined!")

    }

}


public struct CycleGenerator<Base : CollectionType> : GeneratorType {

    private let generatorProducer: () -> Base.Generator

    private var generator: Base.Generator

    private init(_ generatorProducer: () -> Base.Generator) {

        self.generatorProducer = generatorProducer

        self.generator = generatorProducer()

    }

    @warn_unused_result

    public mutating func next() -> Base.Generator.Element? {

        if let element = generator.next() {

            return element

        }

        generator = generatorProducer()

        return generator.next()

    }

}


extension CycleSequence {

    @warn_unused_result

    public func dropLast(n: Int) -> AnySequence<Base.Generator.Element> {

        return AnySequence(self)

    }

    @warn_unused_result

    public func suffix(maxLength: Int) -> AnySequence<Base.Generator.Element>
{

        let maxCount = base.count.toIntMax()

        let sequenceLength = maxCount >= Int.max.toIntMax() ? Int.max : Int
(maxCount)

        if maxLength < sequenceLength {

            return AnySequence(base.suffix(maxLength))

        }

        return self.dropFirst(sequenceLength - (maxLength %
sequenceLength)).prefix(maxLength)

    }

}


extension CollectionType {

    public var cycle: CycleSequence<Self> { return CycleSequence(self) }

}



// this produces an infinite loop when evaluating .suffix(7)

let cycle = ["a", "b", "c"].cycle

cycle.dropLast(1).suffix(7).forEach { print("suffix: \($0)") }



On Mon, Dec 28, 2015 at 6:35 PM, Developer via swift-evolution <
swift-evolution at swift.org> wrote:

> +1.  Stream support is long overdue.
>
> ~Robert Widmann
>
> 2015/12/28 2:20、Kevin Ballard via swift-evolution <
> swift-evolution at swift.org> のメッセージ:
>
> > ## Introduction
> >
> > Add a new property `cycle` to CollectionType that returns an infinite
> SequenceType that yields the elements of the collection in a loop.
> >
> > ## 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.
> >
> > ## 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). 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()`.
> >
> > 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. 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.
> >
> > ## Impact on existing code
> >
> > None
> >
> > -Kevin Ballard
> > _______________________________________________
> > swift-evolution mailing list
> > swift-evolution at swift.org
> > https://lists.swift.org/mailman/listinfo/swift-evolution
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151229/6ac7c741/attachment.html>