Changes to RangeReplaceableCollectionType


(Haravikk) #1

So today I’ve been trying to put together an implementation of an ordered collection, and I noticed that a lot of important mutating methods are actually grouped together under RangeReplaceableCollectionType, which is actually kind of weird, and has led me to create some more specialised protocols of my own as I actually can’t implement RangeReplaceableCollectionType as it for a number of reasons, which I’ll discuss here:

Remove initialisers

I’m not actually sure why RangeReplaceableCollectionType has required initialisers, since it shouldn’t really matter how you create it since you can reserve capacity separately if you have to, prior to dumping elements into it. However, having these initialiser requirements actually makes it impossible to conform to this protocol if you require other data in order to initialise your type.

For example, my type requires a closure, and I can’t provide a default closure (since the whole point of it is so I can support elements of any type). I can’t think of any reason why these initialiser requirements should be necessary, so hopefully they can just be removed.

Separate out the append(), appendContentsOf() and reserveCapacity() methods:

These methods don’t seem to me to be specific to RangeReplaceableCollectionType, and it seems like they should be separated into an AppendableCollectionType or ExpandableCollectionType or similar. While .replaceRange() could technically be used to fulfil .append() and .appendContentsOf(), it’s not actually replacing anything so it isn’t directly related IMO.

Indeed, it’s conceivable that a type might want to declare the ability to append elements separately from declaring means of removing them arbitrarily (which is what RangeReplaceableCollectionType does), as they may want stricter requirements on removal; for example a queue where elements can only be removed via a removeHead() method or similar.

Separate removal and insertion:

Another case where RangeReplaceableCollectionType forces potentially incompatible actions is that it requires both the ability to remove and to insert arbitrarily into a collection. This is fine if the collection has no form of sort order, however, if the collection is sorted, then insertion operations actually make no sense, requiring the type to ignore the provided indices and just position elements where it decides is best regardless. Removals from a sorted collection don’t have this issue however (if you remove a chunk from them then the remaining elements should still be in the correct order).

Essentially this is a bunch of issues I ran into while attempting to implement an ordered collection with as many of the same capabilities of an Array as possible; while I realise that separation will result in two new CollectionType protocols, I think that it could be beneficial for flexibility when defining our own custom types.


(plx) #2

