Add protocols for unordered collections (and 'sequences')

(Dante Broggi) #1

There exist Collection like types that have no inherent order, yet still want to be able to use functions generic over Collection or Sequence.
Even the standard library has two, namely Set and Dictionary. On such types first and even index(after: ) fail to have the semantics Collection should guarantee, namely that equal collections - as Equatable is the standard guarantee of substitutability - should have substitutable nth elements. e.g:
[“a”:1, “b”:2, “c”:3, “d”:4] == [“c”:3, “a”:1, “d”:4, “b”:2]
but swap their 2nd elements, and we have:
[“a”:1, “c”:3, “d”:4] != [“c”:3, “b”:1, “d”:4]

Thus, I propose we add:

  • Iterable an explicitly unordered ‘for-in’-able from which Sequence will inherit.
  • UnorderedCollection to which Collection's order-agnostic requirements will be extracted (including finiteness).
  • MutableUnorderedCollection which will be the same for MutableCollection.

Here is a SE branch which contains everything I have put together for this.
(I started around when transitioning to the forum, and waited for it to put it forward)

[Pitch] Remove the single-pass requirement on Sequence
Is a set a sequence?
(Saagar Jha) #2

equal collections - as Equatable is the standard guarantee of substitutability - should have substitutable nth elements

I’m sorry, but where is this specified? As far as I know, it’s not Collection that has an equality operator, but rather each individual Collection provides their own. For Collections with a defined ordering this definition makes sense, but as you mentioned it doesn’t apply to those who don’t, such as Set or Dictionary.

(Xiaodi Wu) #3

This is not the first time that this suggestion has been put forward. Now that the archives are easily searchable, I’d recommend a review and summarization of previous conversation first so that we don’t expend a considerable amount of time rehashing the same topic.

If I recall correctly, the bottom line is that Swift’s protocol hierarchies attempt to make useful algorithms possible, and in the course of doing so, actively tries to balance the desire for perfectly granular modeling against the difficulties of having too many protocols. You’ll see in previous conversations that the imperfect fit of ordering-sensitive methods for unordered collections has not escaped the attention of API designers, but that the present design is seen as reflecting the best balance of trade-offs.

My suggestion to people who want to tackle this area, therefore, is to be clear-minded about whether any proposed changes are sensitive to the delicate balancing task and to share your thinking on the detailed pros and cons rather than only enumerating a list of changes.

Is a set a sequence?
(Dante Broggi) #4

It isn’t, I was merely saying that what Is said implies that they should be.

(Xiaodi Wu) #5

A reply from some core team members to a previous thread about this topic explained very clearly that custom Equatable on any type, in Swift and in every other language that permits it, has always meant that == may consider some (call them ‘salient’) attributes of the value but not all. Perhaps the documentation should make it clearer that this is the case.

(Saagar Jha) #6

Yes, that’s what I’m getting at. While it may seem like equality must be defined this way, it’s left ambiguous on purpose so that it “does what it’s supposed to” on all Collections. It may be useful to explicitly address this misconception in the documentation, but other than that I don’t see any immediate solution this issue.