[swift-evolution] Bike-shedding alternate collections API

Thu Mar 24 02:07:38 CDT 2016

Bike-shedding alternate collections API - cut down to keep them short enough to post.

They differ from the current collections API and the new proposed collections API in that:
They use the existing external iterator, `iterator.next()`, rather than the proposed style, `iterator.next(&i)`, because the new style ties the iterator to a particular collection type and therefore cannot be type erased. Type erasure is required to keep return types generic, e.g. rather than map returning an Array it returns an `AnyNextorable<Element>` (see point 5 below).
The protocols are not, in general, heirarchical; instead they are small building blocks at the top level that can be fitted together.
Protocols are split when a good default implementation cannot be provided, e.g. CountableCollection is seperate because the default of iterating and counting the elements is not a good implimentation of count.
Hierarchies are used for convenience, e.g. ArrayCollection is a convenience protocol that extends base protocols.
The protocol member's return generic implementations of protocols, e.g. where you might return an Array instead you return an `AnyNextorable<Element>`. This sidesteps issues with associated types and generics and prevents large type signatures. The downside is that you have comitted to a particular interface and therefore lost covariance. When generics are completed hopefully these return types can be replaced with `Any<... where ...>`, e.g. `Any<Nextorable where Element == Element>`
LazyNextable is split out seperately so that the semantics of lazy are articulated in the type system. The design of LazyNextable is also compatible with adding ParallelLazyNextable in the future.
The naming of the protocols is one of:
Xxxable because it is a main behavioural protocol and its main member is xxx, e.g. Nextorable has a main property nextor.
If in the rare case that a protocol extends another protocol then the new property is prepended, e.g. MutableSubstriptable extends Substriptable and the main method added is mutable subscripting.
If they don't have a main member then they are named after what they are used for, e.g. ArrayCollection defines the members of Array like collections. Note name format of XxxCollection.
AnyXxxx is a type erased implimentation of Xxx, e.g. AnyLazyNextable is an erased LazyNextable.
Xxxee and xxxee is used for the subject of an action, e.g. Rangee is a collection of methods that a type must impliment to be used in a Range.
Range has an Int index of 0 to count - 1 and a value of start + index * stride, where start and stride are of type Rangee. Int and Double via extension are made Rangees.
Index, used in Subscriptables, can be any type.

The main protocols that define what a collection is are:

/// Mutable, potentially infinite, and multiply traversable (because nextor is non-mutating) collection.
protocol Nextorable {
    associatedtype Element

    /// Give a new nextable for iterating through the collection.
    /// The collection can be iterated multiple times and therefore each Nextable must contain its own state.
    var nextor: AnyNextable<Element> { get }

    /// View this collection as a LazyNextable.
    /// If the collection changes then the view may or may not change, it depends upon the semantics of the collection.
    /// Default implementation provided.
    var asLazy: AnyLazyNextable<Element> { get }

    /// Note how the map's return type is a protocol not a specific type.
    /// Default implementation provided.
    @warn_unused_result func map<Mapped>(@noescape mapper: (Element) throws -> Mapped) rethrows -> AnyNextorable<Mapped>

    /// Default implementation provided for IterableCollections.
    func forEach(@noescape eacher: (Element) throws -> Void) rethrows

    /// View this Nextorable as an AnyNextorable.
    /// Default implementation provided.
    var asNextorable: AnyNextorable<Element> { get }
}

/// Protocol that allows a sequence of elements to be iterated from a collection or generated anew by calling the next method.
protocol Nextable {
    associatedtype Element

    /// Gives the next element in a collection or generates a new element (if used as a generator), if there is one.
    /// A return of nil, mean no more elements.
    /// If the collection underlying the Nextable isn't modified and if this Nextable has returned nil it should continue to return nil.
    /// If the collection underlying the Nextable is modified whilst iterating; next can return a previous value that was in the collection, can skip some or all values, or can repeat values, but should still ultimate terminate when called repeatedly and return nil.
    /// Even if next has returned nil, if the underlting collection is modified it could return values again.
    @warn_unused_result mutating func next() -> Element?

    /// View this Nextable as an AnyNextable.
    /// Default implementation provided.
    @warn_unused_result mutating func asNextable() -> AnyNextable<Element>
}