On the one hand, I agree with your assessment (I’ve also done various order-maintaining collections, and based on that I think you’ll find *neither* `RangeReplaceableCollectionType` nor `MutableCollectionType` are actually adoptable for your type; the “weaker" `MutableCollectionType` isn’t even adoptable by `Set` and `Dictionary` as it requires ordered, freely-reorderable storage).

But, on the other hand, I’m not sure there’s actually a meaningful version of `RangeReplaceableCollectionType` that’d make sense for an order-maintaining collection, anyways, for the reasons you outlined in “Separate removal and insertion”; the API seems entirely inappropriate outside of the `remove*` functions, as you noted (FWIW it seems *mostly* meant to support things like ropes and other, similar data structures).

I’d expect a generic ordered-collection protocol to have methods more like this:

// some example removal methods:
mutating func removeElementsWithin(interval: ClosedInterval<Element>) // <- requires `Element:Comparable`
mutating func removeElementsBefore(element: Element)
mutating func removeElementsAfter(element: Element)

…(e.g., functions that actually reference/take advantage of the ordering), and there’s actually rather a lot of methods that would *potentially* be useful things to have and override.

I’m a bit curious if anything other than (perhaps?) “Collections move Indices” is on tap for standard-library updates on this topic (e.g. any plans for a baked-in “OrderedCollection” protocol, or for tree-shaped collections, etc.?).

PS: FWIW, I’ve found the best way to handle “ordered collections” at present is to make it so it “has-a” (read-only) collection, but is *not* itself a collection…for read-only use this doesn’t change much, and as already noted the mutable-collection protocols are rather troublesome here.

···

On Feb 28, 2016, at 11:47 AM, Haravikk via swift-evolution <swift-evolution@swift.org> wrote:

So today I’ve been trying to put together an implementation of an ordered collection, and I noticed that a lot of important mutating methods are actually grouped together under RangeReplaceableCollectionType, which is actually kind of weird, and has led me to create some more specialised protocols of my own as I actually can’t implement RangeReplaceableCollectionType as it for a number of reasons, which I’ll discuss here:

Remove initialisers

I’m not actually sure why RangeReplaceableCollectionType has required initialisers, since it shouldn’t really matter how you create it since you can reserve capacity separately if you have to, prior to dumping elements into it. However, having these initialiser requirements actually makes it impossible to conform to this protocol if you require other data in order to initialise your type.

For example, my type requires a closure, and I can’t provide a default closure (since the whole point of it is so I can support elements of any type). I can’t think of any reason why these initialiser requirements should be necessary, so hopefully they can just be removed.

Separate out the append(), appendContentsOf() and reserveCapacity() methods:

These methods don’t seem to me to be specific to RangeReplaceableCollectionType, and it seems like they should be separated into an AppendableCollectionType or ExpandableCollectionType or similar. While .replaceRange() could technically be used to fulfil .append() and .appendContentsOf(), it’s not actually replacing anything so it isn’t directly related IMO.

Indeed, it’s conceivable that a type might want to declare the ability to append elements separately from declaring means of removing them arbitrarily (which is what RangeReplaceableCollectionType does), as they may want stricter requirements on removal; for example a queue where elements can only be removed via a removeHead() method or similar.

Separate removal and insertion:

Another case where RangeReplaceableCollectionType forces potentially incompatible actions is that it requires both the ability to remove and to insert arbitrarily into a collection. This is fine if the collection has no form of sort order, however, if the collection is sorted, then insertion operations actually make no sense, requiring the type to ignore the provided indices and just position elements where it decides is best regardless. Removals from a sorted collection don’t have this issue however (if you remove a chunk from them then the remaining elements should still be in the correct order).

Essentially this is a bunch of issues I ran into while attempting to implement an ordered collection with as many of the same capabilities of an Array as possible; while I realise that separation will result in two new CollectionType protocols, I think that it could be beneficial for flexibility when defining our own custom types.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #3

So today I’ve been trying to put together an implementation of an ordered
collection, and I noticed that a lot of important mutating methods are
actually grouped together under RangeReplaceableCollectionType, which is
actually kind of weird, and has led me to create some more specialised
protocols of my own as I actually can’t implement
RangeReplaceableCollectionType as it for a number of reasons, which I’ll
discuss here:

Remove initialisers

I’m not actually sure why RangeReplaceableCollectionType has required
initialisers, since it shouldn’t really matter how you create it since you
can reserve capacity separately if you have to, prior to dumping elements
into it. However, having these initialiser requirements actually makes it
impossible to conform to this protocol if you require other data in order to
initialise your type.

If your type absolutely requires non-zero data elements for an
instance to exist, how would it implement removeAll()?

For example, my type requires a closure, and I can’t provide a default
closure (since the whole point of it is so I can support elements of any
type). I can’t think of any reason why these initialiser requirements should
be necessary, so hopefully they can just be removed.

Could you provide more information about your type? If the closure is
a crucial part of the value, how do you implement collection equality?

Separate out the append(), appendContentsOf() and reserveCapacity() methods:

These methods don’t seem to me to be specific to
RangeReplaceableCollectionType, and it seems like they should be separated
into an AppendableCollectionType or ExpandableCollectionType or similar.
While .replaceRange() could technically be used to fulfil .append() and
.appendContentsOf(), it’s not actually replacing anything so it isn’t
directly related IMO.

We had ExtensibleCollection before, but we dropped it. The rationale
is that if you can create an empty collection, and can append, then
you can implement replaceRange() with just that. Thus,
ExtensibleCollection and RangeReplaceableCollection are the same type.

Indeed, it’s conceivable that a type might want to declare the ability to
append elements separately from declaring means of removing them arbitrarily
(which is what RangeReplaceableCollectionType does), as they may want
stricter requirements on removal; for example a queue where elements can
only be removed via a removeHead() method or similar.

Then your type is not a RangeReplaceableCollection, it is a Queue, or
something else that we don't have.

Separate removal and insertion:

Another case where RangeReplaceableCollectionType forces potentially
incompatible actions is that it requires both the ability to remove and to
insert arbitrarily into a collection. This is fine if the collection has no
form of sort order, however, if the collection is sorted, then insertion
operations actually make no sense, requiring the type to ignore the provided
indices and just position elements where it decides is best regardless.
Removals from a sorted collection don’t have this issue however (if you
remove a chunk from them then the remaining elements should still be in the
correct order).

Essentially this is a bunch of issues I ran into while attempting to
implement an ordered collection with as many of the same capabilities of an
Array as possible; while I realise that separation will result in two new
CollectionType protocols, I think that it could be beneficial for
flexibility when defining our own custom types.

Could you provide more information about the semantics of your
collection, and supported operations?

Dmitri

···

On Sun, Feb 28, 2016 at 9:47 AM, Haravikk via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Haravikk) #4

