> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu <xiaodi...@gmail.com> wrote:
>>> That ordering can be arbitrary, but it shouldn’t leak internal
>>> representation such that the method used to create identical things affects
>>> the outcome of generic methods because of differences in internal
>>> representation.
>>>
>>>
>>>> It would be better to say that the iteration order is well-defined. That
>>>> will almost always mean documented, and usually predictable though
>>>> obviously e.g. RNGs and iterating in random order will not be predictable
>>>> by design.
>>>>
>>>>> That's actually more semantically constrained than what Swift calls a
>>>>> `Collection` (which requires conforming types to be multi-pass and(?)
>>>>> finite). By contrast, Swift's `SpongeBob` protocol explicitly permits
>>>>> conforming single-pass, infinite, and/or unordered types.
>>>>
>>>> I think you’re talking about Sequence here, I’ve lost track of your
>>>> nonsense by now. Yes, the current Swift protocol named Sequence allows
>>>> unordered types. You seem to keep asserting that but not actually
>>>> addressing my argument, which is that allowing Sequences to be unordered
>>>> with the current API is undesired and actively harmful, and should
>>>> therefore be changed.
>>>>
>>>> What is harmful about it?
>>>
>>> After thinking about it, I think the harmful bit is that unordered
>>> sequences are leaking internal representation (In your example, this is
>>> causing people to be surprised when two sets with identical elements are
>>> generating different sequences/orderings based on how they were created).
>>> You are correct when you say that this problem is even true for for-in.
>>>
>>> I would not say it is a problem. Rather, by definition, iteration involves
>>> retrieving one element after another; if you're allowed to do that with
>>> Set, then the elements of a Set are observably ordered in some way. Since
>>> it's not an OrderedSet--i.e., order doesn't matter--then the only sensible
>>> conclusion is that the order of elements obtained in a for...in loop must
>>> be arbitrary. If you think this is harmful, then you must believe that one
>>> should be prohibited from iterating over an instance of Set. Otherwise, Set
>>> is inescapably a Sequence by the Swift definition of Sequence. All
>>> extension methods on Sequence like drop(while:) are really just
>>> conveniences for common things that you can do with iterated access; to my
>>> mind, they're essentially just alternative ways of spelling various
>>> for...in loops.
>>
>> I think an argument could be made that you shouldn’t be able to iterate over
>> a set without first defining an ordering on it (even if that ordering is
>> somewhat arbitrary). Maybe we have something like a “Sequenc(e)able”
>> protocol which defines things which can be turned into a sequence when
>> combined with some sort of ordering. One possible ordering could be the
>> internal representation (At least in that case we are calling it out
>> specifically). If I had to say
>> “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)” I would definitely
>> be less surprised when it returns false even though setA == setB.
>>
>> Well, that's a totally different direction, then; you're arguing that `Set`
>> and `Dictionary` should not conform to `Sequence` altogether. That's fine
>> (it's also a direction that some of us explored off-list a while ago), but
>> at this point in Swift's evolution, realistically, it's not within the realm
>> of possible changes.
>
> I am actually suggesting something slightly different. Basically, Set and
> Dictionary’s conformance to Collection would have a different implementation.
> They would conform to another protocol declaring that they are unordered.
> That protocol would fill in part of the conformance to sequence/collection
> using a default ordering, which is mostly arbitrary, but guaranteed to
> produce the same ordering for the same list of elements (even across
> collection types). This would be safer, but a tiny bit slower than what we
> have now (We could also potentially develop a way for collections like set to
> amortize the cost). For those who need to recover speed, the new protocol
> would also define a property which quickly returns a sequence/iterator using
> the internal ordering (I arbitrarily called it .arbitraryOrder).
>
> I believe it would not be source breaking.
>
> That is indeed something slightly different.
>
> In an ideal world--and my initial understanding of what you were
> suggesting--Set and Dictionary would each have a member like `collection`,
> which would expose the underlying data as a `SetCollection` or
> `DictionaryCollection` that in turn would conform to `Collection`; meanwhile,
> Set and Dictionary themselves would not offer methods such as `prefix`, or
> indexing by subscript, which are not compatible with being unordered. For
> those who want a particular ordering, there'd be something like
> `collection(ordered areInIncreasingOrder: (T, T) -> Bool) ->
> {Set|Dictionary}Collection`.
>
> What you suggest here instead would be minimally source-breaking. However,
> I'm unsure of where these guarantees provide benefit to justify the
> performance cost. Certainly not for `first` or `dropFirst(_:)`, which still
> yields an arbitrary result which doesn't make sense for something
> _unordered_. We *could* have an underscored customization point named
> something like `_customOrderingPass` that is only invoked from
> `elementsEqual` or other such methods to pre-rearrange the internal ordering
> of unordered collections in some deterministic way before comparison. Is that
> what you have in mind?
Something like that. Whatever we do, there will be a tradeoff between speed,
correctness, and ergonomics.
My suggestion trades speed for correctness, and provides a way to recover speed
through additional typing (which is slightly less ergonomic).
We could do something like you suggest. I don’t think the method would need to
be underscored… the ordering pass could just be a method on the protocol which
defines it as unordered. Then we could provide a special conformance for
things where order really matters based on adherence to that protocol. That
might be an acceptable tradeoff. It would give us speed at the cost of having
the correct implementation being less ergonomic and more error prone (you have
to remember to check that it is unordered and call the ordering method when it
mattered).
I’d still be a bit worried that people would make incorrect generic algorithms
based on expecting an order from unordered things, but at least it would be
possible for them check and handle it correctly. I think I could get behind
that tradeoff/compromise, given where we are in the swift process and Swift's
obsession with speed (though I still slightly prefer the safer default). At
least the standard library would handle all the things correctly, and that is
what will affect the majority of programmers.
Thanks,
Jon
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
