16 Replies
Latest reply on Dec 21, 2016 11:02 AM by NotMyName
Level 1 (0 points)

Since a Set is unordered, why does it have the Index associated type, and functions for using or obtaining and index?

• ###### Re: Why does Set have Index
Level 8 (8,445 points)

because Set is a collection, it inherits its index property.

but effectively, as it is unordered, this index does not really make sense, and there is no guarantee what index i will return.

• ###### Re: Why does Set have Index
Level 1 (0 points)

Sound like a flaw in the design of Set then. In theory, where myset is a Set then myset[0] returns some unpredictable value. Worse, it gives a consistent result in one release of the Swift library, but changes in the next release.

• ###### Re: Why does Set have Index
Level 8 (8,445 points)

I would not call it à flaw. Onelust just look precisely at what the index returns. And in fact it does return the nth element in the set, so it works as planned.

It is not because the index is not much useful that it is flawed.

If you need you can use ordered sets.

• ###### Re: Why does Set have Index
Level 1 (0 points)

I don't need order. Indexes mean order, so they confuse the meaning of Set. There aren't addressable positions in a mathematical set, so there shouldn't be in Swift Set. Getting the next element N times should not be guaranteed to return s[N].

• ###### Re: Why does Set have Index
Level 4 (585 points)

>> Indexes mean order

Where did you get that idea? An index is a means of referencing a particular element in a collection. It doesn't need to be a number, never mind a number denoting position in an order.

>> There aren't addressable positions in a mathematical set, so there shouldn't be in Swift Set.

There shouldn't be and there aren't. Have you ever actually tried to use myset[0] where myset is a Set? It won't compile, of course.

>> Getting the next element N times should not be guaranteed to return s[N].

Again, s[N] where s is a Set and N is an Int is meaningless in Swift, so where did you find this guarantee?

• ###### Re: Why does Set have Index
Level 8 (6,050 points)

>> In theory, where myset is a Set then myset[0] returns some unpredictable value.

In what theory?

>>Worse, it gives a consistent result in one release of the Swift library, but changes in the next release.

There's no API contract about the order in which index refer to elements, so why do you care?

It seems highly advantageous to be able to iterate through the elements of a set ("for x in someSet"). For an analogy, consider this scenario: "I have 3 cats, but I can't tell you their names because the set of their names is unordered and so I have no way of listing them."

Or: "Yesterday you told Tommy your cats are called A, B and C, but today you told Jilly your cats are called C, A and B. Which list is correct?"

The point is, we list unordered things all the time.

• ###### Re: Why does Set have Index
Level 1 (0 points)

Subscripts mean order and Set is explicitly unordered. That's that theory. Iterating through the elements I agree is necessary and useful. Being Indexable is confusing ordered responsibilities with unordered. My concern is the implied guarantees new coders may try to depend on.

• ###### Re: Why does Set have Index
Level 8 (6,050 points)

I agree that it's better not to leave opportunities of misunderstanding in the path of new developers. However, as soon as sets are iterable (specificially, able to provide elements in turn with no duplications and no omissions), the "no ordering" ship has sailed.

Set subscripts are not numeric. You can't write "someSet [0]" (although you can write "someSet.first"). It takes a bit of effort to actually treat a Set as a numerically indexable Array.

I think you might get some traction if you argued that there should be no "someSet.first" (etc), while retaining "someSet.startIndex" (etc) for custom iteration purposes. The trouble is, you be arguing against the convenience of using a known (consistent) collection API, and it's hard to see who should win.

• ###### Re: Why does Set have Index
Apple Staff (13,355 points)

Subscripts mean order …

They do?  Dictionaries, like sets, support subscripting but don’t guarantee the order.  Do you find that equally troubling?

Share and Enjoy

Quinn “The Eskimo!”
Apple Developer Relations, Developer Technical Support, Core OS/Hardware
`let myEmail = "eskimo" + "1" + "@apple.com"`

• ###### Re: Why does Set have Index
Level 1 (0 points)

Thanks to eveyrone who's taken the time to answer. I was wrong about the integer indicies. That was my bad assumption; I haven't worked in environments where an index is anything other than an integer. So, an index is nothing more than a "bookmark" to a member of the collection. I've since played around with sets and indices in a playground to try this out.

So if they aren't integers, then where do I get the idea these "bookmarks" have an ordering relative to themselves?

"Traversing a Collection

[...] Moreover, a collection’s indices form a finite range of the positions of the collection’s elements. [...] Iterating over the elements of a collection by their positions yields the same elements in the same order as iterating over that collection using its iterator."

