> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu via swift-evolution
> <swift-evolution@swift.org> wrote:
>
>
> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull <jh...@gbis.com
> <mailto:jh...@gbis.com>> wrote:
>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu <xiaodi...@gmail.com
>> <mailto:xiaodi...@gmail.com>> wrote:
>>
>>
>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz <tseit...@icloud.com
>> <mailto:tseit...@icloud.com>> wrote:
>>
>>
>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu <xiaodi...@gmail.com
>> <mailto:xiaodi...@gmail.com>>:
>>
>>>
>>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz <tseit...@icloud.com
>>> <mailto:tseit...@icloud.com>> wrote:
>>>> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution
>>>> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:
>>>>
>>>>
>>>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull <jh...@gbis.com
>>>> <mailto:jh...@gbis.com>> wrote:
>>>>
>>>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu <xiaodi...@gmail.com
>>>>> <mailto:xiaodi...@gmail.com>> wrote:
>>>>>
>>>>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull <jh...@gbis.com
>>>>> <mailto:jh...@gbis.com>> wrote:
>>>>>
>>>>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu <xiaodi...@gmail.com
>>>>>> <mailto: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).
>>>>>
>>>>> You haven't convinced me that this is at all improved in "correctness."
>>>>> It trades one arbitrary iteration order for another on a type that tries
>>>>> to model an unordered collection.
>>>>>
>>>>> 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.
>>>>>
>>>>> What is an example of such an "incorrect" generic algorithm that would be
>>>>> made correct by such a scheme?
>>>>
>>>> To start with, the one you gave as an example at the beginning of this
>>>> discussion: Two sets with identical elements which have different internal
>>>> storage and thus give different orderings as sequences. You yourself have
>>>> argued that the confusion around this is enough of a problem that we need
>>>> to make a source-breaking change (renaming it) to warn people that the
>>>> results of the ‘elementsEqual’ algorithm are undefined for sets and
>>>> dictionaries.
>>>>
>>>> No, I am arguing that the confusion about ‘elementsEqual’ is foremost a
>>>> problem with its name; the result of this operation is not at all
>>>> undefined for two sets but actually clearly defined: it returns true if
>>>> two sets have the same elements in the same iteration order, which is a
>>>> publicly observable behavior of sets (likewise dictionaries).
>>>
>>> But it is a behavior which has absolutely no meaning at all because the
>>> order does not depend on the elements of the set but on the history of how
>>> the set has been reached its current state.
>>> So why should I ever use this method on a set?
>>> What is the use case?
>>>
>>> One example: you can use it to check an instance of Set<Float> to determine
>>> if it has a NaN value. (The “obvious” way of doing it is not guaranteed to
>>> work since NaN != NaN.)
>>
>> How would I do that? I'd rather expect to use a property isNaN on Float to
>> do that.
>>
>> set.elementsEqual(set)
>
> I see why that would work (thanks to Set being a collection vs a sequence),
> but it still feels like a hack. I definitely wouldn’t want to be maintaining
> code with that in it. Especially when compared to something like:
>
> set.contains(where: {$0.isNaN})
>
> The purpose of protocols is to enable useful generic code. You cannot use
> isNaN for code that works on generic Collection, or for that matter, even
> code that works on Set where Element : Numeric.
>
> Much generic code (for example, generic sorting) easily blows up when
> encountering NaN. If you want an algorithm that is robust enough to handle
> (or at least reject) that scenario, then you will need to check for it. It is
> not a “hack” but a very common and accepted way of determining the presence
> of NaN.
That's easy to fix:
public protocol Numeric {
// whatever's there now, plus
var isNaN: Bool {get}
}
public extension Numeric where Self: BinaryInteger {
var isNaN: Bool { return false }
}
- Dave Sweeris
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution