# Is a set a sequence?

(Tino) #87

https://www.cs.uaf.edu/2009/fall/cs301/lecture/12_09_float_to_int.html

So far, I have seen more valid use cases for bit shifting floats than for asking a `Set` for its order…

#88

I wish it were an opinion, but I’m afraid it’s only a quick rhetorical answer. Oh, well, someone is wrong on the internet. Merry April day to everyone :-)

Note that while the “bit-patterness” of `Int` is accessible directly, it is also accessible for `Float`, although indirectly:

``````let ia = 123
let ib = ia << 1

let fa = Float(1.23)
let fb = Float(bitPattern: fa.bitPattern << 1)
``````

So floating point types have a very restricted and explicit API for treating them as bit patterns (which I think is good!), while non-sequential types (like Set and Dictionary) exposes their API for treating them as sequential types directly among their API for treating them like non-sequential types, which I think is confusing.

Btw, can anyone give a succinct definition of the terms “sequential” and “sequence” in the context of Swift (for use in naming and documentation)?

(cherrywoods) #90

In my current understanding, `Sequence` means `SequentiallyIteratable` (which is long for `Iteratable` in this discussion, I think). The first sentence of `Sequence` documentation also describes it that way.

If something is `SequentiallyIteratable` and usable in a for loop, it really isn‘t much effort to write a `prefix` function based on the for loop iteration. Such a function can actually make sence, if I am processing the elements stored in a `Set` in chunks (as mentioned above) and want to process the first chunk specially before I process the remaining chunks in a for loop iteration.

The biggest problem with `Sequence` therefore seems to be naming to me right now, because some of us seem to understand it not in the semantics it is used. I think `Iteratable` would fit was better.

If Swift should be a language that’s easy to learn and close to natural language, the names of the protocols should not be confusing. Requiring everyone to read the documentation before using a feature is in my opinion not the optimal solution.

Based on this understanding I would eigther prefer seeing `Array` as a special type with a predicable and controlable kind of Iteratable or indeed having a second protocol that expressed that a type is Iteratable with a predictable iteration order. An other typs beside Array that would conform to this protocol was `SortedSet`.

I think that some of Arrays capabilities could be generalized and put into this protocol. This would make the protocol in my opinion a well fitting addition to swifts protocol hierarchy.

(TJ Usiyan) #91

I seem to have failed to make my point clear.

My opinion, here, is “yes, we do get some kind of stable ordering falling out of `Set`'s conformance to Collection. The ‘stable’ ordering is not the point and, actually, not core to satisfying the requirements of `Collection`.”

Let’s look at those requirements. Per the documentation:
A sequence whose elements can be

• traversed multiple times, nondestructively
• accessed by an indexed subscript.

Nowhere here is the order of indices mentioned. An requirement for an index, at strongest, guarantees that you will receive the same item with repeated use of the same index. The ‘weakest’ satisfying condition that I can think of is that you will receive an item in the same ‘position’. This former is what `Set` does and the latter is what `Array` does, in my understanding.

Considering this, `Set` can actually behave as I described and change order whenever you aren’t traversing it and still completely work as intended without affecting the behavior of clients. All the implementer of this `WackySet` would need to do is guarantee that you get the same object back for a given index no matter what changes to order occur and that no changes in order made traversal visit the same member twice.

(Ben Cohen) #93

Hi @Erica_Sadun – discussion of SE-0203 should stay on the review thread. This thread is specifically for whether `Sequence` should be changed/augmented to differentiate between different notionally ordered and unordered iterable things.

There is some discussion of the case for/against eliminating the sequentially-equal method on that thread.

#94

You add water to the mill of another persistent myth about sets that needs debunking: the “unstable set myth”:

Set can […] change order whenever you aren’t traversing it and still completely work as intended without affecting the behavior of clients.

This is not true, and I’ll quote the two relevant part of the documentations of Collection and index(after:) that do imply that sets are forced to have a stable ordering (meaning “defined and stable ordering over multiple passes of the same instance”):

Traversing a Collection