So today I’ve been trying to put together an implementation of an ordered
collection, and I noticed that a lot of important mutating methods are
actually grouped together under RangeReplaceableCollectionType, which is
actually kind of weird, and has led me to create some more specialised
protocols of my own as I actually can’t implement
RangeReplaceableCollectionType as it for a number of reasons, which I’ll
discuss here:

Remove initialisers

I’m not actually sure why RangeReplaceableCollectionType has required
initialisers, since it shouldn’t really matter how you create it since you
can reserve capacity separately if you have to, prior to dumping elements
into it. However, having these initialiser requirements actually makes it
impossible to conform to this protocol if you require other data in order to
initialise your type.

If your type absolutely requires non-zero data elements for an
instance to exist, how would it implement removeAll()?

I’m not sure if I’m misunderstanding you, or you’ve misunderstood me, but I’m not talking about requiring one or more elements, I’m talking about requiring other data. For example:

  struct SortedType<Element> {
    init(isOrderedBefore:(Element, Element) -> Bool, initialElements:Element…) { … }
  }

i.e- it can have zero elements, that’s not the issue, but my initialiser *must* have an isOrderedBefore closure in order to be able to sort elements of arbitrary type, which I can’t do if I’m requiring to include an initialiser with no arguments at all.

Unless your meaning is that I should implement removeAll() by returning SortedType(), but I don’t believe that that should be a necessary requirement as it’s a bit of a fudge as a default means of implementing keepCapacity false; for example, if I were using an unsafe pointer then I could just discard the allocated memory and open a new pointer into a new, default-size, memory chunk. Plus keepCapacity is actually non-binding (I don’t actually have to respect it).

For example, my type requires a closure, and I can’t provide a default

closure (since the whole point of it is so I can support elements of any
type). I can’t think of any reason why these initialiser requirements should
be necessary, so hopefully they can just be removed.

Could you provide more information about your type? If the closure is
a crucial part of the value, how do you implement collection equality?

I haven’t done that yet, but testing that the elements are the same should still satisfy it, as they’ll either be sorted into the same order or not. If the collection has one or less elements then I guess it’s not as clear what should be done, but I’d say that at that point the two collections are still equal, regardless of their sort order, i.e- they can’t become unequal until some sorting has occurred.

Separate out the append(), appendContentsOf() and reserveCapacity() methods:

These methods don’t seem to me to be specific to
RangeReplaceableCollectionType, and it seems like they should be separated
into an AppendableCollectionType or ExpandableCollectionType or similar.
While .replaceRange() could technically be used to fulfil .append() and
.appendContentsOf(), it’s not actually replacing anything so it isn’t
directly related IMO.

We had ExtensibleCollection before, but we dropped it. The rationale
is that if you can create an empty collection, and can append, then
you can implement replaceRange() with just that. Thus,
ExtensibleCollection and RangeReplaceableCollection are the same type.

I suppose I didn’t consider that append() implies that the element is always added to the end though, I suppose another add() method that makes no assumptions about where the element ends up would make more sense.

Indeed, it’s conceivable that a type might want to declare the ability to
append elements separately from declaring means of removing them arbitrarily
(which is what RangeReplaceableCollectionType does), as they may want
stricter requirements on removal; for example a queue where elements can
only be removed via a removeHead() method or similar.

Then your type is not a RangeReplaceableCollection, it is a Queue, or
something else that we don't have.

But a RangeReplaceCollection could be used to satisfy its requirements, which is why it seems like at least some part of the protocol should be able to be implemented separately, i.e- it seems like I should be able to implement a pure queue and have it be interchangeable with an Array, but there is currently no protocol that supports this, even though adding and consuming elements of a collection are a fairly common concept that doesn’t necessarily need to be tied together with insertion as well.

Separate removal and insertion:

Another case where RangeReplaceableCollectionType forces potentially
incompatible actions is that it requires both the ability to remove and to
insert arbitrarily into a collection. This is fine if the collection has no
form of sort order, however, if the collection is sorted, then insertion
operations actually make no sense, requiring the type to ignore the provided
indices and just position elements where it decides is best regardless.
Removals from a sorted collection don’t have this issue however (if you
remove a chunk from them then the remaining elements should still be in the
correct order).

