I don't understand the relevance of these strange examples about shifting random bits in memory or that every type should conform to Error, etc. Sequence doesn't contain arbitrary and nonsensical functionality, it contains logical things that you can do given the ability to iterate over a sequence of items. Some of these might not be useful for a particular conforming type, but they do give you the expected answer given the semantics of the protocol. I'm not sure “I can think of a use for this method on all possible conforming types” is a reasonable basis for designing protocol hierarchies.
I've said this before, but there's nothing stupid about asking a Set for its prefix that isn't stupid about iterating over elements of a Set in a for-in loop or using an iterator. If you want an arbitrary n items, or you are processing elements in chunks of n in a way that is indifferent to order, then it's a perfectly fine way to express that.
[Ok, I think now I might have to give up on this part of the discussion ;-)]
I can shift the bits of an Int as easy as I can ask an Array for its prefix.
Technically, an Int is nothing but a sequence (let's just not argue about what a sequence is here ;-) of bits, so shifting is straightforward.
A Float is also nothing but a sequence of bits (and not random it general), which can be shifted in the exact same way as I can shift the bits of Int. Afaik, Float does not have shift operations, although they could be added easily (just as I could add prefix to Iterable).
So, from the low-level standpoint, Int and Float both are just a bunch of zeros and ones.
But the order of the bits in those two number types has a completely different meaning, and so does the order in Set and Array.
I can see the parallel that you are trying to draw, but Set is not to Array as Float is to Int.
Int has an extra job, when it comes down to it. That job is to be a sequence of addressable bits. Historically, the cost of creating a separate type for this was high enough that we simply didn't do it. It was convenient and powerful to directly manipulate the bits of an Int-like thing.
Arguably, Array has a similar double duty (buffer) and that can already be seen in the pieces of API that allow you to address the array as a buffer.
The arrangement of bits in both Int and Float are part of the API in a fairly explicit way. The layout is standard and documented. They are concrete types that have concrete implementations that we are clearly allowed to depend on. This is not the case for the Sequence protocol. You are told, at once, what sequence has (It can be iterated over) and things that can conform (Set, Dictionary, Array). only one of those has stable ordering.
... and this whole discussion is about a stronger definition of sequence that removes conformance from types without stable ordering:
Just like Float is more than a bunch of bits, Sequence should be more than a bunch of objects (and it already pretends that this is the case)
Beware making wrong conclusions based on wrong premises. I don't quite know what you mean by "stable ordering", but Set and Dictionaries are guaranteed defined ordering over multiple passes of the same instance, via their conformance to Collection.
It shouldn't be and it doesn't. There are provided methods that can be more useful when you have a stable ordering, yes, but they don't actually imply a stable ordering.
Not a terribly useful nit to pick in my opinion. Mutation give you a new instance and you have no control over the ordering that you are ever given, beside all of that. If, through some feat of bit mastery, indexes always gave you the corresponding item but the order in which you iterated over the collection literally changed every moment that you were not iterating over the collection, I believe that the promises would be fulfilled.
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)?
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.
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.
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.
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.
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 upSet with this thread..
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.
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.
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).
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.
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.
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.
