Rethink about the SequenceType, GeneratorType and CollectionType


#1

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.


#2

i find that IndexingGenerator is also causing circularity

···

2016-01-11 18:14 GMT+08:00 Susan Cheng <susan.doggie@gmail.com>:

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.