Essentially this is a bunch of issues I ran into while attempting to
implement an ordered collection with as many of the same capabilities of an
Array as possible; while I realise that separation will result in two new
CollectionType protocols, I think that it could be beneficial for
flexibility when defining our own custom types.

Could you provide more information about the semantics of your
collection, and supported operations?

At its most basic its a fully conforming CollectionType that requires as an isOrderedBefore closure to sort elements, and can have new elements added to it. Effectively in addition to the CollectionType requires it only really needs an add() operation, but at the same time methods like reserveCapacity(), removeFirst(), removeRange() and removeLast() also make sense, but are currently limited to RangeReplaceableCollectionType.

···

On 29 Feb 2016, at 10:17, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Sun, Feb 28, 2016 at 9:47 AM, Haravikk via swift-evolution > <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Dmitri Gribenko) #5

So today I’ve been trying to put together an implementation of an ordered
collection, and I noticed that a lot of important mutating methods are
actually grouped together under RangeReplaceableCollectionType, which is
actually kind of weird, and has led me to create some more specialised
protocols of my own as I actually can’t implement
RangeReplaceableCollectionType as it for a number of reasons, which I’ll
discuss here:

Remove initialisers

I’m not actually sure why RangeReplaceableCollectionType has required
initialisers, since it shouldn’t really matter how you create it since you
can reserve capacity separately if you have to, prior to dumping elements
into it. However, having these initialiser requirements actually makes it
impossible to conform to this protocol if you require other data in order to
initialise your type.

If your type absolutely requires non-zero data elements for an
instance to exist, how would it implement removeAll()?

I’m not sure if I’m misunderstanding you, or you’ve misunderstood me, but
I’m not talking about requiring one or more elements, I’m talking about
requiring other data. For example:

struct SortedType<Element> {
init(isOrderedBefore:(Element, Element) -> Bool, initialElements:Element…) {
… }
}

i.e- it can have zero elements, that’s not the issue, but my initialiser
*must* have an isOrderedBefore closure in order to be able to sort elements
of arbitrary type, which I can’t do if I’m requiring to include an
initialiser with no arguments at all.

Understood.

Could you provide more information about your type? If the closure is
a crucial part of the value, how do you implement collection equality?

I haven’t done that yet, but testing that the elements are the same should
still satisfy it, as they’ll either be sorted into the same order or not. If
the collection has one or less elements then I guess it’s not as clear what
should be done, but I’d say that at that point the two collections are still
equal, regardless of their sort order, i.e- they can’t become unequal until
some sorting has occurred.

How would you decide equality? You would have two collections, one on
the left, and one on the right, and each of those has a different
concept of equality via the stored 'isOrderedBefore' closure.

Separate out the append(), appendContentsOf() and reserveCapacity() methods:

These methods don’t seem to me to be specific to
RangeReplaceableCollectionType, and it seems like they should be separated
into an AppendableCollectionType or ExpandableCollectionType or similar.
While .replaceRange() could technically be used to fulfil .append() and
.appendContentsOf(), it’s not actually replacing anything so it isn’t
directly related IMO.

We had ExtensibleCollection before, but we dropped it. The rationale
is that if you can create an empty collection, and can append, then
you can implement replaceRange() with just that. Thus,
ExtensibleCollection and RangeReplaceableCollection are the same type.

I suppose I didn’t consider that append() implies that the element is always
added to the end though, I suppose another add() method that makes no
assumptions about where the element ends up would make more sense.

Well, it is a different method then, with different semantics, and
different guarantees :slight_smile:

Indeed, it’s conceivable that a type might want to declare the ability to
append elements separately from declaring means of removing them arbitrarily
(which is what RangeReplaceableCollectionType does), as they may want
stricter requirements on removal; for example a queue where elements can
only be removed via a removeHead() method or similar.

Then your type is not a RangeReplaceableCollection, it is a Queue, or
something else that we don't have.

But a RangeReplaceCollection could be used to satisfy its requirements,

Why? Protocols are not just bags of syntax, they represent classes of
entities with semantics.

which is why it seems like at least some part of the protocol should be able
to be implemented separately, i.e- it seems like I should be able to
implement a pure queue and have it be interchangeable with an Array, but
there is currently no protocol that supports this, even though adding and
consuming elements of a collection are a fairly common concept that doesn’t
necessarily need to be tied together with insertion as well.

