[swift-evolution] Rethink about the SequenceType, GeneratorType and CollectionType

Susan Cheng susan.doggie at gmail.com
Mon Jan 11 04:14:56 CST 2016

Jordan Rose has a thought in PermutationGenerator thread that about any
GeneratorType "is-a" SequenceType. (I missed the thread)

So i get a graph with:

SequenceType -----------------------------------> CollectionType
        ∟ generate() ----> GeneratorType

if this correct, we will redefine the GeneratorType as SequenceType

/// Encapsulates iteration state and interface for iteration over a

/// *sequence*.


/// - Note: While it is safe to copy a *generator*, advancing one

///   copy may invalidate the others.


/// Any code that uses multiple generators (or `for`...`in` loops)

/// over a single *sequence* should have static knowledge that the

/// specific *sequence* is multi-pass, either because its concrete

/// type is known or because it is constrained to `CollectionType`.

/// Also, the generators must be obtained by distinct calls to the

/// *sequence's* `generate()` method, rather than by copying.

public protocol GeneratorType : SequenceType {

    /// The type of element generated by `self`.

    typealias Element

    /// Advance to the next element and return it, or `nil` if no next

    /// element exists.


    /// - Requires: `next()` has not been applied to a copy of `self`

    ///   since the copy was made, and no preceding call to `self.next()`

    ///   has returned `nil`.  Specific implementations of this protocol

    ///   are encouraged to respond to violations of this requirement by

    ///   calling `preconditionFailure("...")`.


    public mutating func next() -> Self.Element?


extension GeneratorType {

    public func generate() -> Self {

        return self



and discard this(break circularity between SequenceType and GeneratorType):

extension SequenceType where Self.Generator == Self, Self : GeneratorType {

    public func generate() -> Self


also, adding the follows to stdlib:

public extension SequenceType where Self : Indexable {

    var startIndex: MultipassIndex<Generator> {

        var g = self.enumerate().generate()

        if let (idx, val) = g.next() {

            return MultipassIndex(reachEnd: false, index: idx, buffer: val,
generator: g)


        return MultipassIndex(reachEnd: true, index: nil, buffer: nil,
generator: g)


    var endIndex: MultipassIndex<Generator> {

        return MultipassIndex(reachEnd: true, index: nil, buffer: nil,
generator: self.enumerate().generate())


    subscript(position: MultipassIndex<Generator>) -> Generator.Element {

        return position.buffer!



// Note: Requires G has value semantics

public struct MultipassIndex<G: GeneratorType> : ForwardIndexType {

    public func successor() -> MultipassIndex {

        var r = self

        if !reachEnd, let (idx, val) = r.generator.next() {

            r.index = idx

            r.buffer = val

        } else {

            r.reachEnd = true

            r.index = nil

            r.buffer = nil


        return r


    var reachEnd: Bool

    var index: Int?

    var buffer: G.Element?

    var generator: EnumerateGenerator<G>


public func == <T>(x: MultipassIndex<T>, y: MultipassIndex<T>) -> Bool {

    return x.index == y.index


That means we can defined a collection as follows and implement Indexable

struct Fib : CollectionType {

    typealias Generator = FibGenerator

    var a, b: Int

    func generate() -> FibGenerator {

        return FibGenerator(a: a, b: b)



struct FibGenerator : GeneratorType {

    var a, b: Int

    mutating func next() -> Int? {

        let temp = a

        (a, b) = (b, a + b)

        return temp



in this case, because of GeneratorType is clearly a destructive iteration
type and CollectionType is clearly a multi-pass indexed type

we should stop using the SequenceType (or just rename it to _SequenceType
and tell people don't use it directly) directly. we have the GeneratorType
which confirms SequenceType already. it can reduce
confusion of SequenceType.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160111/63d3505a/attachment.html>

More information about the swift-evolution mailing list