Although a sequence can be consumed as it is traversed, a collection is guaranteed to be multipass: Any element can be repeatedly accessed by saving its index. Moreover, a collection’s indices form a finite range of the positions of the collection’s elements. The fact that all collections are finite guarantees the safety of many sequence operations, such as using the contains(_:) method to test whether a collection includes an element.

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. This example demonstrates that the characters view of a string returns the same characters in the same order whether the view’s indices or the view itself is being iterated.

index(after:)

The successor of an index must be well defined. For an index i into a collection c, calling c.index(after: i) returns the same index every time.

What was missing from your reasoning was just the constraint on `index(after:)`. It’s now on the table.

I hope that after the unordered set myth, the “unstable set myth” is also dead for good. This should clean up this conversation from persistent fallacies that just spread useless FUD.

(Anthony Latsis) #95

I wouldn’t say so. Practically impossible not because the core team is biased, rather, because big ideas tend to be ill-judged and have serious implications, and even if they don’t, they are easy to talk about but very hard to be qualitatively implemented. The current idea simply doesn’t yet have a good enough reason to meet the consequences.

You didn’t, it was me who pointed out that there would be a need to split `Collection` with the `Iterable` approach

That’s likely a delusion you got. Decisions that change something require facts and a good enough reason. That reason right now doesn’t exist. Confusion due to inexperience and the uselessness of some methods in particular cases isn’t a good enough reason for an overhaul of a key hierarchy of the Standard Library and a large source breaking change on the verge of ABI stability.

I am not going to argue about what a sequence is, but I would like to notice this kind of example is irrelevant, because absolutely any type can be considered a sequence of bits. This is similar to comparing a Swift `Sequence` to a infinite sequence in analysis.

First of all, note that `contains` is a valid method for any `Sequence`, not just `Collection`. Also, note that collections don’t have to be ordered, thus what you propose isn’t a modern day `Collection`. The same goes for sequences in general.

A Swift `Set` is a Swift `Sequence` that doesn’t guarantee that a value that is contained at position `n` will remain at that position across repeated access. Do you feel the order? It’s still there in a sense.

And it looks like `Set` is a bit up`Set` with this thread…

(TJ Usiyan) #96

If, for the sake of argument, we decided to implement `WackySet` where startIndex and endIndex were pinned every time we mutated but nothing else… we could still honor every requirement of Collection.

I don’t suggest it and I don’t believe it would be beneficial except to demonstrate the possibility but here is my overview of an implementation.

Index keeps a copy of the set that it is an index of and some sort of collection associating past indexes and values. Calling index(after) uses the stored set and randomly chooses a value to be next. Once decided, it internally documents the order ‘chosen’ for any calls to index(before, if we care. In this way, we are guaranteed that an iteration will only ever visit an item in the set once, we have no guarantees other than the first and last element (pinned to make it less ridiculous sounding but no less ridiculous). We have replayability ‘within’ an iteration without maintaining an order. Every time that you call startIndex, you begin this process anew and thus create a new order. All without breaking behavior from what I can tell.
I actually scrutinized the section of the docs that you quoted and it does almost contradict me. However, if we agree–for just one moment–that an index is semantically tied to an element for Set and not a position, then we don’t violate that passage at all. Iterate through indices in the same order and you are asking for the elements in the same order so you will naturally iterate in the same order.

I am not saying that this is how it does work but that this could work without violation of any rules and… for the most part…without breaking any client code. Its subtle, and you might be able to argue that it is too subtle for many cases and people, but it isn’t a myth from what I can tell.

#97

You miss the bijection between elements and indexes (focus on “its” in “Any element can be repeatedly accessed by saving its index”). You can’t build a valid Collection that exhibits unstable ordering.

“Unstable sets” are a myth.

(Tino) #98

I guess we have a different definition of fact as well ;-):
I remember many proposals (I’m not even speaking of decisions in general…) that have not been backed by facts, and not a single one that had such a foundation.
But that’s no accusation towards those proposals, but rather the assessment that most decisions are based on gut feeling, just because it can be incredible hard to collect pertinent facts.
The good thing with facts is that you can check them: If you remember some proposals that got accepted because of scientific studies, I’m very interested to see the links.

There’s no split necessary (that is a fact that can be proven easily, because none of all the protocols in Swift are essential – believe it or not, arrays can exist without conforming to protocols ;-)
But protocols are fine, so I neither want to get rid of them, nor increase their count up to an excess.