I'm not opposed to adding a new protocol. What seems strange to me is
that you are describing various collections that clearly can't
implement RangeReplaceableCollection, and trying to weaken protocol's
guarantees so that they can.

Separate removal and insertion:

Another case where RangeReplaceableCollectionType forces potentially
incompatible actions is that it requires both the ability to remove and to
insert arbitrarily into a collection. This is fine if the collection has no
form of sort order, however, if the collection is sorted, then insertion
operations actually make no sense, requiring the type to ignore the provided
indices and just position elements where it decides is best regardless.
Removals from a sorted collection don’t have this issue however (if you
remove a chunk from them then the remaining elements should still be in the
correct order).

Essentially this is a bunch of issues I ran into while attempting to
implement an ordered collection with as many of the same capabilities of an
Array as possible; while I realise that separation will result in two new
CollectionType protocols, I think that it could be beneficial for
flexibility when defining our own custom types.

Could you provide more information about the semantics of your
collection, and supported operations?

At its most basic its a fully conforming CollectionType that requires as an
isOrderedBefore closure to sort elements, and can have new elements added to
it. Effectively in addition to the CollectionType requires it only really
needs an add() operation, but at the same time methods like
reserveCapacity(), removeFirst(), removeRange() and removeLast() also make
sense, but are currently limited to RangeReplaceableCollectionType.

These methods are not "limited" to RangeReplaceableCollectionType. We
can define a different protocol that suits your collection, we just
need to figure out what your collection does, and what does it
generalize to, what other (non-Array-based) implementations are
possible etc.

What you're describing seems like a priority queue, which is typically
implemented using heaps, which don't maintain all elements sorted. If
you want to always maintain sorted order, you could use an array, or
better, a tree.

We need to figure out which basic operations make sense on such data
structures, what are their semantics and performance guarantees, and
then, what generic algorithms would make sense. (If we can't find a
useful generic algorithm that operates through a protocol, then the
protocol is not useful.)

Dmitri

···

On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution@haravikk.me> wrote:

On 29 Feb 2016, at 10:17, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Sun, Feb 28, 2016 at 9:47 AM, Haravikk via swift-evolution > <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Haravikk) #6

How would you decide equality? You would have two collections, one on
the left, and one on the right, and each of those has a different
concept of equality via the stored 'isOrderedBefore' closure.

To me two collections are equal so long as their contents are the same, and in the same order. In other words the actual closure isn’t necessary to the comparison, though obviously it will affect it, since elements stored in ascending numeric order clearly won’t match the same elements in descending numeric order.

I'm not opposed to adding a new protocol. What seems strange to me is
that you are describing various collections that clearly can't
implement RangeReplaceableCollection, and trying to weaken protocol's
guarantees so that they can.

I’m not trying to weaken its guarantees; the only thing directly affecting RangeReplaceableCollectionType would be removing the initialisers, as I don’t think they’re necessary to implementing that type (though of course I welcome any description as to why they may be necessary).

Otherwise a new protocol is exactly what I’m interested in; you mentioned an ExpandableCollectionType, which I think is a start, though it should probably have add() and addContentsOf() methods rather than appends (this way they place no guarantees on where elements will go, only that they are added). While the add() method would be a synonym of append() for arrays, it would be useful for aligning with Set I think.

Moving the removeRange() and related methods (removeAtIndex etc.) would take them away from RangeReplaceableCollectionType (it should extend whatever new protocol is added), but the idea is to separate the concept of removing things by index, and replacing them/performing insertions.

Basically I’d like to tweak the protocols such that a generic collection can be expanded, and its elements accessed in an order, but that order may be defined by the type itself; to me, inserting a value directly at a specific index is a more specialist type.

···

On 29 Feb 2016, at 11:11, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution@haravikk.me <mailto:swift-evolution@haravikk.me>> wrote:


(Dmitri Gribenko) #7

How would you decide equality? You would have two collections, one on
the left, and one on the right, and each of those has a different
concept of equality via the stored 'isOrderedBefore' closure.

To me two collections are equal so long as their contents are the same, and
in the same order. In other words the actual closure isn’t necessary to the
comparison, though obviously it will affect it, since elements stored in
ascending numeric order clearly won’t match the same elements in descending
numeric order.

I'm not opposed to adding a new protocol. What seems strange to me is
that you are describing various collections that clearly can't
implement RangeReplaceableCollection, and trying to weaken protocol's
guarantees so that they can.

