[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)
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160104/005525.html

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("...")`.

    @warn_unused_result

    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
automatically:


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