Bike-shedding alternate collections API


(Howard Lovatt) #1

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
}


(Dave Abrahams) #2

_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/
swift-evolution

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:

1. They use the existing external iterator,

You mean index.

    `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.

The new style does not prevent type erasure. See
https://github.com/apple/swift/blob/swift-3-indexing-model/stdlib/public/core/ExistentialCollection.swift.gyb
for an example.

    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).
2. The protocols are not, in general, heirarchical; instead they are small building blocks at the top level that can be fitted together.
3. 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.
4. Hierarchies are used for convenience, e.g. ArrayCollection is a convenience protocol that extends base protocols.
5. 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>`
6. 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.
7. The naming of the protocols is one of:
     1. Xxxable because it is a main behavioural protocol and its main member is xxx, e.g. Nextorable has a main property nextor.
     2. 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.
     3. 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.
     4. AnyXxxx is a type erased implimentation of Xxx, e.g. AnyLazyNextable is an erased LazyNextable.
     5. 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.
8. 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.
9. Index, used in Subscriptables, can be any type.

Let's cut to the chase: what problem are you trying to solve, and how
does your proposal address that problem?

···

on Thu Mar 24 2016, Howard Lovatt <swift-evolution@swift.org> wrote:

--
Dave


(Howard Lovatt) #3

Detailed comments about iterator inline below.

Big picture is:

Separating lazy collections from eager collection with a view to a future world with lazy parallel collections.
Returning AnyXxx rather than a specific type to both keep types short and to be more flexible.
Removing constraints on Index, useful for linked lists etc.
Changing the way Range works to that it plays nicer with a larger range of types; range[index] = start + index * stride
Flattening the hierarchy, to allow a mix and match approach to features for more flexibility.

Saying problem to be solved is too strong. There is no real problem with the current collections. They work just fine. However I think they could be finessed. Much like many of the things discussed on swift-eveolution :frowning:

_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/
swift-evolution

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:

1. They use the existing external iterator,

You mean index.

For the proposed new collections you would write:

    var iterator = array.iterator
    let element = array.next(&iterator)

You can’t type erase the returned iterator because it must be called on the original array and therefore must be of the type that that specific array’s next method accepts, not an arbitrary AnyIterator type. These proposed iterators are a cross between an internal and external iterator.

The current and the iterator I used are classic internal iterators and therefore can be type erased because they encapsulate the collection being iterated and the iteration state.

   `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.

The new style does not prevent type erasure. See
https://github.com/apple/swift/blob/swift-3-indexing-model/stdlib/public/core/ExistentialCollection.swift.gyb
for an example.

This is for the current behaviour which I used. Is this the correct reference?

···

On 25 Mar 2016, at 8:28 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Thu Mar 24 2016, Howard Lovatt <swift-evolution@swift.org> wrote:

   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).
2. The protocols are not, in general, heirarchical; instead they are small building blocks at the top level that can be fitted together.
3. 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.
4. Hierarchies are used for convenience, e.g. ArrayCollection is a convenience protocol that extends base protocols.
5. 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>`
6. 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.
7. The naming of the protocols is one of:
    1. Xxxable because it is a main behavioural protocol and its main member is xxx, e.g. Nextorable has a main property nextor.
    2. 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.
    3. 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.
    4. AnyXxxx is a type erased implimentation of Xxx, e.g. AnyLazyNextable is an erased LazyNextable.
    5. 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.
8. 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.
9. Index, used in Subscriptables, can be any type.

Let's cut to the chase: what problem are you trying to solve, and how
does your proposal address that problem?

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #4

In your proposal? That's not what we're intending to bring forward.

···

on Thu Mar 24 2016, Howard Lovatt <swift-evolution@swift.org> wrote:

Detailed comments about iterator inline below.

Big picture is:

Separating lazy collections from eager collection with a view to a future world with lazy parallel collections.
Returning AnyXxx rather than a specific type to both keep types short and to be more flexible.
Removing constraints on Index, useful for linked lists etc.
Changing the way Range works to that it plays nicer with a larger range of types; range[index] = start + index * stride
Flattening the hierarchy, to allow a mix and match approach to features for more flexibility.

Saying problem to be solved is too strong. There is no real problem
with the current collections. They work just fine. However I think
they could be finessed. Much like many of the things discussed on
swift-eveolution :frowning:

On 25 Mar 2016, at 8:28 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Thu Mar 24 2016, Howard Lovatt <swift-evolution@swift.org> wrote:

_______________________________________________ swift-evolution
mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/
swift-evolution

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:

1. They use the existing external iterator,

You mean index.

For the proposed new collections you would write:

    var iterator = array.iterator
    let element = array.next(&iterator)

--
Dave