I’m not trying to weaken its guarantees; the only thing directly affecting
RangeReplaceableCollectionType would be removing the initialisers, as I
don’t think they’re necessary to implementing that type (though of course I
welcome any description as to why they may be necessary).

Otherwise a new protocol is exactly what I’m interested in; you mentioned an
ExpandableCollectionType, which I think is a start, though it should
probably have add() and addContentsOf()

Set calls this operation 'insert'.

methods rather than appends (this
way they place no guarantees on where elements will go, only that they are
added). While the add() method would be a synonym of append() for arrays, it
would be useful for aligning with Set I think.

Moving the removeRange() and related methods (removeAtIndex etc.) would take
them away from RangeReplaceableCollectionType (it should extend whatever new
protocol is added), but the idea is to separate the concept of removing
things by index, and replacing them/performing insertions.

Basically I’d like to tweak the protocols such that a generic collection can
be expanded, and its elements accessed in an order, but that order may be
defined by the type itself; to me, inserting a value directly at a specific
index is a more specialist type.

Sound like a plan. Please make sure to design the protocol in such a
way that there are useful generic algorithms that can be written over
such a protocol.

Dmitri

···

On Mon, Feb 29, 2016 at 1:13 PM, Haravikk <swift-evolution@haravikk.me> wrote:

On 29 Feb 2016, at 11:11, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution@haravikk.me> > wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Haravikk) #8

Okay so I’ve been tweaking the protocols that I’m using. For my own use I’ve ended up with two protocols:

ExtendableCollectionType: Which implements .insert() and .insertContentsOf() methods, as well as a non-binding concept of capacity.
RangeRemoveableCollectionType: Which implements most basic removal methods that don’t involve replacing anything (i.e- they don’t include insertions at specific indices). This is therefore safe for self-ordering collections as while insertion can’t support an index (can’t guarantee item will end up where it’s placed), removing them should have no such restrictions that I can see.

This effectively leaves RangeReplaceCollectionType with index based insertions, append (insert at end) and range replacement methods. Other proposed changes include removing the initialisers (since these restrict implementations), and possibly changing the .replaceRange() method to accept a sequence rather than a collection as I don’t believe a collection should be required?

Here’s a quick, simplified, example of how everything would look:

// Extension of a collection by adding new contents
protocol ExtendableCollectionType : CollectionType {
    var capacity:Index.Distance { get }

    mutating func insert(element:Self.Generator.Element)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S)

    mutating func reserveCapacity(minimumCapacity:Bool)
}

extension ExtendableCollectionType {
    var capacity:Index.Distance { return self.count }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S) {
        for element in elements { self.insert(element) }
    }
}

extension ExtendableCollectionType where Self:RangeReplaceableCollectionType {
    mutating func insert(element:Self.Generator.Element) { self.append(element) }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S) { self.appendContentsOf(elements) }
}

// Removal of specific indices
protocol RangeRemoveableCollectionType : ExtendableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool)
    mutating func removeAtIndex(index:Index) -> Self.Generator.Element
    mutating func removeRange(subRange:Range<Index>)
}

extension RangeRemoveableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool) { self.removeRange(self.startIndex ..< self.endIndex) }
    mutating func removeFirst() -> Self.Generator.Element? { … }
    mutating func removeFirst(n:Index.Distance) { self.removeRange(self.startIndex ..< self.startIndex.advancedBy(n)) }
}

extension RangeRemoveableCollectionType where Self.Index:BidirectionalIndexType {
    mutating func removeLast() -> Self.Generator.Element? { … }
    mutating func removeLast(n:Index.Distance) { self.removeRange(self.endIndex.advancedBy(-n) ..< self.endIndex) }
}

// Insertion/replacement at specific indices
protocol RangeReplaceableCollectionType : RangeRemoveableCollectionType {
    mutating func append(element:Self.Generator.Element)
    mutating func appendContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S)
    mutating func insert(element:Self.Generator.Element, atIndex:Index)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element == Self.Generator.Element>(elements:S, atIndex:Index)
    mutating func replaceRange<S:SequenceType where S.Generator.Element == Self.Generator.Element>(subRange:Range<Index>, with elements:S)
}

This is just to give an idea, there may be some accidental omissions and some stuff is simplified or omitted on purpose, but it hopefully shows the separation and structure that I’m aiming for.

