[swift-evolution] Changes to RangeReplaceableCollectionType

[Dmitri Gribenko]

On Mon, Feb 29, 2016 at 2:54 AM, Haravikk <swift-evolution at haravikk.me> wrote:
>
> On 29 Feb 2016, at 10:17, Dmitri Gribenko <gribozavr at gmail.com> wrote:
>
> On Sun, Feb 28, 2016 at 9:47 AM, Haravikk via swift-evolution
> <swift-evolution at 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.
>
>
> 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 :)

> 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

-- 
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 at gmail.com>*/