[swift-evolution] Changes to RangeReplaceableCollectionType

[Haravikk]

> 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 <mailto: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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160229/adb83240/attachment.html>