I was originally going to put all of the RangeRemovableCollectionType methods into ExtendableCollectionType, however that would mean tying the ability to add and to remove together, which may still be limiting; a collection could for example be designed to be consumed internally, or even to just expire its own contents (e.g- a cache type) so may not wish to externally expose methods that would remove elements.

Also, naming is absolutely up for debate too, all feedback appreciated!

P.S- I know that naming conventions are currently up for debate, so I’m just sticking with the way things are right now for simplicity, obviously everything would be tweaked to match whatever decision is made for whichever version this ends up in =)

···

On 29 Feb 2016, at 21:16, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Feb 29, 2016 at 1:13 PM, Haravikk <swift-evolution@haravikk.me <mailto:swift-evolution@haravikk.me>> wrote:

On 29 Feb 2016, at 11:11, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution@haravikk.me> >> wrote:

How would you decide equality? You would have two collections, one on
the left, and one on the right, and each of those has a different
concept of equality via the stored 'isOrderedBefore' closure.

To me two collections are equal so long as their contents are the same, and
in the same order. In other words the actual closure isn’t necessary to the
comparison, though obviously it will affect it, since elements stored in
ascending numeric order clearly won’t match the same elements in descending
numeric order.

I'm not opposed to adding a new protocol. What seems strange to me is
that you are describing various collections that clearly can't
implement RangeReplaceableCollection, and trying to weaken protocol's
guarantees so that they can.

I’m not trying to weaken its guarantees; the only thing directly affecting
RangeReplaceableCollectionType would be removing the initialisers, as I
don’t think they’re necessary to implementing that type (though of course I
welcome any description as to why they may be necessary).

Otherwise a new protocol is exactly what I’m interested in; you mentioned an
ExpandableCollectionType, which I think is a start, though it should
probably have add() and addContentsOf()

Set calls this operation 'insert'.

methods rather than appends (this
way they place no guarantees on where elements will go, only that they are
added). While the add() method would be a synonym of append() for arrays, it
would be useful for aligning with Set I think.

Moving the removeRange() and related methods (removeAtIndex etc.) would take
them away from RangeReplaceableCollectionType (it should extend whatever new
protocol is added), but the idea is to separate the concept of removing
things by index, and replacing them/performing insertions.

Basically I’d like to tweak the protocols such that a generic collection can
be expanded, and its elements accessed in an order, but that order may be
defined by the type itself; to me, inserting a value directly at a specific
index is a more specialist type.

Sound like a plan. Please make sure to design the protocol in such a
way that there are useful generic algorithms that can be written over
such a protocol.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>>*/


(Dmitri Gribenko) #9

Okay so I’ve been tweaking the protocols that I’m using. For my own use I’ve
ended up with two protocols:

ExtendableCollectionType: Which implements .insert() and .insertContentsOf()
methods, as well as a non-binding concept of capacity.

Hi,

Thank you for preparing these APIs. Could you explain what the
semantics of these new APIs are (in doc comments, for example), and
provide examples of generic algorithms that work on any collection
that implements the desired semantics in the minimal way?

Dmitri

···

On Thu, Mar 3, 2016 at 12:29 PM, Haravikk <swift-evolution@haravikk.me> wrote:

RangeRemoveableCollectionType: Which implements most basic removal methods
that don’t involve replacing anything (i.e- they don’t include insertions at
specific indices). This is therefore safe for self-ordering collections as
while insertion can’t support an index (can’t guarantee item will end up
where it’s placed), removing them should have no such restrictions that I
can see.

This effectively leaves RangeReplaceCollectionType with index based
insertions, append (insert at end) and range replacement methods. Other
proposed changes include removing the initialisers (since these restrict
implementations), and possibly changing the .replaceRange() method to accept
a sequence rather than a collection as I don’t believe a collection should
be required?

Here’s a quick, simplified, example of how everything would look:

// Extension of a collection by adding new contents
protocol ExtendableCollectionType : CollectionType {
    var capacity:Index.Distance { get }

    mutating func insert(element:Self.Generator.Element)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element
== Self.Generator.Element>(elements:S)

    mutating func reserveCapacity(minimumCapacity:Bool)
}

extension ExtendableCollectionType {
    var capacity:Index.Distance { return self.count }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element
== Self.Generator.Element>(elements:S) {
        for element in elements { self.insert(element) }
    }
}