So, instead of `OrderedCollection`, we could use `Collection & Sequence` – or, if you prefer, `Ordered & Collection` (and we could also have `Finite & Sequence`, `Sorted & Collection`, `Finite & Sorted & Collection` and other combinations if those make sense).

(TJ Usiyan) #99

I… didn’t, though. The index stores the mapping. Therefore, storing the index stores the mapping. Use the index to get the object as many times as you want and it should work because the index knows what it was mapped to.

#100

I don’t need to look at any WackySet. I’d rather deduce things.

• Take a collection.
• Take its first element: collection.first
• Bijection between elements and their indexes => the first element has one index, which is startIndex, which refers to the first element.
• index(after:) must return the same index every time => from startIndex, you always get the same indexes and elements of the collection, in a stable iteration order, until you reach the end of the collection.

If you don’t like sets to have a first element:

• Take a set.
• Take any element from the set: E
• Bijection between elements and their indexes => E has one index, which it the index of E.
• index(after:) must return the same index every time => from index of E, you always get the same indexes and elements of the collection, in iteration order, until you reach the end of the collection.
• If the last step didn’t iterate all elements, pick another element, and restart. You are guaranteed, in a finite number of steps, to eventually find the first element in the set, from which you can iterate all elements of the set. In a stable order.

No matter how hard you try to go against sequence and collection axioms: unstable sets are a myth.

(Anthony Latsis) #101

I will not deny, I don’t know for sure. But it’s hard to believe there were accepted proposals without a rationale or a gist explaining the motivation and use cases.

Why scientific studies? They might be required if you want to propose improved compiler type-checking algorithms that require extensive rewriting for instance, but the vast majority of proposals don’t require such lengths. It is sufficient to have an approval of the community and the core team, followed by a gist that proves the changes are useful and worth the complications they imply. This of course includes use cases, motivation and an acceptable draft implementation.

`Ordered`, `Finite`? What are those supposed to mean and contain? What are the full names and what do they inherit?

Yes, everything can exist without protocols. Is that the approach we want in Swift?

`Sequence & Collection` to work as `OrderedCollection` requires moving all order-sensitive APIs for multi-pass sequences to `Sequence`. That isn’t a solution – `Sequence` is meant to be a generalization of sequences. You would get another handful of useless methods o single-pass sequences. Again, we will face the need to split something.

(Tino) #102

All had a rationale, but that’s weaker than a fact – facts usually don’t need nearly as much debate ;-) (although with regard to facts, we live in crazy times… ;-)

Are you familiar with the meaning of `&` for protocols?
When we split `Sequence` from `Collection`, `Sequence & Collection` is the same thing that is now called `Collection`.

`Ordered` and `Sorted` could be a pure markers, and for `Finite`, it would make sense to have some sort of `length` requirement.
All of those could be composed freely, removing the need to have a special protocol for every combination.
That would be somewhat holistic… but alas, as I said: It’s to big; just look at the digressions in this thread, which has a rather humble topic.

(Anthony Latsis) #103

It is unclear to me what facts you are talking about. A rationale can include a lot of facts…I don’t think this is worth discussing anyway

Where would all order-sensitive APIs for multi-pass sequences be after splitting `Sequence` and `Collection`?

(Tino) #104
``````extension Ordered & MultiPass & Iterable
``````

(where else? ;-)
But current Swift does not even allow this convenient spelling

(Anthony Latsis) #105

Exactly. You will have to further declare a `OrderedMultiPass` protocol and provide appropriate functionality, that only applies to sequences that are both ordered and multi-pass.
Then again, if `Ordered` and `MultiPass` aren’t type aliases, you demonstrate splitting. And even more than `OrderedCollection` would require.

`extension A & B` is not convenient at all. You are not only ‘extending an arbitrary type’, this would mean every occurrence of `A & B` will imply extended functionality. That is not the meaning of existentials.

(Tino) #106

I really don’t understand how the last sentence is connected to the rest…

Do you think

``````extension A where Self: B
``````

is more convenient?

(Anthony Latsis) #107

You can’t list requirements in protocol extensions or refine semantics…

That would be extremely source-breaking.