/// Thrown by the next function in a LazyNextable collection to indicate the end of the collection.
/// LazyNext.end can also be thrown to act like a break in a for loop.
enum LazyNext: ErrorType {
    case end
}

/// An immutable, potentially infinite, and singley traversable collection that is evaluated lazily.
/// The internal iterator is exposed via next, so that something external may control the iteration.
protocol LazyNextable {
    associatedtype Element

    /// Eagerly gives the next element in the lazy collection.
    /// A throw of LazyNext.end means no more elements.
    /// If the LazyNextable isn't modified and it has thrown LazyNext.end it should continue to thrown LazyNext.end.
    /// If the LazyNextable is modified whilst iterating; next can return a previous value that was in the collection, can skip some or all values, or can repeat values, but should still ultimate terminate when called repeatedly and throw LazyNext.end.
    /// Even if next has thrown LazyNext.end, if the collection is modified it could return values again.
    @warn_unused_result mutating func next() throws -> Element

    /// Maps all the remaining elements of the collection lazily.
    /// See next for semantics in the face of mutation of the underlying collection.
    /// The returned LazyNextable typically modifies self, hence this function is mutating
    /// Default implementation provided.
    @warn_unused_result mutating func map<Mapped>(mapper: (Element) throws -> Mapped) -> AnyLazyNextable<Mapped>

    /// Applies the eacher eagerly to all the remaining elements in the collection.
    /// Note: a mutating function since it forces evaluation of the colection, it is eager.
    /// See next for semantics in the face of mutation of the underlying collection.
    /// Default implementation provided.
    mutating func forEach(@noescape eacher: (Element) throws -> Void)

    /// View into this collection wrapped in an AnyLazyNextable.
    /// Note it is a mutating func because the LazyNextable returned can mutate this LazyNextable (self).
    /// Default implementation provided.
    @warn_unused_result mutating func asNextable() -> AnyLazyNextable<Element>
}

protocol Subscriptable {
    associatedtype Element
    associatedtype Index
    var firstIndex: Index { get }
    var lastIndex: Index { get }
    subscript(index: Index) -> Element { get }

    /// Provides a lazy view into this collection; mapping the indices.
    /// It provides a collection whose subscript(Index) is `self[range[index]]`.
    /// If self or range change then this view changes.
    /// Ideally you could specify a generic argument for subscript range, but in Swift 2.1 you can't :(;
    /// something like, `subscript<S: SubscriptableCollection where S.Element = Index>(range: S) -> Subscriptable<Element, S.Index> { get }`.
    /// To partially compensate use `asSubscriptable` as in `self[range.asSubsctiptable]`.
    /// This only partially compensates because the range argument is `AnySubscriptable<Index, Index>`, not `AnySubscriptable<Index, NewIndex>` and hence the return type is `AnySubscriptable<Element, Index>` not `AnySubscriptable<Element, NewIndex>`.
    /// Default implementation provided.
    subscript(range: AnySubscriptable<Index, Index>) -> AnySubscriptable<Element, Index> { get }

    /// View as a type erased Subscriptable.
    /// Default implementation provided.
    var asSubscriptable: AnySubscriptable<Element, Index> { get }
}

/// A SubscriptableCollection that also allows subscripts to mutate self.
protocol MutableSubscriptableCollection: Subscriptable {
    // `sets` commented out because of compiler issues in Xcode 7.3
    subscript(index: Index) -> Element { get /*set*/ }
    subscript(range: AnySubscriptable<Index, Index>) -> AnyMutableSubscriptable<Element, Index> { get /*set*/ }
    var asMutableSubscriptable: AnyMutableSubscriptable<Element, Index> { get }
}

/// Provide the capabilities needed to impliment Range.
/// Ranges are indexed with an Int index between 0 and count - 1 inclusive and they return start + index * stride, where start and stride are Rangees.
/// Via extensions Int and Double are Rangees.
protocol Rangee {
    /// self += rhs
    mutating func add(rhs: Self)

    /// self -= rhs
    mutating func sub(rhs: Self)

    /// self *= rhs
    mutating func mult(rhs: Self)

    /// self /= rhs
    mutating func div(rhs: Self)

    /// Converts to an Int, truncating towards 0 if necessary
    var toInt: Int { get }

    /// Convert from an int, fails if the int is not representable
    static func fromInt(i: Int) -> Self
}

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160324/1307557d/attachment-0001.html>