extension ExtendableCollectionType where Self:RangeReplaceableCollectionType
{
    mutating func insert(element:Self.Generator.Element) {
self.append(element) }
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element
== Self.Generator.Element>(elements:S) { self.appendContentsOf(elements) }
}

// Removal of specific indices
protocol RangeRemoveableCollectionType : ExtendableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool)
    mutating func removeAtIndex(index:Index) -> Self.Generator.Element
    mutating func removeRange(subRange:Range<Index>)
}

extension RangeRemoveableCollectionType {
    mutating func removeAll(keepCapacity keepCapacity:Bool) {
self.removeRange(self.startIndex ..< self.endIndex) }
    mutating func removeFirst() -> Self.Generator.Element? { … }
    mutating func removeFirst(n:Index.Distance) {
self.removeRange(self.startIndex ..< self.startIndex.advancedBy(n)) }
}

extension RangeRemoveableCollectionType where
Self.Index:BidirectionalIndexType {
    mutating func removeLast() -> Self.Generator.Element? { … }
    mutating func removeLast(n:Index.Distance) {
self.removeRange(self.endIndex.advancedBy(-n) ..< self.endIndex) }
}

// Insertion/replacement at specific indices
protocol RangeReplaceableCollectionType : RangeRemoveableCollectionType {
    mutating func append(element:Self.Generator.Element)
    mutating func appendContentsOf<S:SequenceType where S.Generator.Element
== Self.Generator.Element>(elements:S)
    mutating func insert(element:Self.Generator.Element, atIndex:Index)
    mutating func insertContentsOf<S:SequenceType where S.Generator.Element
== Self.Generator.Element>(elements:S, atIndex:Index)
    mutating func replaceRange<S:SequenceType where S.Generator.Element ==
Self.Generator.Element>(subRange:Range<Index>, with elements:S)
}

This is just to give an idea, there may be some accidental omissions and
some stuff is simplified or omitted on purpose, but it hopefully shows the
separation and structure that I’m aiming for.

I was originally going to put all of the RangeRemovableCollectionType
methods into ExtendableCollectionType, however that would mean tying the
ability to add and to remove together, which may still be limiting; a
collection could for example be designed to be consumed internally, or even
to just expire its own contents (e.g- a cache type) so may not wish to
externally expose methods that would remove elements.

Also, naming is absolutely up for debate too, all feedback appreciated!

P.S- I know that naming conventions are currently up for debate, so I’m just
sticking with the way things are right now for simplicity, obviously
everything would be tweaked to match whatever decision is made for whichever
version this ends up in =)

On 29 Feb 2016, at 21:16, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Feb 29, 2016 at 1:13 PM, Haravikk <swift-evolution@haravikk.me> > wrote:

On 29 Feb 2016, at 11:11, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution@haravikk.me> > wrote:

How would you decide equality? You would have two collections, one on
the left, and one on the right, and each of those has a different
concept of equality via the stored 'isOrderedBefore' closure.

To me two collections are equal so long as their contents are the same, and
in the same order. In other words the actual closure isn’t necessary to the
comparison, though obviously it will affect it, since elements stored in
ascending numeric order clearly won’t match the same elements in descending
numeric order.

I'm not opposed to adding a new protocol. What seems strange to me is
that you are describing various collections that clearly can't
implement RangeReplaceableCollection, and trying to weaken protocol's
guarantees so that they can.

I’m not trying to weaken its guarantees; the only thing directly affecting
RangeReplaceableCollectionType would be removing the initialisers, as I
don’t think they’re necessary to implementing that type (though of course I
welcome any description as to why they may be necessary).

Otherwise a new protocol is exactly what I’m interested in; you mentioned an
ExpandableCollectionType, which I think is a start, though it should
probably have add() and addContentsOf()

Set calls this operation 'insert'.

methods rather than appends (this
way they place no guarantees on where elements will go, only that they are
added). While the add() method would be a synonym of append() for arrays, it
would be useful for aligning with Set I think.

Moving the removeRange() and related methods (removeAtIndex etc.) would take
them away from RangeReplaceableCollectionType (it should extend whatever new
protocol is added), but the idea is to separate the concept of removing
things by index, and replacing them/performing insertions.

Basically I’d like to tweak the protocols such that a generic collection can
be expanded, and its elements accessed in an order, but that order may be
defined by the type itself; to me, inserting a value directly at a specific
index is a more specialist type.

Sound like a plan. Please make sure to design the protocol in such a
way that there are useful generic algorithms that can be written over
such a protocol.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/