Order of elements comes up once again, here the order is as viewed either through its iterator or indexes. Indices impose order, at least until the iterator changes the order (maybe when a member is added or removed, or the library implementation changes).

The page for SetIndex says it conforms to Comparable: https://developer.apple.com/reference/swift/setindex

So set *indexes* have an order relative to one another, but the set *elements* do not have an order relative to one another. I don't understand the distinction, but that's where I've arrived.

(My apology for the long delay answering. A certain huge cable ISP conglomerate accidentally disconnected me for several days.)

• ###### Re: Why does Set have Index
Level 4 (875 points)

So first principle:  Iteration order over a collection is stable.  Iteration order may change when the collection is mutated.

That's a trivial promise for the collection API to make, especially for immutable data types.

But that trivial promise lets you arrive at the definition of integer indexing:

set[0] is the element found by the initial iterator.

set[n+1] is the result after set[n]

A trivial integer mapping that is the consequence of being able to iterate over the collection in a stable order when it is not being mutated.

Do you want to propose an argument for why set should not have a stable iterator?  Because the existence of the stable iterator is what produces the mapping from integers to set elements.

• ###### Re: Why does Set have Index
Level 1 (0 points)

Where did you read to conclude the first principle? I don't see it yet, setting aside assumptions of implementation. BTW, it's established that SetIndex is not integer.

• ###### Re: Why does Set have Index
Level 4 (875 points)

So your complaint is on the duration of time that the iteration is stable now?  Because the iteration has to be stable (produce the elements in some order, without incorrect repetitions, and not skip any elements) in order to obey the semantics of iteration.  So there is a context in which set[n] must return consistent values (iteration loops), even though there may exist contexts in which calls to set[n] return arbitrary elements of the set.

And whether setIndex is an integer is irrelevant.  Count from 0 to n-1 as the elements are returned.  It's an ordering, and a mapping from integers to the set elements.

Keep in mind that this is all coming from the order that the ieterator produced.  Whether or not the set is inherently ordered doesn't matter, the ieterator has to produce the elements in some order.

• ###### Re: Why does Set have Index
Level 8 (6,050 points)

>> So set *indexes* have an order relative to one another, but the set *elements* do not have an order relative to one another. I don't understand the distinction, but that's where I've arrived.

There is no distinction, but the point is that it doesn't matter whether the elements are ordered relative to each other (either naturally or according to some listing/iteration/index).

The point is that two sets are identical if they contain the same elements regardless of order.

So, the semantics of Set (Swift) and NSSet (Obj-C) are:

1. They're collections of values.

2. They contain no duplicate values, according to the rules of Equatable (Swift) or "isEqual:" (Obj-C).

3. Two sets are equal (Equatable/isEqual:) if they contain the same values regardless of order.

All Swift/Obj-C collections are iterable, and the iteration order is (of course) an ordering of the elements, but the iteration order is unpredictable, except for arrays.

NotMyName might be correct about the stability of iteration order, but I'm not aware of any API contract to that effect (except for arrays). In particular, it seems imprudent to assume that an immutable/unnmutated Swift Set will necessarily be enumerated in the same order in different iterations, or that its elements will necessarily be represented by the same index values in different iterations.

• ###### Re: Why does Set have Index
Level 1 (0 points)

Thanks again. I couldn't find any contract about iteration order consistency for Sets either. I know how Sets behave independent of the presence of the Collection-required order-reliant methods. I still think the presence of order adds confusion. I haven't thought hard about it but perhaps a solution would be to create OrderedCollection which conforms to Collection and adds methods and properties like first, last, distance.

• ###### Re: Why does Set have Index
Level 8 (6,050 points)

A couple of footnotes:

— When the NSFastEnumeration protocol was added to Obj-C  a few years ago (to support the "for … in" construct), NSIndexSet didn't support it.To iterate through the values in the set, you had to use a much uglier traditional "for …; …; …;" loop. It was a huge relief when conformance was added. My point is that the convenience having iterable access for the collection far outweighs any perceived inconsistency of semantics.

An alternative way of saying this is that Set/NSSet don't implement mathematical sets. Instead, they are "standard" Swift/Obj-C collections that are merely inspired by mathematical sets.

— In Cocoa there is also NSOrderedSet, where the iteration order is the natural order of the elements. The price you pay, though, is that it's much more expensive in performance than either NSArray or NSSet. I don't think this has been ported to Swift.