Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 19.10.2017 um 22:49 schrieb Adam Kemp :
> 
>> 
>> On Oct 18, 2017, at 9:58 PM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>> In your earlier emails you wrote
>> 
>> "To make it concrete, say you write a function that just wraps map:
>> func firstNames(ofPeople people: Sequence) -> Sequence { 
>> return people.map { $0.firstName } } 
>>  I want that function to work on both ordered and unordered Sequences, and 
>> if you start with an ordered Sequence you should end up with an ordered 
>> Sequence. How do I make that work?"
>> Your example _won't work even today_ as `map` _returns an Array_ and _not_ a 
>> Sequence, like I have written several times now including in the very email 
>> you have been answering.
> 
> I guess it wouldn’t work exactly as written because Sequence isn’t generic 
> (why? I don’t know…)
> 
> Something like this is closer to what I was trying to describe:
> 
> func firstNames(ofPeople people:SeqPerson) -> AnySequence 
> where SeqPerson : Sequence, SeqPerson.Element : Person {
> return AnySequence(people.map { $0.firstName })
> }
> 
> (I shudder at how unnecessarily complex that is compared to .Net. I hope this 
> can be improved in the future, or that I am missing something that would make 
> it much simpler)
> 
> Since an array is a Sequence the (fixed) code above will work today with 
> either an Array or Set or any other Sequence of Person objects, and its 
> result can be fed into any function that takes in a Sequence of String.
> 
>> So you would just write the method with the most general argument type which 
>> is required by the method:
>> 
>> func firstNames(ofPeople people: Iterable) -> [String] {
>> return people.map { $0.firstName }
>> }
>> 
>> The return type would still be Array _just like today_.
> 
> Let me be clearer: I want my method firstNames(ofPeople:) to work on sets 
> just as it would work on any other Sequence. This method doesn’t care what 
> order things are in, but it also doesn’t alter the order so it is suitable 
> for use with both ordered and unordered inputs. Today I can write that 
> method, and it will work for a set or an array or anything else that conforms 
> to Sequence of Person, and it can then be chained with any other method that 
> operates on a Sequence of Person.
> 
> In order for your proposal to actually be effective you would need to change 
> map so that it doesn’t always give an ordered result. That means you would 
> have to make it not always return an array. The reason for that is that if 
> you left map alone then you could end up writing code like this:
> 
> var people:Set // comes from elsewhere
> var names:[String] // comes from elsewhere
> if (people.map { $0.firstName }.elementsEqual(names)) { // using the current 
> name
> // …
> }

I agree that `map` returning an Array is not a good solution (this applies for 
the current state as well) and it would make it decidedly too easy to move from 
unordered to ordered collections. So, you have a point there. Fixing this is 
still desirable even if not differentiating between unordered and ordered 
collections, though. This does require features which are currently planned 
like recursive protocol constraints on associated types (SR-1445, work on the 
implementation is already happening) and probably other features from the 
Generics Manifesto (which are highly desirable by themselves). 

-Thorsten


 
> 
> Notice how you start with an unordered input, but then map gives you an 
> array, which is ordered. Obviously map is useful to apply to sets so it would 
> have to continue accepting whatever protocol Set conforms to. If it still 
> returned Array regardless of the input type then it would convert an 
> unordered input into an ordered output, and that loses all of the benefits 
> you’re hoping to gain by having two types.
> 
> So clearly you would need map to not return Array when given an unordered 
> input. It’s important that you understand this. Without changing the return 
> type of map and other similar functions you have a huge hole in the type 
> system that loses most of the benefits you’re going for. You may as well not 
> do the feature if you’re not going to change this.
> 
> However, you also can’t just make map always return an unordered output type 
> because then if you started with an ordered input you would get an unordered 
> output, and that doesn’t make sense. That would be really tedious. So now you 
> need two implementations of map: one that takes an unordered input and gives 
> an unordered output, and another that takes an ordered input and returns an 
> ordered output.
> 
> Kevin was suggesting that you could make this easier to deal with by 
> introducing a new language feature, but it’s not clear exactly how that would 
> work, and I’m not convinced it would actually solve the problem I’ve 
> described.
> 
> This is what I mean when I said 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 18, 2017, at 9:58 PM, Thorsten Seitz via swift-evolution 
>  wrote:
> 
> In your earlier emails you wrote
> 
> "To make it concrete, say you write a function that just wraps map:
> func firstNames(ofPeople people: Sequence) -> Sequence { 
> return people.map { $0.firstName } } 
>  I want that function to work on both ordered and unordered Sequences, and if 
> you start with an ordered Sequence you should end up with an ordered 
> Sequence. How do I make that work?"
> Your example _won't work even today_ as `map` _returns an Array_ and _not_ a 
> Sequence, like I have written several times now including in the very email 
> you have been answering.

I guess it wouldn’t work exactly as written because Sequence isn’t generic 
(why? I don’t know…)

Something like this is closer to what I was trying to describe:

func firstNames(ofPeople people:SeqPerson) -> AnySequence 
where SeqPerson : Sequence, SeqPerson.Element : Person {
return AnySequence(people.map { $0.firstName })
}

(I shudder at how unnecessarily complex that is compared to .Net. I hope this 
can be improved in the future, or that I am missing something that would make 
it much simpler)

Since an array is a Sequence the (fixed) code above will work today with either 
an Array or Set or any other Sequence of Person objects, and its result can be 
fed into any function that takes in a Sequence of String.

> So you would just write the method with the most general argument type which 
> is required by the method:
> 
> func firstNames(ofPeople people: Iterable) -> [String] {
> return people.map { $0.firstName }
> }
> 
> The return type would still be Array _just like today_.

Let me be clearer: I want my method firstNames(ofPeople:) to work on sets just 
as it would work on any other Sequence. This method doesn’t care what order 
things are in, but it also doesn’t alter the order so it is suitable for use 
with both ordered and unordered inputs. Today I can write that method, and it 
will work for a set or an array or anything else that conforms to Sequence of 
Person, and it can then be chained with any other method that operates on a 
Sequence of Person.

In order for your proposal to actually be effective you would need to change 
map so that it doesn’t always give an ordered result. That means you would have 
to make it not always return an array. The reason for that is that if you left 
map alone then you could end up writing code like this:

var people:Set // comes from elsewhere
var names:[String] // comes from elsewhere
if (people.map { $0.firstName }.elementsEqual(names)) { // using the current 
name
// …
}

Notice how you start with an unordered input, but then map gives you an array, 
which is ordered. Obviously map is useful to apply to sets so it would have to 
continue accepting whatever protocol Set conforms to. If it still returned 
Array regardless of the input type then it would convert an unordered input 
into an ordered output, and that loses all of the benefits you’re hoping to 
gain by having two types.

So clearly you would need map to not return Array when given an unordered 
input. It’s important that you understand this. Without changing the return 
type of map and other similar functions you have a huge hole in the type system 
that loses most of the benefits you’re going for. You may as well not do the 
feature if you’re not going to change this.

However, you also can’t just make map always return an unordered output type 
because then if you started with an ordered input you would get an unordered 
output, and that doesn’t make sense. That would be really tedious. So now you 
need two implementations of map: one that takes an unordered input and gives an 
unordered output, and another that takes an ordered input and returns an 
ordered output.

Kevin was suggesting that you could make this easier to deal with by 
introducing a new language feature, but it’s not clear exactly how that would 
work, and I’m not convinced it would actually solve the problem I’ve described.

This is what I mean when I said people weren’t thinking this all the way 
through. When you start to actually write out some code and thinking about how 
that code would work with the proposed split then things start to get a lot 
more complicated. It’s not just a matter of this one function. You have to 
think about which types other functions will take and produce, and you have to 
both avoid losing that new type information as well as avoid making simple code 
patterns much harder. I haven’t seen any clear explanation for how all of that 
can be satisfied.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

Oh, this is weird... I replied to a different thread an hour ago. Somehow that 
message hasn't posted yet, but this one from three days ago apparently got 
reposted? Weird.
> On Oct 19, 2017, at 12:11 PM, David Sweeris via swift-evolution 
>  wrote:
> 
> 
> On Oct 16, 2017, at 10:42, BJ Homer via swift-evolution 
> > wrote:
> 
>>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>>> > wrote:
>>> 
 Am 16.10.2017 um 07:19 schrieb Xiaodi Wu >:
>>> 
 What useful generic algorithms would this protocol support that are not 
 already possible?
>>> 
>>> It would allow expressing generic algorithms depending on an order.
>>> 
>>> -Thorsten
>> 
>> We can already express generic algorithms that depend on an order—any 
>> generic algorithm that works on a Sequence works on something that is 
>> ordered. A Swift Set has an undefined order right now, but a generic 
>> algorithm working on any arbitrary Sequence likely doesn’t care about what 
>> the order, just that an order exists. And a Swift Set does indeed have an 
>> order. If you have a generic algorithm that only works on inputs sorted in a 
>> particular manner, then you’ve likely either documented that or added a 
>> “sortedBy” parameter. Otherwise, you probably just want to be able to 
>> iterate through everything.
>> 
>> Let’s assume, though, that you wanted to write an algorithm that works only 
>> on MeaningfullyOrdered inputs. 
>> 
>> func extractInfo(_ input: T) { }
>> extractInfo(someArray)
>> 
>> What stops the caller from simply wrapping the Set in an Array?
>> 
>> extractInfo(Array(someSet))
>> 
>> The Array constructed here is going to reflect the arbitrary ordering 
>> provided by Set, but as far as the type system is concerned, the input is an 
>> Array, which is certainly meaningfully-ordered. Have we gained anything by 
>> requiring the caller to wrap the input in an array? We’ve made the call site 
>> a bit more awkward, and we’ve lost a bit of performance. We certainly need 
>> to be able to convert Sets in to Arrays; to eliminate that would be 
>> massively source-breaking, and it’s not clear that allowing that conversion 
>> is actively harmful, so it’s unlikely to change in Swift 5.
> 
> Should/could we just rename `Set` to `UniquedArray` or something like that? 
> This is starting to feel a bit like the access control debate.
> 
> - Dave Sweeris
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 16, 2017, at 10:42, BJ Homer via swift-evolution 
>  wrote:
> 
>>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>>>  wrote:
>>> 
>>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu :
>> 
>>> What useful generic algorithms would this protocol support that are not 
>>> already possible?
>> 
>> It would allow expressing generic algorithms depending on an order.
>> 
>> -Thorsten
> 
> We can already express generic algorithms that depend on an order—any generic 
> algorithm that works on a Sequence works on something that is ordered. A 
> Swift Set has an undefined order right now, but a generic algorithm working 
> on any arbitrary Sequence likely doesn’t care about what the order, just that 
> an order exists. And a Swift Set does indeed have an order. If you have a 
> generic algorithm that only works on inputs sorted in a particular manner, 
> then you’ve likely either documented that or added a “sortedBy” parameter. 
> Otherwise, you probably just want to be able to iterate through everything.
> 
> Let’s assume, though, that you wanted to write an algorithm that works only 
> on MeaningfullyOrdered inputs. 
> 
> func extractInfo(_ input: T) { }
> extractInfo(someArray)
> 
> What stops the caller from simply wrapping the Set in an Array?
> 
> extractInfo(Array(someSet))
> 
> The Array constructed here is going to reflect the arbitrary ordering 
> provided by Set, but as far as the type system is concerned, the input is an 
> Array, which is certainly meaningfully-ordered. Have we gained anything by 
> requiring the caller to wrap the input in an array? We’ve made the call site 
> a bit more awkward, and we’ve lost a bit of performance. We certainly need to 
> be able to convert Sets in to Arrays; to eliminate that would be massively 
> source-breaking, and it’s not clear that allowing that conversion is actively 
> harmful, so it’s unlikely to change in Swift 5.

Should/could we just rename `Set` to `UniquedArray` or something like that? 
This is starting to feel a bit like the access control debate.

- Dave Sweeris___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

In your earlier emails you wrote

"To make it concrete, say you write a function that just wraps map:
func firstNames(ofPeople people: Sequence) -> Sequence { return 
people.map { $0.firstName } } 
 I want that function to work on both ordered and unordered Sequences, and if 
you start with an ordered Sequence you should end up with an ordered Sequence. 
How do I make that work?"
Your example _won't work even today_ as `map` _returns an Array_ and _not_ a 
Sequence, like I have written several times now including in the very email you 
have been answering.
So you would just write the method with the most general argument type which is 
required by the method:

func firstNames(ofPeople people: Iterable) -> [String] {
return people.map { $0.firstName }
}

The return type would still be Array _just like today_.

-Thorsten


> Am 19.10.2017 um 01:30 schrieb Adam Kemp :
> 
> Please re-read my earlier emails with concrete examples of problems this 
> split would cause:
> 
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171016/040501.html
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171016/040540.html
> 
> You’re not thinking far enough ahead about the consequences of this change. 
> It’s not just about map, and it’s not even just about the functions that 
> already exist today. It’s about all of the future functions that you and I 
> and every other Swift developer is going to write dealing with Sequences. 
> Think about the impact on those functions.
> 
> I’ve written many functions in C# that fit this pattern, and if C# had split 
> IEnumerable in the same way you propose then my job would have been much 
> harder.
> 
>>> On Oct 18, 2017, at 4:14 PM, Thorsten Seitz  wrote:
>>> 
>>> 
 Am 18.10.2017 um 22:04 schrieb Adam Kemp :
 
 
 On Oct 18, 2017, at 12:25 PM, Thorsten Seitz via swift-evolution 
  wrote:
 
 Therefore having `elementsEqual` as API for unordered collections is a 
 source of bugs …
>>> 
>>> You keep saying that, and yet after repeated requests to provide evidence 
>>> you still have not backed up this claim. How many bugs are caused by this? 
>>> Hypotheticals are not evidence. Show us how much of a problem this is in 
>>> the real world. Why do you think this is so important to fix? What impact 
>>> is it going to have? If it weren’t for this thread would you even know the 
>>> problem existed?
>>> 
 Adam expressed the concern that this required `map` to implemented 
 separately for the split APIs: `Iterable.map` would have to return an 
 `Iterable` whereas `Sequence.map` would have to return a `Sequence`. 
 This is an independent issue IMO, because currently we have a similar 
 situation: `Collection.map` does not return a `Collection` either. It 
 returns an Array. This is a compromise partly due to missing language 
 features which can simply remain when `Sequence` is split.
>>> 
>>> That description does not come close to showing the magnitude of the 
>>> problem with this approach. The reason you think it’s not a significant 
>>> problem is that you’re only looking at a single function (map). This 
>>> problem isn’t specific to just one function, though. The problem is that 
>>> every single function that takes in one Sequence and returns another 
>>> Sequence would have to handle this distinction, including functions that 
>>> you and I will want to write and reuse. That means either:
>>> 
>>> 1. Implement the function twice to handle either ordered or unordered.
>>> 2. Only handle one type.
>>> 3. Implement a complex new language feature that makes #1 slightly easier, 
>>> but still harder than it is today.
>>> 
>>> That’s not an improvement. It’s a huge regression in usability. To make 
>>> that kind of change should require a much stronger argument than 
>>> “hypothetically this could lead to bugs”.
>> 
>> Is it really such a huge regression? You already have to decide whether to 
>> use `Sequence` or `Collection` or `BiDirectionalCollection` etc. Or maybe 
>> just `Array` or `Set` or `Dictionary`.
>> 
>> Most such functions (like map, flatMap, filter) currently return `Array`. 
>> These will not be better or worse than before.
>> 
>> For example, `dictionary.map(f)` will result in an `Array` instead of a 
>> `Dictionary` where just the values have been replaced. You see, the problem 
>> already exists.
>> 
>> For functions that do not change the element type we can use existing 
>> language features like associated types as it is already done with 
>> `SubSequence`.
>> 
>> -Thorsten
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 19.10.2017 um 01:13 schrieb Adam Kemp :
> 
> 
>> On Oct 18, 2017, at 3:38 PM, Thorsten Seitz > > wrote:
>> 
>> Now this is not production code (hopefully) but it demonstrates the problem.
> 
> A single StackOverflow post is not convincing evidence of a problem that 
> leads to many real-world bugs. No one here would dispute that people can get 
> confused. That’s why there’s a proposal in the first place. The proposal 
> would have prevented this example merely by making the name clearer.
> 
> This is at best evidence that a name change is needed. It’s not evidence that 
> we should make large changes to the library and language.
> 
>> How will I know if the code behind a generic function taking a Sequence as 
>> argument will internally use `elementsEqual` so that I cannot use a Set as 
>> argument? 
> 
> More generally, how would you know if someone wrote a function that takes an 
> unordered sequence and then writes an algorithm that relies on the order 
> anyway? Splitting the Sequence protocol can’t guarantee you won’t have those 
> kind of bugs. If the semantics of the function are not clear then that’s a 
> naming problem or a library design problem. That’s why the proposal is to fix 
> the name so that it’s clear what it actually does.


I agree, it is a naming problem or a library design problem. That’s why I 
propose to have different names for both notions (unordered and ordered), so 
that it’s clear what the contract of the whole type is (and not just that of a 
single method).

-Thorsten___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

Please re-read my earlier emails with concrete examples of problems this split 
would cause:

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171016/040501.html
 

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171016/040540.html
 


You’re not thinking far enough ahead about the consequences of this change. 
It’s not just about map, and it’s not even just about the functions that 
already exist today. It’s about all of the future functions that you and I and 
every other Swift developer is going to write dealing with Sequences. Think 
about the impact on those functions.

I’ve written many functions in C# that fit this pattern, and if C# had split 
IEnumerable in the same way you propose then my job would have been much harder.

> On Oct 18, 2017, at 4:14 PM, Thorsten Seitz  wrote:
> 
>> 
>> Am 18.10.2017 um 22:04 schrieb Adam Kemp :
>> 
>> 
>>> On Oct 18, 2017, at 12:25 PM, Thorsten Seitz via swift-evolution 
>>>  wrote:
>>> 
>>> Therefore having `elementsEqual` as API for unordered collections is a 
>>> source of bugs …
>> 
>> You keep saying that, and yet after repeated requests to provide evidence 
>> you still have not backed up this claim. How many bugs are caused by this? 
>> Hypotheticals are not evidence. Show us how much of a problem this is in the 
>> real world. Why do you think this is so important to fix? What impact is it 
>> going to have? If it weren’t for this thread would you even know the problem 
>> existed?
>> 
>>> Adam expressed the concern that this required `map` to implemented 
>>> separately for the split APIs: `Iterable.map` would have to return an 
>>> `Iterable` whereas `Sequence.map` would have to return a `Sequence`. 
>>> This is an independent issue IMO, because currently we have a similar 
>>> situation: `Collection.map` does not return a `Collection` either. It 
>>> returns an Array. This is a compromise partly due to missing language 
>>> features which can simply remain when `Sequence` is split.
>> 
>> That description does not come close to showing the magnitude of the problem 
>> with this approach. The reason you think it’s not a significant problem is 
>> that you’re only looking at a single function (map). This problem isn’t 
>> specific to just one function, though. The problem is that every single 
>> function that takes in one Sequence and returns another Sequence would have 
>> to handle this distinction, including functions that you and I will want to 
>> write and reuse. That means either:
>> 
>> 1. Implement the function twice to handle either ordered or unordered.
>> 2. Only handle one type.
>> 3. Implement a complex new language feature that makes #1 slightly easier, 
>> but still harder than it is today.
>> 
>> That’s not an improvement. It’s a huge regression in usability. To make that 
>> kind of change should require a much stronger argument than “hypothetically 
>> this could lead to bugs”.
> 
> Is it really such a huge regression? You already have to decide whether to 
> use `Sequence` or `Collection` or `BiDirectionalCollection` etc. Or maybe 
> just `Array` or `Set` or `Dictionary`.
> 
> Most such functions (like map, flatMap, filter) currently return `Array`. 
> These will not be better or worse than before.
> 
> For example, `dictionary.map(f)` will result in an `Array` instead of a 
> `Dictionary` where just the values have been replaced. You see, the problem 
> already exists.
> 
> For functions that do not change the element type we can use existing 
> language features like associated types as it is already done with 
> `SubSequence`.
> 
> -Thorsten

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 18.10.2017 um 22:04 schrieb Adam Kemp :
> 
> 
>> On Oct 18, 2017, at 12:25 PM, Thorsten Seitz via swift-evolution 
>>  wrote:
>> 
>> Therefore having `elementsEqual` as API for unordered collections is a 
>> source of bugs …
> 
> You keep saying that, and yet after repeated requests to provide evidence you 
> still have not backed up this claim. How many bugs are caused by this? 
> Hypotheticals are not evidence. Show us how much of a problem this is in the 
> real world. Why do you think this is so important to fix? What impact is it 
> going to have? If it weren’t for this thread would you even know the problem 
> existed?
> 
>> Adam expressed the concern that this required `map` to implemented 
>> separately for the split APIs: `Iterable.map` would have to return an 
>> `Iterable` whereas `Sequence.map` would have to return a `Sequence`. 
>> This is an independent issue IMO, because currently we have a similar 
>> situation: `Collection.map` does not return a `Collection` either. It 
>> returns an Array. This is a compromise partly due to missing language 
>> features which can simply remain when `Sequence` is split.
> 
> That description does not come close to showing the magnitude of the problem 
> with this approach. The reason you think it’s not a significant problem is 
> that you’re only looking at a single function (map). This problem isn’t 
> specific to just one function, though. The problem is that every single 
> function that takes in one Sequence and returns another Sequence would have 
> to handle this distinction, including functions that you and I will want to 
> write and reuse. That means either:
> 
> 1. Implement the function twice to handle either ordered or unordered.
> 2. Only handle one type.
> 3. Implement a complex new language feature that makes #1 slightly easier, 
> but still harder than it is today.
> 
> That’s not an improvement. It’s a huge regression in usability. To make that 
> kind of change should require a much stronger argument than “hypothetically 
> this could lead to bugs”.

Is it really such a huge regression? You already have to decide whether to use 
`Sequence` or `Collection` or `BiDirectionalCollection` etc. Or maybe just 
`Array` or `Set` or `Dictionary`.

Most such functions (like map, flatMap, filter) currently return `Array`. These 
will not be better or worse than before.

For example, `dictionary.map(f)` will result in an `Array` instead of a 
`Dictionary` where just the values have been replaced. You see, the problem 
already exists.

For functions that do not change the element type we can use existing language 
features like associated types as it is already done with `SubSequence`.

-Thorsten

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 18, 2017, at 3:38 PM, Thorsten Seitz  wrote:
> 
> Now this is not production code (hopefully) but it demonstrates the problem.

A single StackOverflow post is not convincing evidence of a problem that leads 
to many real-world bugs. No one here would dispute that people can get 
confused. That’s why there’s a proposal in the first place. The proposal would 
have prevented this example merely by making the name clearer.

This is at best evidence that a name change is needed. It’s not evidence that 
we should make large changes to the library and language.

> How will I know if the code behind a generic function taking a Sequence as 
> argument will internally use `elementsEqual` so that I cannot use a Set as 
> argument? 

More generally, how would you know if someone wrote a function that takes an 
unordered sequence and then writes an algorithm that relies on the order 
anyway? Splitting the Sequence protocol can’t guarantee you won’t have those 
kind of bugs. If the semantics of the function are not clear then that’s a 
naming problem or a library design problem. That’s why the proposal is to fix 
the name so that it’s clear what it actually does.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 18.10.2017 um 22:36 schrieb Michael Ilseman :
>> To get back to the topic at hand: I propose to differentiate between 
>> unordered and ordered collections because I think that this is an important 
>> distinction with tractable impact on algorithms (as shown above). The method 
>> `elementsEqual` would be part of the ordered sequence protocol and I would 
>> suggest the name `elementsPairwiseEqual`.
>> 
> 
> You are free to propose that and justify its cost. You'll probably want to 
> plan on how you’ll present the cost/benefit analysis for the feedback of “why 
> not just slap a warning on Set/Dictionary?”

The warning will have to be slapped on `Sequence` because I and others can 
write types adopting Sequence but being unordered.

And it will have to be slapped on every public generic function written by 
anyone which takes a Sequence as argument and internally uses `elementsEqual` 
on that argument, so that the user of such an API knows that he cannot use that 
function with a Set or another unordered subtype of Sequence.

-Thorsten

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 18.10.2017 um 22:31 schrieb Adam Kemp :
> 
> 
>> On Oct 18, 2017, at 1:20 PM, David Sweeris > > wrote:
>> 
>> How many bugs have been caused by floating point types violating the 
>> programmer's mental model of how numbers work? To me, their both in the same 
>> category... both involve specific types that claim to adhere to a certain 
>> behavior, and both don't in sometimes subtle ways.
> 
> I think we have plenty of evidence that misunderstandings about floating 
> point lead to bugs. For example: 
> https://www.theinquirer.net/inquirer/news/1047844/floating-point-bugs-explode 
> 
> 
> It took me about 30 seconds to find a clear example for floating point, and 
> we all know there are many many more.
> 
> Can anyone find even a single example of this function leading to a shipping 
> bug in the real world?

Well, it took me not much longer to find a clear example of a bug in a 
suggested usage of `elementsEqual` on Stackoverflow:

"And, finally, if the two arrays of permissions are actually sets of 
permissions then you can use
return Set(tokenPermissions).elementsEqual(Set(permissions))
"
(https://stackoverflow.com/questions/33354709/swift-compare-set)


Clearly the example will given random results depending on the order of 
`tokenPermissions` and `permissions` which is obviously *not* what the author 
had in mind.

Now this is not production code (hopefully) but it demonstrates the problem.

How will I know if the code behind a generic function taking a Sequence as 
argument will internally use `elementsEqual` so that I cannot use a Set as 
argument? 

-Thorsten

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 18.10.2017 um 22:36 schrieb Michael Ilseman :
> 
> 
> 
>> On Oct 18, 2017, at 12:24 PM, Thorsten Seitz > > wrote:
>> 
>>> 
>>> Am 17.10.2017 um 20:47 schrieb Michael Ilseman via swift-evolution 
>>> >:
>>> 
>>> 
>>> 
 On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
 > wrote:
 
> Because, in my analysis, the problem is that the method is incorrectly 
> named. The problem affects all types that conform to Sequence and not 
> just Set and Dictionary; elementsEqual is a distinct function from ==, 
> and it must either continue to be distinct or cease to exist, but its 
> name does nothing to clarify any distinction.
 
 In my analysis, the problem is the method's implementation. As I see it, 
 the only use for `elementsEqual` is as a replacement for `==` when two 
 objects are different types (or not known to be the same)—equal elements, 
 and IF the sequences have an order, in the same order. Could you provide 
 an example where `elementsEqual` randomly returning either true or false 
 depending on internal state alone is a legitimate and desirable result?
 
>>> 
>>> It doesn’t randomly return true or false, it consistently returns true or 
>>> false for the *same* pair of Sequences. What *same* means, of course, is 
>>> complicated and exists at two levels (as we have two ways of talking about 
>>> *same*). 
>> 
>> 
>> It is random (for unordered collections) from the standpoint of business 
>> logic.
> 
> Could you define what you mean by “business logic”? Is this is a subset of 
> programming in Swift, and if so what is in it? Can users define their own 
> types in this subset? Also, why would arguments made in that subset also 
> apply to all of Swift?

>From Wikipedia: "In computer software 
>, business logic or domain logic is 
>the part of the program that encodes the real-world business rules 
> that determine how data can be 
>created, stored, and changed 
>. It is 
>contrasted with the remainder of the software that might be concerned with 
>lower-level details of managing a database 
> or displaying the user interface 
>, system infrastructure, or 
>generally connecting various parts of the program.“
(https://en.wikipedia.org/wiki/Business_logic)

I explained why there is no possibility to use `elementsEqual` with unordered 
collections like Set except for the single use case of comparing the elements 
of a set with themselves, i.e. `set.elementsEqual(set)`.

> 
>> The order of the elements of a Set, while publicly observable, cannot be 
>> influenced by business logic because it is an implementation detail. 
> 
> Yes, this is what Set means when it says: “You use a set instead of an array 
> when you need to test efficiently for membership and you aren’t concerned 
> with the order of the elements in the collection, or when you need to ensure 
> that each element appears only once in a collection.” (emphasis mine)

Exactly. I am well aware that Sets are unordered. This whole discussion 
revolves around `elementsEqual` being not appropriate for unordered collections 
like Set. 

-Thorsten


>> Therefore it is not possible to write business logic that exploits this 
>> order, i.e. it is not possible to write business logic using `elementsEqual` 
>> on a Set.
>> The only exception is using the receiver as argument, i.e. 
>> `set.elementsEqual(set)` because in this case, and in this case alone, the 
>> result is independent of the effectively random order.
>> Therefore the single use case for `elementsEqual` for unordered collections 
>> is calling `set.elementsEqual(set)` to determine whether a Set of Floats 
>> contains NaN values. I claim that this is better written as `set.contains { 
>> $0.isNaN }` which works nicely for a Set and is intention revealing 
>> as opposed to using `elementsEqual`.
>> 
>> As I have shown this really is the *single* use case for `elementsEqual` for 
>> unordered collections. There can be no other use case.
>> All other uses of `elementsEqual` involving two different collections where 
>> one is an unordered collection have random results that have absolutely no 
>> business meaning and therefore are bugs.
>> 
>> Therefore having `elementsEqual` as API for unordered collections is a 
>> source of bugs except for a single use case which has a better solution 
>> using `contains`. That is why I would like to split the API.
>> 
>> Adam expressed the concern that this required `map` to implemented 
>> separately for the split APIs: `Iterable.map` would have to return 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 18, 2017, at 12:24 PM, Thorsten Seitz  wrote:
> 
>> 
>> Am 17.10.2017 um 20:47 schrieb Michael Ilseman via swift-evolution 
>> >:
>> 
>> 
>> 
>>> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>>> > wrote:
>>> 
 Because, in my analysis, the problem is that the method is incorrectly 
 named. The problem affects all types that conform to Sequence and not just 
 Set and Dictionary; elementsEqual is a distinct function from ==, and it 
 must either continue to be distinct or cease to exist, but its name does 
 nothing to clarify any distinction.
>>> 
>>> In my analysis, the problem is the method's implementation. As I see it, 
>>> the only use for `elementsEqual` is as a replacement for `==` when two 
>>> objects are different types (or not known to be the same)—equal elements, 
>>> and IF the sequences have an order, in the same order. Could you provide an 
>>> example where `elementsEqual` randomly returning either true or false 
>>> depending on internal state alone is a legitimate and desirable result?
>>> 
>> 
>> It doesn’t randomly return true or false, it consistently returns true or 
>> false for the *same* pair of Sequences. What *same* means, of course, is 
>> complicated and exists at two levels (as we have two ways of talking about 
>> *same*). 
> 
> 
> It is random (for unordered collections) from the standpoint of business 
> logic.

Could you define what you mean by “business logic”? Is this is a subset of 
programming in Swift, and if so what is in it? Can users define their own types 
in this subset? Also, why would arguments made in that subset also apply to all 
of Swift?

> The order of the elements of a Set, while publicly observable, cannot be 
> influenced by business logic because it is an implementation detail.

Yes, this is what Set means when it says: “You use a set instead of an array 
when you need to test efficiently for membership and you aren’t concerned with 
the order of the elements in the collection, or when you need to ensure that 
each element appears only once in a collection.” (emphasis mine)


> Therefore it is not possible to write business logic that exploits this 
> order, i.e. it is not possible to write business logic using `elementsEqual` 
> on a Set.
> The only exception is using the receiver as argument, i.e. 
> `set.elementsEqual(set)` because in this case, and in this case alone, the 
> result is independent of the effectively random order.
> Therefore the single use case for `elementsEqual` for unordered collections 
> is calling `set.elementsEqual(set)` to determine whether a Set of Floats 
> contains NaN values. I claim that this is better written as `set.contains { 
> $0.isNaN }` which works nicely for a Set and is intention revealing as 
> opposed to using `elementsEqual`.
> 
> As I have shown this really is the *single* use case for `elementsEqual` for 
> unordered collections. There can be no other use case.
> All other uses of `elementsEqual` involving two different collections where 
> one is an unordered collection have random results that have absolutely no 
> business meaning and therefore are bugs.
> 
> Therefore having `elementsEqual` as API for unordered collections is a source 
> of bugs except for a single use case which has a better solution using 
> `contains`. That is why I would like to split the API.
> 
> Adam expressed the concern that this required `map` to implemented separately 
> for the split APIs: `Iterable.map` would have to return an `Iterable` whereas 
> `Sequence.map` would have to return a `Sequence`. 
> This is an independent issue IMO, because currently we have a similar 
> situation: `Collection.map` does not return a `Collection` either. It returns 
> an Array. This is a compromise partly due to missing language features which 
> can simply remain when `Sequence` is split.
> 
> Actually the question for the correct return type for `map` is not a simple 
> one. For a `Dictionary` we would probably want to get a `Dicitonary` where 
> the values have been replaced by the mapped ones (this is how Smalltalk does 
> it). But for `Set` we typically do *not* want a `Set` because in general we 
> will be interested in duplicate mapped values. There are times where a `Set` 
> would be the correct return type but this applies to ordered collections or 
> dictionaries as well, so there should be a variant (or an argument with a 
> default) allowing to provide the desired result type or target collection. 
> But this is a completely separate issue which can be easily deferred until 
> the planned language features have arrived which might help finding a good 
> solution for this question. Until then we will just use the current 
> implementation which returns an array.
> 
> To get back to the topic at hand: I propose to differentiate between 
> 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 18, 2017, at 1:20 PM, David Sweeris  wrote:
> 
> How many bugs have been caused by floating point types violating the 
> programmer's mental model of how numbers work? To me, their both in the same 
> category... both involve specific types that claim to adhere to a certain 
> behavior, and both don't in sometimes subtle ways.

I think we have plenty of evidence that misunderstandings about floating point 
lead to bugs. For example: 
https://www.theinquirer.net/inquirer/news/1047844/floating-point-bugs-explode 


It took me about 30 seconds to find a clear example for floating point, and we 
all know there are many many more.

Can anyone find even a single example of this function leading to a shipping 
bug in the real world?
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 18, 2017, at 1:04 PM, Adam Kemp via swift-evolution 
>  wrote:
> 
> 
>> On Oct 18, 2017, at 12:25 PM, Thorsten Seitz via swift-evolution 
>>  wrote:
>> 
>> Therefore having `elementsEqual` as API for unordered collections is a 
>> source of bugs …
> 
> You keep saying that, and yet after repeated requests to provide evidence you 
> still have not backed up this claim. How many bugs are caused by this? 
> Hypotheticals are not evidence. Show us how much of a problem this is in the 
> real world. Why do you think this is so important to fix? What impact is it 
> going to have? If it weren’t for this thread would you even know the problem 
> existed?

How many bugs have been caused by floating point types violating the 
programmer's mental model of how numbers work? To me, their both in the same 
category... both involve specific types that claim to adhere to a certain 
behavior, and both don't in sometimes subtle ways.

- Dave Sweeris
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 18, 2017, at 12:25 PM, Thorsten Seitz via swift-evolution 
>  wrote:
> 
> Therefore having `elementsEqual` as API for unordered collections is a source 
> of bugs …

You keep saying that, and yet after repeated requests to provide evidence you 
still have not backed up this claim. How many bugs are caused by this? 
Hypotheticals are not evidence. Show us how much of a problem this is in the 
real world. Why do you think this is so important to fix? What impact is it 
going to have? If it weren’t for this thread would you even know the problem 
existed?

> Adam expressed the concern that this required `map` to implemented separately 
> for the split APIs: `Iterable.map` would have to return an `Iterable` whereas 
> `Sequence.map` would have to return a `Sequence`. 
> This is an independent issue IMO, because currently we have a similar 
> situation: `Collection.map` does not return a `Collection` either. It returns 
> an Array. This is a compromise partly due to missing language features which 
> can simply remain when `Sequence` is split.

That description does not come close to showing the magnitude of the problem 
with this approach. The reason you think it’s not a significant problem is that 
you’re only looking at a single function (map). This problem isn’t specific to 
just one function, though. The problem is that every single function that takes 
in one Sequence and returns another Sequence would have to handle this 
distinction, including functions that you and I will want to write and reuse. 
That means either:

1. Implement the function twice to handle either ordered or unordered.
2. Only handle one type.
3. Implement a complex new language feature that makes #1 slightly easier, but 
still harder than it is today.

That’s not an improvement. It’s a huge regression in usability. To make that 
kind of change should require a much stronger argument than “hypothetically 
this could lead to bugs”.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 20:47 schrieb Michael Ilseman via swift-evolution 
> :
> 
> 
> 
>> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>> > wrote:
>> 
>>> Because, in my analysis, the problem is that the method is incorrectly 
>>> named. The problem affects all types that conform to Sequence and not just 
>>> Set and Dictionary; elementsEqual is a distinct function from ==, and it 
>>> must either continue to be distinct or cease to exist, but its name does 
>>> nothing to clarify any distinction.
>> 
>> In my analysis, the problem is the method's implementation. As I see it, the 
>> only use for `elementsEqual` is as a replacement for `==` when two objects 
>> are different types (or not known to be the same)—equal elements, and IF the 
>> sequences have an order, in the same order. Could you provide an example 
>> where `elementsEqual` randomly returning either true or false depending on 
>> internal state alone is a legitimate and desirable result?
>> 
> 
> It doesn’t randomly return true or false, it consistently returns true or 
> false for the *same* pair of Sequences. What *same* means, of course, is 
> complicated and exists at two levels (as we have two ways of talking about 
> *same*). 


It is random (for unordered collections) from the standpoint of business logic. 
The order of the elements of a Set, while publicly observable, cannot be 
influenced by business logic because it is an implementation detail. Therefore 
it is not possible to write business logic that exploits this order, i.e. it is 
not possible to write business logic using `elementsEqual` on a Set.

The only exception is using the receiver as argument, i.e. 
`set.elementsEqual(set)` because in this case, and in this case alone, the 
result is independent of the effectively random order.
Therefore the single use case for `elementsEqual` for unordered collections is 
calling `set.elementsEqual(set)` to determine whether a Set of Floats contains 
NaN values. I claim that this is better written as `set.contains { $0.isNaN }` 
which works nicely for a Set and is intention revealing as opposed to 
using `elementsEqual`.

As I have shown this really is the *single* use case for `elementsEqual` for 
unordered collections. There can be no other use case.
All other uses of `elementsEqual` involving two different collections where one 
is an unordered collection have random results that have absolutely no business 
meaning and therefore are bugs.

Therefore having `elementsEqual` as API for unordered collections is a source 
of bugs except for a single use case which has a better solution using 
`contains`. That is why I would like to split the API.

Adam expressed the concern that this required `map` to implemented separately 
for the split APIs: `Iterable.map` would have to return an `Iterable` whereas 
`Sequence.map` would have to return a `Sequence`. 
This is an independent issue IMO, because currently we have a similar 
situation: `Collection.map` does not return a `Collection` either. It returns 
an Array. This is a compromise partly due to missing language features which 
can simply remain when `Sequence` is split.

Actually the question for the correct return type for `map` is not a simple 
one. For a `Dictionary` we would probably want to get a `Dicitonary` where the 
values have been replaced by the mapped ones (this is how Smalltalk does it). 
But for `Set` we typically do *not* want a `Set` because in general we will be 
interested in duplicate mapped values. There are times where a `Set` would be 
the correct return type but this applies to ordered collections or dictionaries 
as well, so there should be a variant (or an argument with a default) allowing 
to provide the desired result type or target collection. 
But this is a completely separate issue which can be easily deferred until the 
planned language features have arrived which might help finding a good solution 
for this question. Until then we will just use the current implementation which 
returns an array.

To get back to the topic at hand: I propose to differentiate between unordered 
and ordered collections because I think that this is an important distinction 
with tractable impact on algorithms (as shown above). The method 
`elementsEqual` would be part of the ordered sequence protocol and I would 
suggest the name `elementsPairwiseEqual`.

-Thorsten



> 
> I apologize for not reading every email in depth in this thread (they are 
> coming in faster than I can parse them), but let me try to present motivation 
> for this and hopefully provide more shared understanding.
> 
> We have two forms of equality we’re talking about: equality of Sequence and 
> equality of the elements of Sequences in their respective ordering. `==` 
> covers the former, and I’ll use the existing (harmful) name of 
> `elementsEqual` for the latter.
> 
> `==` conveys 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Ben Cohen via swift-evolution]

> On Oct 18, 2017, at 5:28 AM, Ole Begemann via swift-evolution 
>  wrote:
> 
> It also seems to clash with Michael's idea 
> 
>  that two substitutable sequences should return true for ==.

This is a bug in Float’s implementation of Equatable, rather than a bug in 
Array. So long as all the elements of Array are correct wrt all the 
requirements of ==, then the performance optimization that compares buffer 
pointers shouldn’t have correctness issues like this.

But Float fails to adhere to those rules – specifically reflexivity, because 
for `let f = 0.0/0.0`, `f == f` returns `false`.

This is the motivation behind the FP part of this proposal for Swift 4, which 
probably needs another go-around for Swift 5:
https://github.com/airspeedswift/swift-evolution/blob/fa007138a54895e94d22e053122ca24ffa0b2eeb/proposals/-ComparisonReform.md

(For which I’ll open a new thread, as this one’s plenty long already :)

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Wed, Oct 18, 2017 at 08:11 Martin R  wrote:

>
>
> > On 18. Oct 2017, at 13:55, Xiaodi Wu  wrote:
> >
> > On Wed, Oct 18, 2017 at 03:05 Martin R  wrote:
> >
> >
> > > On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution <
> swift-evolution@swift.org> wrote:
> > >
> > >
> > >
> > >> On Oct 17, 2017, at 1:36 PM, Benjamin G 
> wrote:
> > >>
> > >>
> > >>
> > >> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman 
> wrote:
> > >>
> > >>
> > >>> On Oct 17, 2017, at 12:54 PM, Benjamin G <
> benjamin.garrig...@gmail.com> wrote:
> > >>>
> > >>> Thanks for the post, that's the first clear explanation i see on
> this thread for the concepts behind the design for Sequence.
> > >>>
> > >>> I am a bit afraid that understanding all that is a bit above what to
> expect the average swift developer will guess when he sees functions like
> "prefix / first / elementEqual (or whatever it's called)" on the Set type.
> > >>> There is, IMHO, a much higher chance he'll either :
> > >>> 1/ not understand anything, or
> > >>> 2/ think Sets are in fact secretely ordered sets, or start writing
> generic extensions above Sequence or Collection thinking those protocols
> are synonymous for orderer collections.
> > >>>
> > >>> 1/ is pretty harmless, but 2/ seems like a source of bug.
> > >>>
> > >>> My personal opinion after reading all this is that we should simply
> change the name
> > >>
> > >> Exactly, and that’s what Xiaodi’s proposal does. Confronted with
> these complexities, his proposal reasons that a name change is the lessor
> or evils, as in the “Proposed solution” section.
> > >>
> > >>> to sequentiallyEquals
> > >>
> > >> Xiaodi floated “lexicographicallyEqual” which is accurate and a big
> improvement, and I’m liking it more and more. I floated
> “sequentiallyEquals”, which I’m liking less and less now. My current
> preference is for “elementsOrderedEqual” which I think is more descriptive
> but unwieldy. On the other hand, this is a far less common facility, and
> order matters, so maybe more verbose names are fine.
> > >>
> > >> I'm sorry to bring more bikeshedding, but lexicographicallyEqual
> seems absolutely atrocious to me. Imagine all the steps required the user
> of a Set to understand why a lexicographicallyEqual function is
> suggested by the compiler ??
> > >>
> > >
> > > My initial resistance is that lexicographical implies a comparability
> beyond equality. `lexicographicallyEquals`, then, had me (erroneously)
> wondering if the “lexicographically” part meant that the elements were
> presented in lexicographical order and then compared for equality. But, I
> was in error and this is a wrong interpretation of the term. “abc” is not
> lexicographically equal to “cba”, and it’s quite a mental leap to think
> that the order of elements would be presented differently. That’s not to
> say that others won't have the same misinterpretation and that’s why I’m
> hoping for a better name. But, if `lexicographicallyEquals` is what we
> settle on, that’s a huge improvement over `elementsEqual`.
> >
> >
> > In the earlier post
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171009/040428.html,
> Xiaodi Wu quoted from
> http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
> because that "defines lexicographical comparison unambiguously for C++".
> >
> > But that definition corresponds to what `lexicographicallyPrecedes()`
> method does: two sequences are compared in iteration order using `<`, until
> one is exhausted or a difference is found. It requires that the sequence
> Element type is Comparable (but not that the sequences elements are
> ordered!) and allows to order all sets with the same element type.
> >
> > In your example, "abc" is not lexicographically equal to "cba" because
> "a" < "c".
> >
> > Not quite. It's because "a" != "c".
> >
> > C++ `lexicographical_compare` does correspond to
> `lexicographicallyPrecedes` and evaluates for lexicographical less-than,
> but the documentation there also defines lexicographical equality, which is
> in terms of equivalence.
>
> Almost the first thing a user reads on
> http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare after
> the prototypes is
>
> > Elements are compared using operator< (or given binary comparison
> function comp)
>
> and later
>
> > The first mismatching element defines which range is lexicographically
> less or greater than the other.


Yes, this is a description of C++ lexicographical_compare, which tells you
if range is lexicographically less than another.

> If two ranges have equivalent elements and are of the same length, then
> the ranges are lexicographically equal.


This is the definition of lexicographical equality. It is a named
std::equal in C++.

My interpretation would be that two ranges (or in our case, sequences) are
> "lexicographically equal" if the comparison of 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

Yup.

On Wed, Oct 18, 2017 at 07:28 Ole Begemann  wrote:

> On Tue, Oct 17, 2017, at 20:46, Xiaodi Wu via swift-evolution wrote:
>
> On Tue, Oct 17, 2017 at 12:54 Jonathan Hull  wrote:
>
> Why was elementsEqual created?  Isn’t it meant to check equality of two
> sequences in a generic context where == isn’t available?
>
>
> No no no no no no no no. That’s precisely why the name is misleading.
> elementsEqual is *not* simply a mixed-type version of ==. Remember that ==
> as implemented on a concrete sequence type *has no obligation* to use
> elementwise comparison using the element’s implementation of ==. This is
> not merely theoretical: [Float].== does *not* do an elementwise comparison
> using Float.==. By contrast, you are guaranteed a true elementwise
> comparison with elementsEqual regardless of how equivalence is defined for
> the sequence.
>
>
> Really? I would have thought an elementwise comparison is exactly what
> [Float].== would do.
>
> I tested this and these are the (very surprising, at least to me) results:
>
> let numbers: [Float] = [1, .nan]
> let copy = numbers
> let sameNumbers: [Float] = [1, .nan]
>
> numbers == copy // (1) true (!)
> numbers == sameNumbers  // (2) false (!)
> numbers.elementsEqual(copy) // (3) false (ok)
> numbers.elementsEqual(sameNumbers)  // (4) false (ok)
>
> So [Float].== returns a different result depending on whether you compare
> two arrays that share the same buffer (1) or two arrays with the same
> contents (2) when the array contains NaN. The reason is that Array.==
> immediately returns true if two arrays share the same buffer
> 
> .
>
> Even knowing that comparing floats is problematic in the context of NaN
> (and in general), I find this very surprising. It also seems to clash with 
> Michael's
> idea
> 
> that two substitutable sequences should return true for ==.
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Martin R via swift-evolution]

> On 18. Oct 2017, at 13:55, Xiaodi Wu  wrote:
> 
> On Wed, Oct 18, 2017 at 03:05 Martin R  wrote:
> 
> 
> > On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution 
> >  wrote:
> >
> >
> >
> >> On Oct 17, 2017, at 1:36 PM, Benjamin G  
> >> wrote:
> >>
> >>
> >>
> >> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman  
> >> wrote:
> >>
> >>
> >>> On Oct 17, 2017, at 12:54 PM, Benjamin G  
> >>> wrote:
> >>>
> >>> Thanks for the post, that's the first clear explanation i see on this 
> >>> thread for the concepts behind the design for Sequence.
> >>>
> >>> I am a bit afraid that understanding all that is a bit above what to 
> >>> expect the average swift developer will guess when he sees functions like 
> >>> "prefix / first / elementEqual (or whatever it's called)" on the Set type.
> >>> There is, IMHO, a much higher chance he'll either :
> >>> 1/ not understand anything, or
> >>> 2/ think Sets are in fact secretely ordered sets, or start writing 
> >>> generic extensions above Sequence or Collection thinking those protocols 
> >>> are synonymous for orderer collections.
> >>>
> >>> 1/ is pretty harmless, but 2/ seems like a source of bug.
> >>>
> >>> My personal opinion after reading all this is that we should simply 
> >>> change the name
> >>
> >> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these 
> >> complexities, his proposal reasons that a name change is the lessor or 
> >> evils, as in the “Proposed solution” section.
> >>
> >>> to sequentiallyEquals
> >>
> >> Xiaodi floated “lexicographicallyEqual” which is accurate and a big 
> >> improvement, and I’m liking it more and more. I floated 
> >> “sequentiallyEquals”, which I’m liking less and less now. My current 
> >> preference is for “elementsOrderedEqual” which I think is more descriptive 
> >> but unwieldy. On the other hand, this is a far less common facility, and 
> >> order matters, so maybe more verbose names are fine.
> >>
> >> I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems 
> >> absolutely atrocious to me. Imagine all the steps required the user of a 
> >> Set to understand why a lexicographicallyEqual function is suggested 
> >> by the compiler ??
> >>
> >
> > My initial resistance is that lexicographical implies a comparability 
> > beyond equality. `lexicographicallyEquals`, then, had me (erroneously) 
> > wondering if the “lexicographically” part meant that the elements were 
> > presented in lexicographical order and then compared for equality. But, I 
> > was in error and this is a wrong interpretation of the term. “abc” is not 
> > lexicographically equal to “cba”, and it’s quite a mental leap to think 
> > that the order of elements would be presented differently. That’s not to 
> > say that others won't have the same misinterpretation and that’s why I’m 
> > hoping for a better name. But, if `lexicographicallyEquals` is what we 
> > settle on, that’s a huge improvement over `elementsEqual`.
> 
> 
> In the earlier post 
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171009/040428.html,
>  Xiaodi Wu quoted from 
> http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare because 
> that "defines lexicographical comparison unambiguously for C++".
> 
> But that definition corresponds to what `lexicographicallyPrecedes()` method 
> does: two sequences are compared in iteration order using `<`, until one is 
> exhausted or a difference is found. It requires that the sequence Element 
> type is Comparable (but not that the sequences elements are ordered!) and 
> allows to order all sets with the same element type.
> 
> In your example, "abc" is not lexicographically equal to "cba" because "a" < 
> "c".
> 
> Not quite. It's because "a" != "c".
> 
> C++ `lexicographical_compare` does correspond to `lexicographicallyPrecedes` 
> and evaluates for lexicographical less-than, but the documentation there also 
> defines lexicographical equality, which is in terms of equivalence.

Almost the first thing a user reads on 
http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare after the 
prototypes is

> Elements are compared using operator< (or given binary comparison function 
> comp)

and later

> The first mismatching element defines which range is lexicographically less 
> or greater than the other.
> If two ranges have equivalent elements and are of the same length, then the 
> ranges are lexicographically equal.

My interpretation would be that two ranges (or in our case, sequences) are 
"lexicographically equal" if the comparison of the elements in iteration order 
does not find a mismatching element, i.e. for all elements (a, b) at the 
corresponding position, neither a < b nor b < a holds.

> In Swift, a type can define a notion of equivalence without defining a notion 
> of precedence, so 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Ole Begemann via swift-evolution]

On Tue, Oct 17, 2017, at 20:46, Xiaodi Wu via swift-evolution wrote:
> On Tue, Oct 17, 2017 at 12:54 Jonathan Hull  wrote:
> 
>> Why was elementsEqual created?  Isn’t it meant to check equality of
>> two sequences in a generic context where == isn’t available?> 
> No no no no no no no no. That’s precisely why the name is misleading.
> elementsEqual is *not* simply a mixed-type version of ==. Remember
> that == as implemented on a concrete sequence type *has no obligation*
> to use elementwise comparison using the element’s implementation of
> ==. This is not merely theoretical: [Float].== does *not* do an
> elementwise comparison using Float.==. By contrast, you are guaranteed
> a true elementwise comparison with elementsEqual regardless of how
> equivalence is defined for the sequence.
Really? I would have thought an elementwise comparison is exactly what
[Float].== would do.
I tested this and these are the (very surprising, at least to me)
results:
let numbers: [Float] = [1, .nan]
let copy = numbers
let sameNumbers: [Float] = [1, .nan]

numbers == copy // (1) true (!)
numbers == sameNumbers  // (2) false (!)
numbers.elementsEqual(copy) // (3) false (ok)
numbers.elementsEqual(sameNumbers)  // (4) false (ok)

So [Float].== returns a different result depending on whether you
compare two arrays that share the same buffer (1) or two arrays with the
same contents (2) when the array contains NaN. The reason is that
Array.== immediately returns true if two arrays share the same
buffer[1].
Even knowing that comparing floats is problematic in the context of NaN
(and in general), I find this very surprising. It also seems to clash
with Michael's idea[2] that two substitutable sequences should return
true for ==.

Links:

  1. 
https://github.com/apple/swift/blob/master/stdlib/public/core/Arrays.swift.gyb#L2194-L2197
  2. 
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171016/040544.html
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Wed, Oct 18, 2017 at 03:05 Martin R  wrote:

>
>
> > On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution <
> swift-evolution@swift.org> wrote:
> >
> >
> >
> >> On Oct 17, 2017, at 1:36 PM, Benjamin G 
> wrote:
> >>
> >>
> >>
> >> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman 
> wrote:
> >>
> >>
> >>> On Oct 17, 2017, at 12:54 PM, Benjamin G 
> wrote:
> >>>
> >>> Thanks for the post, that's the first clear explanation i see on this
> thread for the concepts behind the design for Sequence.
> >>>
> >>> I am a bit afraid that understanding all that is a bit above what to
> expect the average swift developer will guess when he sees functions like
> "prefix / first / elementEqual (or whatever it's called)" on the Set type.
> >>> There is, IMHO, a much higher chance he'll either :
> >>> 1/ not understand anything, or
> >>> 2/ think Sets are in fact secretely ordered sets, or start writing
> generic extensions above Sequence or Collection thinking those protocols
> are synonymous for orderer collections.
> >>>
> >>> 1/ is pretty harmless, but 2/ seems like a source of bug.
> >>>
> >>> My personal opinion after reading all this is that we should simply
> change the name
> >>
> >> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these
> complexities, his proposal reasons that a name change is the lessor or
> evils, as in the “Proposed solution” section.
> >>
> >>> to sequentiallyEquals
> >>
> >> Xiaodi floated “lexicographicallyEqual” which is accurate and a big
> improvement, and I’m liking it more and more. I floated
> “sequentiallyEquals”, which I’m liking less and less now. My current
> preference is for “elementsOrderedEqual” which I think is more descriptive
> but unwieldy. On the other hand, this is a far less common facility, and
> order matters, so maybe more verbose names are fine.
> >>
> >> I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems
> absolutely atrocious to me. Imagine all the steps required the user of a
> Set to understand why a lexicographicallyEqual function is suggested
> by the compiler ??
> >>
> >
> > My initial resistance is that lexicographical implies a comparability
> beyond equality. `lexicographicallyEquals`, then, had me (erroneously)
> wondering if the “lexicographically” part meant that the elements were
> presented in lexicographical order and then compared for equality. But, I
> was in error and this is a wrong interpretation of the term. “abc” is not
> lexicographically equal to “cba”, and it’s quite a mental leap to think
> that the order of elements would be presented differently. That’s not to
> say that others won't have the same misinterpretation and that’s why I’m
> hoping for a better name. But, if `lexicographicallyEquals` is what we
> settle on, that’s a huge improvement over `elementsEqual`.
>
>
> In the earlier post
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171009/040428.html,
> Xiaodi Wu quoted from
> http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
> because that "defines lexicographical comparison unambiguously for C++".
>
> But that definition corresponds to what `lexicographicallyPrecedes()`
> method does: two sequences are compared in iteration order using `<`, until
> one is exhausted or a difference is found. It requires that the sequence
> Element type is Comparable (but not that the sequences elements are
> ordered!) and allows to order all sets with the same element type.
>
> In your example, "abc" is not lexicographically equal to "cba" because "a"
> < "c".


Not quite. It's because "a" != "c".

C++ `lexicographical_compare` does correspond to
`lexicographicallyPrecedes` and evaluates for lexicographical less-than,
but the documentation there also defines lexicographical equality, which is
in terms of equivalence.

In Swift, a type can define a notion of equivalence without defining a
notion of precedence, so lexicographical equality can be evaluated even if
lexicographical less-than cannot in that case.

The equivalent of `elementsEqual()` in C++ would be
> http://en.cppreference.com/w/cpp/algorithm/equal, which has the Note
>
>std::equal should not be used to compare the ranges formed by the
> iterators from
>std::unordered_set, ... because the order in which the elements are
> stored in
>those containers may be different even if the two containers store the
> same elements.
>
> which is the same issue that we are talking about here.
>
> My argument against the name "lexicographicallyEquals" would be
>
> - It suggests that the elements from both sequences are compared (in
> iteration order) using `<` (and thus required to be Comparable).
> - Googling for "lexicographical comparison" leads to the above C++
> reference, or to https://en.wikipedia.org/wiki/Lexicographical_order.
> Both are about ordering sequences (words) based on the order of the
> 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Martin R via swift-evolution]

> On 17. Oct 2017, at 23:22, Michael Ilseman via swift-evolution 
>  wrote:
> 
> 
> 
>> On Oct 17, 2017, at 1:36 PM, Benjamin G  wrote:
>> 
>> 
>> 
>> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman  wrote:
>> 
>> 
>>> On Oct 17, 2017, at 12:54 PM, Benjamin G  
>>> wrote:
>>> 
>>> Thanks for the post, that's the first clear explanation i see on this 
>>> thread for the concepts behind the design for Sequence.
>>> 
>>> I am a bit afraid that understanding all that is a bit above what to expect 
>>> the average swift developer will guess when he sees functions like "prefix 
>>> / first / elementEqual (or whatever it's called)" on the Set type.
>>> There is, IMHO, a much higher chance he'll either : 
>>> 1/ not understand anything, or 
>>> 2/ think Sets are in fact secretely ordered sets, or start writing generic 
>>> extensions above Sequence or Collection thinking those protocols are 
>>> synonymous for orderer collections.
>>> 
>>> 1/ is pretty harmless, but 2/ seems like a source of bug.
>>> 
>>> My personal opinion after reading all this is that we should simply change 
>>> the name
>> 
>> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these 
>> complexities, his proposal reasons that a name change is the lessor or 
>> evils, as in the “Proposed solution” section.
>> 
>>> to sequentiallyEquals
>> 
>> Xiaodi floated “lexicographicallyEqual” which is accurate and a big 
>> improvement, and I’m liking it more and more. I floated 
>> “sequentiallyEquals”, which I’m liking less and less now. My current 
>> preference is for “elementsOrderedEqual” which I think is more descriptive 
>> but unwieldy. On the other hand, this is a far less common facility, and 
>> order matters, so maybe more verbose names are fine.
>> 
>> I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems 
>> absolutely atrocious to me. Imagine all the steps required the user of a 
>> Set to understand why a lexicographicallyEqual function is suggested by 
>> the compiler ??
>> 
> 
> My initial resistance is that lexicographical implies a comparability beyond 
> equality. `lexicographicallyEquals`, then, had me (erroneously) wondering if 
> the “lexicographically” part meant that the elements were presented in 
> lexicographical order and then compared for equality. But, I was in error and 
> this is a wrong interpretation of the term. “abc” is not lexicographically 
> equal to “cba”, and it’s quite a mental leap to think that the order of 
> elements would be presented differently. That’s not to say that others won't 
> have the same misinterpretation and that’s why I’m hoping for a better name. 
> But, if `lexicographicallyEquals` is what we settle on, that’s a huge 
> improvement over `elementsEqual`.


In the earlier post 
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20171009/040428.html,
 Xiaodi Wu quoted from 
http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare because that 
"defines lexicographical comparison unambiguously for C++".

But that definition corresponds to what `lexicographicallyPrecedes()` method 
does: two sequences are compared in iteration order using `<`, until one is 
exhausted or a difference is found. It requires that the sequence Element type 
is Comparable (but not that the sequences elements are ordered!) and allows to 
order all sets with the same element type.

In your example, "abc" is not lexicographically equal to "cba" because "a" < 
"c".

The equivalent of `elementsEqual()` in C++ would be 
http://en.cppreference.com/w/cpp/algorithm/equal, which has the Note

   std::equal should not be used to compare the ranges formed by the iterators 
from
   std::unordered_set, ... because the order in which the elements are stored in
   those containers may be different even if the two containers store the same 
elements.

which is the same issue that we are talking about here.

My argument against the name "lexicographicallyEquals" would be

- It suggests that the elements from both sequences are compared (in iteration 
order) using `<` (and thus required to be Comparable).
- Googling for "lexicographical comparison" leads to the above C++ reference, 
or to https://en.wikipedia.org/wiki/Lexicographical_order. Both are about 
ordering sequences (words) based on the order of the underlying element type 
(alphabet). This does not describe what `elementsEqual()` does.

Both arguments are unrelated to whether the sequences are generated from 
ordered or unordered collections (like sets), or whether the elements in each 
sequence are ordered or not.

Just my 2ct. Probably this has been said before, it is difficult to keep track 
of the various threads in this discussion.

Regards, Martin



___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 17, 2017, at 7:52 PM, Kevin Nattinger via swift-evolution 
>  wrote:
> 
> So, what I'm getting from this explanation is that `Equatable` is meaningless 
> on its own; each class needs to document exactly what  "substitutability" 
> means as implemented, and any code that uses `==` needs to check the 
> documentation for that specific class and make sure the intended use 
> ("context," as you say) aligns with the class's definition.

This is how it works in every language I’ve ever worked on that has a concept 
of overridable equality checks, including Objective-C.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

So, what I'm getting from this explanation is that `Equatable` is meaningless 
on its own; each class needs to document exactly what  "substitutability" means 
as implemented, and any code that uses `==` needs to check the documentation 
for that specific class and make sure the intended use ("context," as you say) 
aligns with the class's definition.

>>> 
>>> Contrived Example: Two Lorem Ipsum generators are the same generator 
>>> (referentially equal, substitutable for the purposes of my library), but 
>>> they sample the user’s current battery level (global state) each time they 
>>> produce text to decide how fancy to make the faux Latin. They’re 
>>> substitutable, but don’t generate the same sequence.
>> 
>> Evidently I disagree with your definition of "substitutable." How can you 
>> say one thing can be substituted for another when doing so gives a different 
>> result?
>> 
> 
> They are substitutable for the purposes of certain operations. The key 
> question is “what” gives a different result.
> 
> Sets are primarily about membership, and equal sets are substitutable (hand 
> wavy) for Set-like purposes. But, two equal Sets are not substitutable for 
> iteration purposes unless they produce the same elements in the same order. 
> This latter requirement is far less important than the former for Sets, but 
> can still come up in generic contexts.
> 
> Two Lorem Ipsum generators could be equal in that they are substitutable for 
> (hand wavy) faux-Latin generation purposes, even if the sequence of generated 
> characters happens to differ.

Hmm, I… guess I could see randomized generators comparing == because their 
public configuration is the same, just not the implementation detail of their 
RNG states.  Not sure I'd implement it that way myself—perhaps I just take the 
"substitutability" more seriously than some.

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 17, 2017, at 2:08 PM, Kevin Nattinger  wrote:
> 
>> 
>> On Oct 17, 2017, at 11:47 AM, Michael Ilseman > > wrote:
>> 
>> 
>> 
>>> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>>> > wrote:
>>> 
 Because, in my analysis, the problem is that the method is incorrectly 
 named. The problem affects all types that conform to Sequence and not just 
 Set and Dictionary; elementsEqual is a distinct function from ==, and it 
 must either continue to be distinct or cease to exist, but its name does 
 nothing to clarify any distinction.
>>> 
>>> In my analysis, the problem is the method's implementation. As I see it, 
>>> the only use for `elementsEqual` is as a replacement for `==` when two 
>>> objects are different types (or not known to be the same)—equal elements, 
>>> and IF the sequences have an order, in the same order. Could you provide an 
>>> example where `elementsEqual` randomly returning either true or false 
>>> depending on internal state alone is a legitimate and desirable result?
>>> 
>> 
>> It doesn’t randomly return true or false, it consistently returns true or 
>> false for the *same* pair of Sequences. What *same* means, of course, is 
>> complicated and exists at two levels (as we have two ways of talking about 
>> *same*). 
> 
> I didn't mean literally random, but the result for any two equal sets is 
> unpredictable and depends on implementation details.
> 

Exactly, and that’s why having this method is important. If you wish to pass a 
Set to a generic operation that cares about the order (e.g. generic over 
Sequence and not e.g. SetAlgebra), it is only substitutable with another 
Sequence if it happens to have the same ordering of the same elements. All 
orderings for Sets are arbitrary, at some level.



>> 
>> I apologize for not reading every email in depth in this thread (they are 
>> coming in faster than I can parse them), but let me try to present 
>> motivation for this and hopefully provide more shared understanding.
>> 
>> We have two forms of equality we’re talking about: equality of Sequence and 
>> equality of the elements of Sequences in their respective ordering. `==` 
>> covers the former, and I’ll use the existing (harmful) name of 
>> `elementsEqual` for the latter.
>> 
>> `==` conveys substitutability of the two Sequences. This does not 
>> necessarily entail anything about their elements, how those elements are 
>> ordered, etc., it just means two Sequences are substitutable. 
>> `elementsEqual` means that the two Sequences produce substitutable elements. 
>> These are different concepts and both are independently useful.
>> 
>> Cases:
>> 
>> 1. Two Sequences are substitutable and produce substitutable elements when 
>> iterated. `==` and `elementsEqual` both return true. 
>> 
>> Example: Two arrays with the same elements in the same order.
>> 
>> 
>> 2. Two Sequences are substitutable, but do not produce substitutable 
>> elements when iterated. `==` returns true, while `elementsEqual` returns 
>> false.
>> 
>> Example: Two Sets that contain the same elements but in a different order.
>> 
>> Contrived Example: Two Lorem Ipsum generators are the same generator 
>> (referentially equal, substitutable for the purposes of my library), but 
>> they sample the user’s current battery level (global state) each time they 
>> produce text to decide how fancy to make the faux Latin. They’re 
>> substitutable, but don’t generate the same sequence.
> 
> Evidently I disagree with your definition of "substitutable." How can you say 
> one thing can be substituted for another when doing so gives a different 
> result?
> 

They are substitutable for the purposes of certain operations. The key question 
is “what” gives a different result.

Sets are primarily about membership, and equal sets are substitutable (hand 
wavy) for Set-like purposes. But, two equal Sets are not substitutable for 
iteration purposes unless they produce the same elements in the same order. 
This latter requirement is far less important than the former for Sets, but can 
still come up in generic contexts.

Two Lorem Ipsum generators could be equal in that they are substitutable for 
(hand wavy) faux-Latin generation purposes, even if the sequence of generated 
characters happens to differ. But, if I cared about the sequences of generated 
characters being the same, then they are only substitutable if they produce the 
same characters in the same order. For example, this has ramifications on how I 
might test my generators.

I agree that this case is a little unintuitive, and I’m still nailing it down 
in my mind.


>> 
>> 
>> 3. Two Sequences are not substitutable, but produce substitutable elements 
>> when iterated. `==` returns false, while `elementsEqual` returns true.
>> 
>> Example: Consider two sequences that have differing 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 14:41 Jonathan Hull  wrote:

> On Oct 17, 2017, at 11:46 AM, Xiaodi Wu  wrote:
>
>
> On Tue, Oct 17, 2017 at 12:54 Jonathan Hull  wrote:
>
>> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu  wrote:
>>
>>
>> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull  wrote:
>>
>>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu  wrote:
>>>
>>>
>>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz 
>>> wrote:
>>>


 Am 17.10.2017 um 00:13 schrieb Xiaodi Wu :


 On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz 
 wrote:

> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org>:
>
>
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>
>>
>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull 
>> wrote:
>>
>>>
>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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.
>

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 17, 2017, at 1:36 PM, Benjamin G  wrote:
> 
> 
> 
> On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman  > wrote:
> 
> 
>> On Oct 17, 2017, at 12:54 PM, Benjamin G > > wrote:
>> 
>> Thanks for the post, that's the first clear explanation i see on this thread 
>> for the concepts behind the design for Sequence.
>> 
>> I am a bit afraid that understanding all that is a bit above what to expect 
>> the average swift developer will guess when he sees functions like "prefix / 
>> first / elementEqual (or whatever it's called)" on the Set type.
>> There is, IMHO, a much higher chance he'll either : 
>> 1/ not understand anything, or 
>> 2/ think Sets are in fact secretely ordered sets, or start writing generic 
>> extensions above Sequence or Collection thinking those protocols are 
>> synonymous for orderer collections.
>> 
>> 1/ is pretty harmless, but 2/ seems like a source of bug.
>> 
>> My personal opinion after reading all this is that we should simply change 
>> the name
> 
> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these 
> complexities, his proposal reasons that a name change is the lessor or evils, 
> as in the “Proposed solution” section.
> 
>> to sequentiallyEquals
> 
> Xiaodi floated “lexicographicallyEqual” which is accurate and a big 
> improvement, and I’m liking it more and more. I floated “sequentiallyEquals”, 
> which I’m liking less and less now. My current preference is for 
> “elementsOrderedEqual” which I think is more descriptive but unwieldy. On the 
> other hand, this is a far less common facility, and order matters, so maybe 
> more verbose names are fine.
> 
> I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems 
> absolutely atrocious to me. Imagine all the steps required the user of a 
> Set to understand why a lexicographicallyEqual function is suggested by 
> the compiler ??
> 

My initial resistance is that lexicographical implies a comparability beyond 
equality. `lexicographicallyEquals`, then, had me (erroneously) wondering if 
the “lexicographically” part meant that the elements were presented in 
lexicographical order and then compared for equality. But, I was in error and 
this is a wrong interpretation of the term. “abc” is not lexicographically 
equal to “cba”, and it’s quite a mental leap to think that the order of 
elements would be presented differently. That’s not to say that others won't 
have the same misinterpretation and that’s why I’m hoping for a better name. 
But, if `lexicographicallyEquals` is what we settle on, that’s a huge 
improvement over `elementsEqual`.

> Since you seem to give the kind of answer i'm looking for, do you have any 
> answer to a previous question i asked regarding the rational for conflating 
> the iterator with the collection ?
> What i mean by that is : i think nobody would have cared if the syntax for 
> Set was actually
> set1.iterator.elementEquals(set2.iterator)
> It's a bit more verbose, but the meaning is obvious.

To me that reads as meaning something more akin to set1.first == set2.first 
(whether nil or not). I think what you’re trying to demonstrate is an equality 
on an iterator that implies equality of iterated elements. But, there could be 
alternatives: if a Sequence has identity, then perhaps its iterator’s equality 
should enforce the identity. I may also be completing misunderstanding your 
question.

> I think a reason why people are confused is that the actual design conflates 
> methods of the "iterator" on the collection type itself. An alternate design 
> would have been to make collection Sequenceable rather than a sequence 
> themselves. But i suppose you've thought about that already, so i'm just 
> curious to know what made you choose the current solution instead.

No, I have not thought about it much. I’m a relatively new contributor (a few 
months) to the standard library, and am just now thinking about such things on 
an as-needed basis.

Personally, I care much more about what operations a data structure provides 
and how it does it than whatever protocol hierarchy it models. As far as what 
hierarchy should exist in the standard library, I care much more about 
pragmatism than purity as the hierarchy’s main benefit is to enable generic 
programming. I think George Box said it best: “All models are wrong, but some 
are useful”.



___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 17, 2017, at 11:47 AM, Michael Ilseman  wrote:
> 
> 
> 
>> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>> > wrote:
>> 
>>> Because, in my analysis, the problem is that the method is incorrectly 
>>> named. The problem affects all types that conform to Sequence and not just 
>>> Set and Dictionary; elementsEqual is a distinct function from ==, and it 
>>> must either continue to be distinct or cease to exist, but its name does 
>>> nothing to clarify any distinction.
>> 
>> In my analysis, the problem is the method's implementation. As I see it, the 
>> only use for `elementsEqual` is as a replacement for `==` when two objects 
>> are different types (or not known to be the same)—equal elements, and IF the 
>> sequences have an order, in the same order. Could you provide an example 
>> where `elementsEqual` randomly returning either true or false depending on 
>> internal state alone is a legitimate and desirable result?
>> 
> 
> It doesn’t randomly return true or false, it consistently returns true or 
> false for the *same* pair of Sequences. What *same* means, of course, is 
> complicated and exists at two levels (as we have two ways of talking about 
> *same*). 

I didn't mean literally random, but the result for any two equal sets is 
unpredictable and depends on implementation details.

> 
> I apologize for not reading every email in depth in this thread (they are 
> coming in faster than I can parse them), but let me try to present motivation 
> for this and hopefully provide more shared understanding.
> 
> We have two forms of equality we’re talking about: equality of Sequence and 
> equality of the elements of Sequences in their respective ordering. `==` 
> covers the former, and I’ll use the existing (harmful) name of 
> `elementsEqual` for the latter.
> 
> `==` conveys substitutability of the two Sequences. This does not necessarily 
> entail anything about their elements, how those elements are ordered, etc., 
> it just means two Sequences are substitutable. `elementsEqual` means that the 
> two Sequences produce substitutable elements. These are different concepts 
> and both are independently useful.
> 
> Cases:
> 
> 1. Two Sequences are substitutable and produce substitutable elements when 
> iterated. `==` and `elementsEqual` both return true. 
> 
> Example: Two arrays with the same elements in the same order.
> 
> 
> 2. Two Sequences are substitutable, but do not produce substitutable elements 
> when iterated. `==` returns true, while `elementsEqual` returns false.
> 
> Example: Two Sets that contain the same elements but in a different order.
> 
> Contrived Example: Two Lorem Ipsum generators are the same generator 
> (referentially equal, substitutable for the purposes of my library), but they 
> sample the user’s current battery level (global state) each time they produce 
> text to decide how fancy to make the faux Latin. They’re substitutable, but 
> don’t generate the same sequence.

Evidently I disagree with your definition of "substitutable." How can you say 
one thing can be substituted for another when doing so gives a different result?

> 
> 
> 3. Two Sequences are not substitutable, but produce substitutable elements 
> when iterated. `==` returns false, while `elementsEqual` returns true.
> 
> Example: Consider two sequences that have differing identity. `==` operates 
> on an identity level, `elementsEqual` operates at an element level.
> 
> Contrived Example: InfiniteMonkeys and Shakespeare both produce the same 
> sonnet, but they’re not substitutable for my library’s purposes. 

The way I see it, this is exactly the reason for this function—determining 
whether two objects give the same sequence without regards to their types.

> 
> 
> 4. Two Sequences are not substitutable and don’t produce substitutable 
> elements when iterated. `==` and `elementsEqual` both return false.
> 
> Example: `[1,2,3]` compared to `[4,5,6]`
> 
> 
> It is true that situations #2 and #3 are a little harder to grok, but they 
> are what illustrate the subtle difference at hand. I think situation #2 is 
> the most confusing, and has been the primary focus of this thread as Set 
> exists and exhibits it.

Indeed. My opinion is that #2 is not just confusing, but an entirely invalid 
result/state. 

> 
> 
> Now, onto naming. `elementsEqual` is a very poor choice of name for the 
> concept of equality of elements in their respective orderings, as it doesn’t 
> highlight the “in their respective orderings” part. `lexicographicallyEqual` 
> highlights the ordering much better, as “abc” is not lexicographically equal 
> to “cba” despite having equal elements. I think it is clearly an improvement 
> over the status quo. I like something a little more explicit (e.g. 
> `elementsOrderedEqual`), personally, but I don’t care that strongly. I’m just 
> glad to see `elementsEqual` getting some 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Manolo van Ee via swift-evolution]

If that’s an option, that could help.

To me it feels like there might be something that could be fixed in the
design. However, I’m not aware of all the things that were considered when
creating the current design, and how much impact it will have to change it,
so I can’t say too much about it and will leave it to more knowledgeable
people to have an opinion on that.

Regards,
/Manolo


On Tue, 17 Oct 2017 at 22:27, Michael Ilseman  wrote:

> (I saw this after I sent my reply to Benjamin G). We can also deprecate it
> or warn when the type is concretely known to be Set. Not a total solution,
> but it’s nice to catch some bugs.
>
>
> On Oct 17, 2017, at 1:21 PM, Manolo van Ee  wrote:
>
>
> On Tue, 17 Oct 2017 at 21:00, Jonathan Hull via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>>
>> On Oct 17, 2017, at 11:47 AM, Michael Ilseman via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>> `==` conveys substitutability of the two Sequences. This does not
>> necessarily entail anything about their elements, how those elements are
>> ordered, etc., it just means two Sequences are substitutable.
>> `elementsEqual` means that the two Sequences produce substitutable
>> elements. These are different concepts and both are independently useful.
>>
>>
>> I agree that ‘==‘ conveys substitutability.  Here is the issue:
>>
>> let a = Set([1,2,3,4,5])
>> let b = Set([5,4,3,2,1])
>>
>> a == b //True, they are substitutable
>>
>> [1,2,3,4,5].elementsEqual(a) //True
>> [1,2,3,4,5].elementsEqual(b) //False… I guess they weren’t actually
>> substitutable after all
>>
>>
>> Thanks,
>> Jon
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
> I read along with most of the thread and like to add one thing. Maybe it’s
> not the right way to look at things, but I see protocol extensions as being
> part of any type that conforms to the protocol. As it is now, code
> completion on a Set will present me with the elementsEqual function, which
> in my view is misleading, since it cannot be used in any useful way with a
> Set.
>
> By renaming elementsEqual we might be able to make it less misleading, but
> it will always be a useless function that is part of the Set namespace (or
> Dictionary for that matter).
>
> I don’t know what the best solution would be, but to me it feels like
> distinguishing between Iterable and Sequence, or Ordered and Unordered
> makes sense, and it might be good to at least investigate what the impact
> would be.
>
> Regards,
> /Manolo
>
>
>
>
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Benjamin G via swift-evolution]

On Tue, Oct 17, 2017 at 10:25 PM, Michael Ilseman 
wrote:

>
>
> On Oct 17, 2017, at 12:54 PM, Benjamin G 
> wrote:
>
> Thanks for the post, that's the first clear explanation i see on this
> thread for the concepts behind the design for Sequence.
>
> I am a bit afraid that understanding all that is a bit above what to
> expect the average swift developer will guess when he sees functions like
> "prefix / first / elementEqual (or whatever it's called)" on the Set type.
> There is, IMHO, a much higher chance he'll either :
> 1/ not understand anything, or
> 2/ think Sets are in fact secretely ordered sets, or start writing generic
> extensions above Sequence or Collection thinking those protocols are
> synonymous for orderer collections.
>
> 1/ is pretty harmless, but 2/ seems like a source of bug.
>
> My personal opinion after reading all this is that we should simply change
> the name
>
>
> Exactly, and that’s what Xiaodi’s proposal does. Confronted with these
> complexities, his proposal reasons that a name change is the lessor or
> evils, as in the “Proposed solution” section.
>
> to sequentiallyEquals
>
>
> Xiaodi floated “lexicographicallyEqual” which is accurate and a big
> improvement, and I’m liking it more and more. I floated
> “sequentiallyEquals”, which I’m liking less and less now. My current
> preference is for “elementsOrderedEqual” which I think is more descriptive
> but unwieldy. On the other hand, this is a far less common facility, and
> order matters, so maybe more verbose names are fine.
>

I'm sorry to bring more bikeshedding, but lexicographicallyEqual seems
absolutely atrocious to me. Imagine all the steps required the user of a
Set to understand why a lexicographicallyEqual function is suggested
by the compiler ??

Since you seem to give the kind of answer i'm looking for, do you have any
answer to a previous question i asked regarding the rational for conflating
the iterator with the collection ?
What i mean by that is : i think nobody would have cared if the syntax for
Set was actually
set1.iterator.elementEquals(set2.iterator)
It's a bit more verbose, but the meaning is obvious.
I think a reason why people are confused is that the actual design
conflates methods of the "iterator" on the collection type itself. An
alternate design would have been to make collection Sequence*able *rather
than a sequence themselves. But i suppose you've thought about that
already, so i'm just curious to know what made you choose the current
solution instead.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

(I saw this after I sent my reply to Benjamin G). We can also deprecate it or 
warn when the type is concretely known to be Set. Not a total solution, but 
it’s nice to catch some bugs.

> On Oct 17, 2017, at 1:21 PM, Manolo van Ee  wrote:
> 
> 
> On Tue, 17 Oct 2017 at 21:00, Jonathan Hull via swift-evolution 
> > wrote:
> 
>> On Oct 17, 2017, at 11:47 AM, Michael Ilseman via swift-evolution 
>> > wrote:
>> 
>> `==` conveys substitutability of the two Sequences. This does not 
>> necessarily entail anything about their elements, how those elements are 
>> ordered, etc., it just means two Sequences are substitutable. 
>> `elementsEqual` means that the two Sequences produce substitutable elements. 
>> These are different concepts and both are independently useful.
> 
> I agree that ‘==‘ conveys substitutability.  Here is the issue:
> 
>   let a = Set([1,2,3,4,5])
>   let b = Set([5,4,3,2,1])
> 
>   a == b //True, they are substitutable
> 
>   [1,2,3,4,5].elementsEqual(a) //True
>   [1,2,3,4,5].elementsEqual(b) //False… I guess they weren’t actually 
> substitutable after all
> 
> 
> Thanks,
> Jon
> ___
> swift-evolution mailing list
> swift-evolution@swift.org 
> https://lists.swift.org/mailman/listinfo/swift-evolution 
> 
> 
> I read along with most of the thread and like to add one thing. Maybe it’s 
> not the right way to look at things, but I see protocol extensions as being 
> part of any type that conforms to the protocol. As it is now, code completion 
> on a Set will present me with the elementsEqual function, which in my view is 
> misleading, since it cannot be used in any useful way with a Set.
> 
> By renaming elementsEqual we might be able to make it less misleading, but it 
> will always be a useless function that is part of the Set namespace (or 
> Dictionary for that matter).
> 
> I don’t know what the best solution would be, but to me it feels like 
> distinguishing between Iterable and Sequence, or Ordered and Unordered makes 
> sense, and it might be good to at least investigate what the impact would be.
> 
> Regards,
> /Manolo
> 
> 
> 
> 

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 17, 2017, at 12:54 PM, Benjamin G  wrote:
> 
> Thanks for the post, that's the first clear explanation i see on this thread 
> for the concepts behind the design for Sequence.
> 
> I am a bit afraid that understanding all that is a bit above what to expect 
> the average swift developer will guess when he sees functions like "prefix / 
> first / elementEqual (or whatever it's called)" on the Set type.
> There is, IMHO, a much higher chance he'll either : 
> 1/ not understand anything, or 
> 2/ think Sets are in fact secretely ordered sets, or start writing generic 
> extensions above Sequence or Collection thinking those protocols are 
> synonymous for orderer collections.
> 
> 1/ is pretty harmless, but 2/ seems like a source of bug.
> 
> My personal opinion after reading all this is that we should simply change 
> the name

Exactly, and that’s what Xiaodi’s proposal does. Confronted with these 
complexities, his proposal reasons that a name change is the lessor or evils, 
as in the “Proposed solution” section.

> to sequentiallyEquals

Xiaodi floated “lexicographicallyEqual” which is accurate and a big 
improvement, and I’m liking it more and more. I floated “sequentiallyEquals”, 
which I’m liking less and less now. My current preference is for 
“elementsOrderedEqual” which I think is more descriptive but unwieldy. On the 
other hand, this is a far less common facility, and order matters, so maybe 
more verbose names are fine.

As you can tell, I’m pretty wishy-washy with names and probably should abstain 
from bike shedding anything important ;-)


> (just because it let people hint at where this function comes from, and not 
> let them believe that it's something native to the Set type), and not touch 
> anything else, until maybe we someday have a way to make everything perfect 
> for everyone.
> 

We can ease the pain a bit. E.g. warnings/deprecation when the type is 
concretely known to be Set, etc. Not a general solution, but might fight some 
bugs.

I think that of all the dichotomies we fail to model in our protocol hierarchy, 
the ordered vs unordered is the least useful to accommodate. It is, however, 
easy and fun to bike shed.


> On Tue, Oct 17, 2017 at 8:47 PM, Michael Ilseman via swift-evolution 
> > wrote:
> 
> 
>> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>> > wrote:
>> 
>>> Because, in my analysis, the problem is that the method is incorrectly 
>>> named. The problem affects all types that conform to Sequence and not just 
>>> Set and Dictionary; elementsEqual is a distinct function from ==, and it 
>>> must either continue to be distinct or cease to exist, but its name does 
>>> nothing to clarify any distinction.
>> 
>> In my analysis, the problem is the method's implementation. As I see it, the 
>> only use for `elementsEqual` is as a replacement for `==` when two objects 
>> are different types (or not known to be the same)—equal elements, and IF the 
>> sequences have an order, in the same order. Could you provide an example 
>> where `elementsEqual` randomly returning either true or false depending on 
>> internal state alone is a legitimate and desirable result?
>> 
> 
> It doesn’t randomly return true or false, it consistently returns true or 
> false for the *same* pair of Sequences. What *same* means, of course, is 
> complicated and exists at two levels (as we have two ways of talking about 
> *same*). 
> 
> I apologize for not reading every email in depth in this thread (they are 
> coming in faster than I can parse them), but let me try to present motivation 
> for this and hopefully provide more shared understanding.
> 
> We have two forms of equality we’re talking about: equality of Sequence and 
> equality of the elements of Sequences in their respective ordering. `==` 
> covers the former, and I’ll use the existing (harmful) name of 
> `elementsEqual` for the latter.
> 
> `==` conveys substitutability of the two Sequences. This does not necessarily 
> entail anything about their elements, how those elements are ordered, etc., 
> it just means two Sequences are substitutable. `elementsEqual` means that the 
> two Sequences produce substitutable elements. These are different concepts 
> and both are independently useful.
> 
> Cases:
> 
> 1. Two Sequences are substitutable and produce substitutable elements when 
> iterated. `==` and `elementsEqual` both return true. 
> 
> Example: Two arrays with the same elements in the same order.
> 
> 
> 2. Two Sequences are substitutable, but do not produce substitutable elements 
> when iterated. `==` returns true, while `elementsEqual` returns false.
> 
> Example: Two Sets that contain the same elements but in a different order.
> 
> Contrived Example: Two Lorem Ipsum generators are the same generator 
> (referentially equal, substitutable for the 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Manolo van Ee via swift-evolution]

On Tue, 17 Oct 2017 at 21:00, Jonathan Hull via swift-evolution <
swift-evolution@swift.org> wrote:

>
> On Oct 17, 2017, at 11:47 AM, Michael Ilseman via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> `==` conveys substitutability of the two Sequences. This does not
> necessarily entail anything about their elements, how those elements are
> ordered, etc., it just means two Sequences are substitutable.
> `elementsEqual` means that the two Sequences produce substitutable
> elements. These are different concepts and both are independently useful.
>
>
> I agree that ‘==‘ conveys substitutability.  Here is the issue:
>
> let a = Set([1,2,3,4,5])
> let b = Set([5,4,3,2,1])
>
> a == b //True, they are substitutable
>
> [1,2,3,4,5].elementsEqual(a) //True
> [1,2,3,4,5].elementsEqual(b) //False… I guess they weren’t actually
> substitutable after all
>
>
> Thanks,
> Jon
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

I read along with most of the thread and like to add one thing. Maybe it’s
not the right way to look at things, but I see protocol extensions as being
part of any type that conforms to the protocol. As it is now, code
completion on a Set will present me with the elementsEqual function, which
in my view is misleading, since it cannot be used in any useful way with a
Set.

By renaming elementsEqual we might be able to make it less misleading, but
it will always be a useless function that is part of the Set namespace (or
Dictionary for that matter).

I don’t know what the best solution would be, but to me it feels like
distinguishing between Iterable and Sequence, or Ordered and Unordered
makes sense, and it might be good to at least investigate what the impact
would be.

Regards,
/Manolo
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

>>> 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.
> 
> Just because a hack is commonly accepted or common doesn’t mean it isn’t a 
> hack.
> 
> It’s not a “hack.” NaN is required by IEEE fiat not to be equivalent to 
> itself. Asking whether a value is reflexively equivalent to itself is 
> guaranteed to be sufficient to detect the presence of NaN in all 
> IEEE-compliant contexts, which is to say all past, present, and future 
> versions of Swift.

- while `a.elementsEqual(a)` returning true precludes the presence of a nan, 
returning false is not a guarantee there is a NaN—at least the way you have 
insist this method should work. The isNaN version is correct in all cases.
- It's a great deal less readable and obvious than the `where { $0.isNaN }` 
version, so while the term "hack" is arguably not correct (assuming you only 
need to disprove a NaN and not prove one exists), it is certainly not the most 
readable way.
- IEEE says Float.nan == Float.nan must be false; I'm pretty sure the IEEE spec 
doesn't say anything about how Swift Sequences must implement `elementsEqual`.

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

But HashSet does implement IEnumerable, and therefore you can still call 
SequenceEqual on it. .Net does not distinguish between ordered and unordered 
enumerables. Random access is a different concept than enumerability.

> On Oct 17, 2017, at 12:48 PM, Jonathan Hull via swift-evolution 
>  wrote:
> 
> Also of interest to this discussion is the following from a discussion on 
> C#’s version of Set:
> 
>> HashSet is more or less modeled after a mathematical set 
>> , which means that:
>> 
>> It may contain no duplicate values.
>> Its elements are in no particular order; therefore the type does not 
>> implement the IList 
>> interface, but the 
>> more basic ICollection 
>> . As a consequence, 
>> elements inside a hash set cannot be randomly accessed through indices; they 
>> can only be iterated over through an enumerator.
> So, it appears that C#/.Net does in fact take into account the fact that Sets 
> are unordered, and only allows it to be iterated (as opposed to accessed with 
> indices).
> 
> Thanks,
> Jon
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Benjamin G via swift-evolution]

Thanks for the post, that's the first clear explanation i see on this
thread for the concepts behind the design for Sequence.

I am a bit afraid that understanding all that is a bit above what to expect
the average swift developer will guess when he sees functions like "prefix
/ first / elementEqual (or whatever it's called)" on the Set type.
There is, IMHO, a much higher chance he'll either :
1/ not understand anything, or
2/ think Sets are in fact secretely ordered sets, or start writing generic
extensions above Sequence or Collection thinking those protocols are
synonymous for orderer collections.

1/ is pretty harmless, but 2/ seems like a source of bug.

My personal opinion after reading all this is that we should simply change
the name to sequentiallyEquals (just because it let people hint at where
this function comes from, and not let them believe that it's something
native to the Set type), and not touch anything else, until maybe we
someday have a way to make everything perfect for everyone.

On Tue, Oct 17, 2017 at 8:47 PM, Michael Ilseman via swift-evolution <
swift-evolution@swift.org> wrote:

>
>
> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Because, in my analysis, the problem is that the method is incorrectly
> named. The problem affects all types that conform to Sequence and not just
> Set and Dictionary; elementsEqual is a distinct function from ==, and it
> must either continue to be distinct or cease to exist, but its name does
> nothing to clarify any distinction.
>
>
> In my analysis, the problem is the method's implementation. As I see it,
> the only use for `elementsEqual` is as a replacement for `==` when two
> objects are different types (or not known to be the same)—equal elements,
> and IF the sequences have an order, in the same order. Could you provide an
> example where `elementsEqual` randomly returning either true or false
> depending on internal state alone is a legitimate and desirable result?
>
>
> It doesn’t randomly return true or false, it consistently returns true or
> false for the *same* pair of Sequences. What *same* means, of course, is
> complicated and exists at two levels (as we have two ways of talking about
> *same*).
>
> I apologize for not reading every email in depth in this thread (they are
> coming in faster than I can parse them), but let me try to present
> motivation for this and hopefully provide more shared understanding.
>
> We have two forms of equality we’re talking about: equality of Sequence
> and equality of the elements of Sequences in their respective ordering.
> `==` covers the former, and I’ll use the existing (harmful) name of
> `elementsEqual` for the latter.
>
> `==` conveys substitutability of the two Sequences. This does not
> necessarily entail anything about their elements, how those elements are
> ordered, etc., it just means two Sequences are substitutable.
> `elementsEqual` means that the two Sequences produce substitutable
> elements. These are different concepts and both are independently useful.
>
> Cases:
>
> 1. Two Sequences are substitutable and produce substitutable elements when
> iterated. `==` and `elementsEqual` both return true.
>
> Example: Two arrays with the same elements in the same order.
>
>
> 2. Two Sequences are substitutable, but do not produce substitutable
> elements when iterated. `==` returns true, while `elementsEqual` returns
> false.
>
> Example: Two Sets that contain the same elements but in a different order.
>
> Contrived Example: Two Lorem Ipsum generators are the same generator
> (referentially equal, substitutable for the purposes of my library), but
> they sample the user’s current battery level (global state) each time they
> produce text to decide how fancy to make the faux Latin. They’re
> substitutable, but don’t generate the same sequence.
>
>
> 3. Two Sequences are not substitutable, but produce substitutable elements
> when iterated. `==` returns false, while `elementsEqual` returns true.
>
> Example: Consider two sequences that have differing identity. `==`
> operates on an identity level, `elementsEqual` operates at an element level.
>
> Contrived Example: InfiniteMonkeys and Shakespeare both produce the same
> sonnet, but they’re not substitutable for my library’s purposes.
>
>
> 4. Two Sequences are not substitutable and don’t produce substitutable
> elements when iterated. `==` and `elementsEqual` both return false.
>
> Example: `[1,2,3]` compared to `[4,5,6]`
>
>
> It is true that situations #2 and #3 are a little harder to grok, but they
> are what illustrate the subtle difference at hand. I think situation #2 is
> the most confusing, and has been the primary focus of this thread as Set
> exists and exhibits it.
>
>
> Now, onto naming. `elementsEqual` is a very poor choice of name for the
> concept of equality of elements in their respective orderings, as it
> doesn’t highlight the “in their respective orderings” 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

Also of interest to this discussion is the following from a discussion on C#’s 
version of Set:

> HashSet is more or less modeled after a mathematical set 
> , which means that:
> 
> It may contain no duplicate values.
> Its elements are in no particular order; therefore the type does not 
> implement the IList 
> interface, but the 
> more basic ICollection 
> . As a consequence, 
> elements inside a hash set cannot be randomly accessed through indices; they 
> can only be iterated over through an enumerator.
So, it appears that C#/.Net does in fact take into account the fact that Sets 
are unordered, and only allows it to be iterated (as opposed to accessed with 
indices).

Thanks,
Jon___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 17, 2017, at 11:46 AM, Xiaodi Wu  wrote:
> 
> 
> On Tue, Oct 17, 2017 at 12:54 Jonathan Hull  > wrote:
>> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu > > wrote:
>> 
>> 
>> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull > > wrote:
>>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu >> > wrote:
>>> 
>>> 
>>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz >> > wrote:
>>> 
>>> 
>>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu >> >:
>>> 
 
 On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz > wrote:
> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
> >:
> 
> 
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  > wrote:
> 
>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu > > wrote:
>> 
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull > > wrote:
>> 
>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu >> > 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.
 
 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 17, 2017, at 11:47 AM, Michael Ilseman via swift-evolution 
>  wrote:
> 
> `==` conveys substitutability of the two Sequences. This does not necessarily 
> entail anything about their elements, how those elements are ordered, etc., 
> it just means two Sequences are substitutable. `elementsEqual` means that the 
> two Sequences produce substitutable elements. These are different concepts 
> and both are independently useful.

I agree that ‘==‘ conveys substitutability.  Here is the issue:

let a = Set([1,2,3,4,5])
let b = Set([5,4,3,2,1])

a == b //True, they are substitutable

[1,2,3,4,5].elementsEqual(a) //True
[1,2,3,4,5].elementsEqual(b) //False… I guess they weren’t actually 
substitutable after all


Thanks,
Jon___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 17, 2017, at 10:15 AM, Kevin Nattinger via swift-evolution 
>  wrote:
> 
>> Because, in my analysis, the problem is that the method is incorrectly 
>> named. The problem affects all types that conform to Sequence and not just 
>> Set and Dictionary; elementsEqual is a distinct function from ==, and it 
>> must either continue to be distinct or cease to exist, but its name does 
>> nothing to clarify any distinction.
> 
> In my analysis, the problem is the method's implementation. As I see it, the 
> only use for `elementsEqual` is as a replacement for `==` when two objects 
> are different types (or not known to be the same)—equal elements, and IF the 
> sequences have an order, in the same order. Could you provide an example 
> where `elementsEqual` randomly returning either true or false depending on 
> internal state alone is a legitimate and desirable result?
> 

It doesn’t randomly return true or false, it consistently returns true or false 
for the *same* pair of Sequences. What *same* means, of course, is complicated 
and exists at two levels (as we have two ways of talking about *same*). 

I apologize for not reading every email in depth in this thread (they are 
coming in faster than I can parse them), but let me try to present motivation 
for this and hopefully provide more shared understanding.

We have two forms of equality we’re talking about: equality of Sequence and 
equality of the elements of Sequences in their respective ordering. `==` covers 
the former, and I’ll use the existing (harmful) name of `elementsEqual` for the 
latter.

`==` conveys substitutability of the two Sequences. This does not necessarily 
entail anything about their elements, how those elements are ordered, etc., it 
just means two Sequences are substitutable. `elementsEqual` means that the two 
Sequences produce substitutable elements. These are different concepts and both 
are independently useful.

Cases:

1. Two Sequences are substitutable and produce substitutable elements when 
iterated. `==` and `elementsEqual` both return true. 

Example: Two arrays with the same elements in the same order.


2. Two Sequences are substitutable, but do not produce substitutable elements 
when iterated. `==` returns true, while `elementsEqual` returns false.

Example: Two Sets that contain the same elements but in a different order.

Contrived Example: Two Lorem Ipsum generators are the same generator 
(referentially equal, substitutable for the purposes of my library), but they 
sample the user’s current battery level (global state) each time they produce 
text to decide how fancy to make the faux Latin. They’re substitutable, but 
don’t generate the same sequence.


3. Two Sequences are not substitutable, but produce substitutable elements when 
iterated. `==` returns false, while `elementsEqual` returns true.

Example: Consider two sequences that have differing identity. `==` operates on 
an identity level, `elementsEqual` operates at an element level.

Contrived Example: InfiniteMonkeys and Shakespeare both produce the same 
sonnet, but they’re not substitutable for my library’s purposes. 


4. Two Sequences are not substitutable and don’t produce substitutable elements 
when iterated. `==` and `elementsEqual` both return false.

Example: `[1,2,3]` compared to `[4,5,6]`


It is true that situations #2 and #3 are a little harder to grok, but they are 
what illustrate the subtle difference at hand. I think situation #2 is the most 
confusing, and has been the primary focus of this thread as Set exists and 
exhibits it.


Now, onto naming. `elementsEqual` is a very poor choice of name for the concept 
of equality of elements in their respective orderings, as it doesn’t highlight 
the “in their respective orderings” part. `lexicographicallyEqual` highlights 
the ordering much better, as “abc” is not lexicographically equal to “cba” 
despite having equal elements. I think it is clearly an improvement over the 
status quo. I like something a little more explicit (e.g. 
`elementsOrderedEqual`), personally, but I don’t care that strongly. I’m just 
glad to see `elementsEqual` getting some clarification.




>> 
>> Thanks,
>> Jon
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 12:54 Jonathan Hull  wrote:

> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu  wrote:
>
>
> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull  wrote:
>
>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu  wrote:
>>
>>
>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz  wrote:
>>
>>>
>>>
>>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu :
>>>
>>>
>>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz 
>>> wrote:
>>>
 Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution <
 swift-evolution@swift.org>:


 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:

>
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>
> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>
>>
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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, 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 17, 2017, at 11:20 AM, Kevin Nattinger  wrote:
> 
> Hmm, I'm not sure that would work with the covariant requirement. The 
> associated type one could:
> func firstNames(ofPeople people: U) -> 
> U.MapResultType {
>   return people.map { $0.firstName }
> }
> 
> If the sequence you put in maps to an ordered sequence, you get the ordered 
> sequence out. 
> That said, I can see how the generics there could get out-of-hand as you add 
> more operations… -> U.MapResultType.FilterResultType.MapResultType… String>

Even in the simple case this leaks an implementation detail (that we’re using 
map) into the signature.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 17, 2017, at 10:41 AM, Kevin Nattinger via swift-evolution 
>  wrote:
> 
>> On Oct 17, 2017, at 10:36 AM, Adam Kemp > > wrote:
>> 
>> 
>>> On Oct 17, 2017, at 10:00 AM, Kevin Nattinger >> > wrote:
>>> 
>>> Once we allow covariant functions to satisfy protocol requirements and have 
>>> generalized existentials and recursive protocol requirements, wouldn't we 
>>> be able to update thusly:
>>> 
>>> protocol Unordered {
>>> func map(…) -> Any
>>> }
>>> protocol Ordered: Unordered {
>>> func map(…) -> Any
>>> }
>>> 
>> 
>> Now apply that to every order-preserving function that takes a Sequence and 
>> returns another Sequence. You’ve moved the burden from users of API to 
>> implementers of API. It reminds me of the const/non-const split that C++ 
>> developers have to deal with, where a lot of functions end up being 
>> implemented twice so that you can have a const version and a non-const 
>> version (generally one just calls the other). It’s a pain. I don’t want that 
>> when working with Sequences. I don’t think it’s worth it. And FWIW, when I 
>> was programming in C# I wrote functions that took an IEnumerable and 
>> return another IEnumerable very often. It’s a powerful feature that would 
>> have been ruined by a change like this.
> 
> The idea is that covariance would mean you only need to implement the 
> function once.

In the example you showed above map is written twice. Maybe the two protocols 
can share an implementation, but you still have to have two versions declared 
somewhere.

What does it look like if you’re just writing a single function somewhere that 
takes in a Sequence and returns another Sequence? How do you make that function 
take both ordered and unordered Sequences? To make it concrete, say you write a 
function that just wraps map:

func firstNames(ofPeople people: Sequence) -> Sequence {
return people.map { $0.firstName }
}

I want that function to work on both ordered and unordered Sequences, and if 
you start with an ordered Sequence you should end up with an ordered Sequence. 
How do I make that work?

> If there are no real-world problems, why do we feel the need to change the 
> function name in the first place?

To quote myself from an earlier email: "I’m not even sure a name change is 
necessary for this method at all, but I’m not at all in favor of anything 
beyond that.”

To extend that, I’m content with doing nothing. I’m not sure there’s cause for 
doing anything at all, and I’m very sure that no one on this list has 
demonstrated any need for a major change to the library, let alone new language 
features.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu  wrote:
> 
> 
> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull  > wrote:
>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu > > wrote:
>> 
>> 
>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz > > wrote:
>> 
>> 
>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu > >:
>> 
>>> 
>>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz >> > wrote:
 Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
 >:
 
 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull > wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  > wrote:
> 
> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  > wrote:
> 
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu > > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 17, 2017, at 10:36 AM, Adam Kemp  wrote:
> 
> 
>> On Oct 17, 2017, at 10:00 AM, Kevin Nattinger > > wrote:
>> 
>> Once we allow covariant functions to satisfy protocol requirements and have 
>> generalized existentials and recursive protocol requirements, wouldn't we be 
>> able to update thusly:
>> 
>> protocol Unordered {
>>  func map(…) -> Any
>> }
>> protocol Ordered: Unordered {
>>  func map(…) -> Any
>> }
>> 
> 
> Now apply that to every order-preserving function that takes a Sequence and 
> returns another Sequence. You’ve moved the burden from users of API to 
> implementers of API. It reminds me of the const/non-const split that C++ 
> developers have to deal with, where a lot of functions end up being 
> implemented twice so that you can have a const version and a non-const 
> version (generally one just calls the other). It’s a pain. I don’t want that 
> when working with Sequences. I don’t think it’s worth it. And FWIW, when I 
> was programming in C# I wrote functions that took an IEnumerable and 
> return another IEnumerable very often. It’s a powerful feature that would 
> have been ruined by a change like this.

The idea is that covariance would mean you only need to implement the function 
once.

> 
>> As I've been saying all along, elementsEqual returning a functionally random 
>> result when an unordered type is involved is a problem.
> 
> In theory. Where is the evidence that this leads to a significant number of 
> real-world bugs? All you’ve done is describe a conceptual problem, but you 
> haven’t connected the dots to real-world problems. Again, I can point to 
> .Net, which has a much larger community of developers who have been working 
> with the same “problem” since version 2.0 released in 2005. If this is a 
> significant source of bugs then there should be evidence of that. Where is 
> that evidence?

If there are no real-world problems, why do we feel the need to change the 
function name in the first place?

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 17, 2017, at 10:00 AM, Kevin Nattinger  wrote:
> 
> Once we allow covariant functions to satisfy protocol requirements and have 
> generalized existentials and recursive protocol requirements, wouldn't we be 
> able to update thusly:
> 
> protocol Unordered {
>   func map(…) -> Any
> }
> protocol Ordered: Unordered {
>   func map(…) -> Any
> }
> 

Now apply that to every order-preserving function that takes a Sequence and 
returns another Sequence. You’ve moved the burden from users of API to 
implementers of API. It reminds me of the const/non-const split that C++ 
developers have to deal with, where a lot of functions end up being implemented 
twice so that you can have a const version and a non-const version (generally 
one just calls the other). It’s a pain. I don’t want that when working with 
Sequences. I don’t think it’s worth it. And FWIW, when I was programming in C# 
I wrote functions that took an IEnumerable and return another IEnumerable 
very often. It’s a powerful feature that would have been ruined by a change 
like this.

> As I've been saying all along, elementsEqual returning a functionally random 
> result when an unordered type is involved is a problem.

In theory. Where is the evidence that this leads to a significant number of 
real-world bugs? All you’ve done is describe a conceptual problem, but you 
haven’t connected the dots to real-world problems. Again, I can point to .Net, 
which has a much larger community of developers who have been working with the 
same “problem” since version 2.0 released in 2005. If this is a significant 
source of bugs then there should be evidence of that. Where is that evidence?___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 17, 2017, at 9:34 AM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> 
> On Tue, Oct 17, 2017 at 09:42 Jonathan Hull  > wrote:
>> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu > > wrote:
>> 
>> 
>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz > > wrote:
>> 
>> 
>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu > >:
>> 
>>> 
>>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz >> > wrote:
 Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
 >:
 
 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull > wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  > wrote:
> 
> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  > wrote:
> 
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu > > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 16, 2017, at 1:29 PM, Adam Kemp via swift-evolution 
>  wrote:
> 
> 
> 
>> On Oct 16, 2017, at 12:35 PM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>> IMHO `elementsEqual` provides a nice example for a method which only makes 
>> sense on something meaningfully ordered:
>> What is the use case for `elementsEqual` that works with a Set?
> 
> There may not be one, but here’s the problem:
> 
> 1. It’s generally useful for Set to conform to a protocol that allows you to 
> iterate over its elements.
> 2. It’s generally useful to be able to ask if two objects that you can 
> iterate over are equal by comparing the elements in the order that they’re 
> iterated over.
> 
> The argument being made is that these two protocols should be different, but 
> I don’t think the proponents of that idea have fully thought through what 
> that would mean in practice. Consider a function like map, which takes a 
> Sequence and produces another Sequence. This function is useful for both 
> ordered and unordered elements so it would have to be defined in terms of the 
> looser (unordered) type, which means its output type would be unordered. 
> Imagine starting with an ordered enumerable and calling map on it. What’s the 
> result? An unordered enumerable (the return type of map would be unordered to 
> match its input type). Now you can’t use any of the methods that require the 
> stricter (ordered) protocol on the result, even though you haven’t actually 
> lost the order. You would have to do something to fix up the type and make 
> the compiler see it as ordered again. Maybe there’s an asOrdered method or 
> something. Imagine having to sprinkle that throughout your code just to make 
> things compile. Does that sound like a usable API?
> 
> 
> let people:[Person] = [] // Ordered
> let orderedNames:[String] = [] // Ordered
> let names = people.map { $0.fullName } // Result is unordered
> return names.elementsEqual(orderedNames) // compile error: names is unordered
> // Maybe: return names.asOrdered().elementsEqual(orderedNames)?
> 
> Avoiding this mess would require overloading such that every function that 
> supports either ordered or unordered would have to be written both ways, 
> which would just be a different mess.

That is a great point. Once we allow covariant functions to satisfy protocol 
requirements and have generalized existentials and recursive protocol 
requirements, wouldn't we be able to update thusly:

protocol Unordered {
func map(…) -> Any
}
protocol Ordered: Unordered {
func map(…) -> Any
}

?

Or the following; it also requires generalized existentials and recursive 
protocol requirements but not covariance; though I can imagine people arguing 
against introducing more associated types:
 
protocol Unordered {
associatedtype MapResultType: Unordered
func map(…) -> Any
}

This would even allow an ordered collection to map to an unordered one or 
vice-versa.  Maybe a collection type that spits out an ordered list when 
mapping to Comparables.
(n.b. the more I think about it, the more I like this option. Where are our 
existentials and recursive requirements? :) )

In this case we wouldn't even need an Ordered override; using concrete classes 
directly it would just work, and a function that requires an ordered result 
could specify it as any other constraint just as you do today:

func foo(in seq: O) where O.Element == Int, O.MapResultType: 
Ordered {
let orderedMapping = seq.map { $0 + 1 } // type = Any
…
}

I'd be ok with `map` and `filter` keeping their array returns (and that's 
what's in my original email about this) until we get the language features 
needed to support these. And I think we'd want to revisit the definitions of 
much of what is currently Sequence once we get these language features anyway.

> 
> All of that would be to solve a problem that in practice doesn’t seem to 
> really cause any problems. I’m not aware of any evidence to suggest that this 
> type causes a significant number of bugs, and we have another 
> language/runtime (C#/.Net) with a large number of active developers and code 
> bases with the same design and the same lack of evidence of a problem.

As I've been saying all along, elementsEqual returning a functionally random 
result when an unordered type is involved is a problem. At the least, we should 
make an OrderedSequence (conforming to Sequence, but could even be otherwise 
empty), move at least elementsEqual and lexicographicallyPrecedes to functions 
or extensions on that, and conform the appropriate stdlib types. Which would 
obviously not include Set or Dictionary. 

> It seems like we’re being asked to make the library significantly harder to 
> work with in order to solve a set of bugs that, as far as I can tell, doesn’t 
> really exist in practice. I think in order to even consider this we would 
> need to see 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> Because, in my analysis, the problem is that the method is incorrectly named. 
> The problem affects all types that conform to Sequence and not just Set and 
> Dictionary; elementsEqual is a distinct function from ==, and it must either 
> continue to be distinct or cease to exist, but its name does nothing to 
> clarify any distinction.

In my analysis, the problem is the method's implementation. As I see it, the 
only use for `elementsEqual` is as a replacement for `==` when two objects are 
different types (or not known to be the same)—equal elements, and IF the 
sequences have an order, in the same order. Could you provide an example where 
`elementsEqual` randomly returning either true or false depending on internal 
state alone is a legitimate and desirable result?

> 
> Thanks,
> Jon
> ___
> swift-evolution mailing list
> swift-evolution@swift.org 
> https://lists.swift.org/mailman/listinfo/swift-evolution 
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 16, 2017, at 11:06 PM, Thorsten Seitz  wrote:
> 
> The new language features (which are sorely needed anyway) are not necessary 
> for the proposed solution of splitting the protocol. They are necessary to 
> fix or improve the definition of map which is currently lacking as well 
> because it always returns an Array.
> Alternatively we can continue to live with that. This is a separate question.

The language change would be necessary to avoid to consequences I described if 
you split the protocol. If there are other benefits to that feature then that’s 
not relevant to this discussion. The point is whether the proposed world where 
Sequence is split into two protocols would be practical to use, and your 
suggestion for how to make it work was to add a feature to the language.

I’m not sure how that hypothetical feature relates to the current return type 
of map being an array. C# doesn’t have your feature, and yet Select takes an 
IEnumerable and returns IEnumerable. I think the fact that Swift’s map 
returns an array instead of a Sequence has more to do with other library design 
decisions. As far as I can tell there’s no reason it couldn’t have been the 
same as .Net with the current type system.

Your proposal, on the other hand, would require a new type system feature not 
present in either Swift or C# just to make it tolerable, and I still haven’t 
seen anyone in this long thread lay out any evidence of a real problem being 
solved.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 11:01 Thorsten Seitz  wrote:

>
>
> Am 17.10.2017 um 14:46 schrieb Xiaodi Wu :
>
> On Tue, Oct 17, 2017 at 01:03 Thorsten Seitz  wrote:
>
>>
>>
>> Am 17.10.2017 um 01:43 schrieb Xiaodi Wu via swift-evolution <
>> swift-evolution@swift.org>:
>>
>> On Mon, Oct 16, 2017 at 6:10 PM, Jonathan Hull  wrote:
>>
>>>
>>> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>>>
>>>
>>> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
>>>

 On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:

 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 that iteration order is undefined and could easily change due to
 changes in the private/internal structure of sets/dictionaries.  Algorithms
 that rely on that “publicly observable behavior” (i.e. leaking of
 internals) will suddenly break.

>>>
>>> And an algorithm in which such “sudden breakage” would occur is…?
>>>
>>>
>>> Here are a few off the top of my head:
>>>
>>> func hasPrefix(Sequence)->Bool
>>> func hasSuffix(Sequence)->Bool
>>> func containsSubsequence(Sequence)->Bool
>>>
>>> What do these methods mean with regards to Set’s “publicly observable
>>> behavior”?
>>>
>>
>> In what way do these algorithms break? They would continue to
>> determine--correctly--whether an instance of Set, when iterated, begins
>> with, ends with, or contains (respectively) a subsequence that matches the
>> argument.
>>
>>
>> Why do you not answe the question, what these methods *mean* for a Set?
>> Still waiting for a use case.
>>
>
> The method means exactly what I just said: the iteration order of one set
> matches the iteration order of another sequence. I’ve given you one use
> case and others have given more.
>
>
> Sorry, the use case you gave was just a clever trick instead of using
> `contains` and Float.isNaN. No one else has provided a use case for
> `elementsEqual` yet.
>

The purpose of protocols is to enable useful generic code. You cannot use
isNaN in generic code that operates on Collection (or even Set where
Element : Numeric) to prevent NaN from blowing up your sort. Comparing a
value to itself is not a “clever trick” but a common and ordinary method of
checking for NaN.


> -Thorsten
>
>
>
>
>> -Thorsten
>>
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 09:42 Jonathan Hull  wrote:

> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu  wrote:
>
>
> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz  wrote:
>
>>
>>
>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu :
>>
>>
>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz  wrote:
>>
>>> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution <
>>> swift-evolution@swift.org>:
>>>
>>>
>>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>>>

 On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:

 On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:

>
> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 14:46 schrieb Xiaodi Wu :
> 
>> On Tue, Oct 17, 2017 at 01:03 Thorsten Seitz  wrote:
>> 
>> 
>>> Am 17.10.2017 um 01:43 schrieb Xiaodi Wu via swift-evolution 
>>> :
>>> 
 On Mon, Oct 16, 2017 at 6:10 PM, Jonathan Hull  wrote:
 
> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
> 
> 
>> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
>> 
 On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
 
 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 that iteration order is undefined and could easily change due to 
>> changes in the private/internal structure of sets/dictionaries.  
>> Algorithms that rely on that “publicly observable behavior” (i.e. 
>> leaking of internals) will suddenly break.
> 
> And an algorithm in which such “sudden breakage” would occur is…?
 
 Here are a few off the top of my head:
 
 func hasPrefix(Sequence)->Bool
 func hasSuffix(Sequence)->Bool
 func containsSubsequence(Sequence)->Bool
 
 What do these methods mean with regards to Set’s “publicly observable 
 behavior”?
>>> 
>>> In what way do these algorithms break? They would continue to 
>>> determine--correctly--whether an instance of Set, when iterated, begins 
>>> with, ends with, or contains (respectively) a subsequence that matches the 
>>> argument.
>> 
>> Why do you not answe the question, what these methods *mean* for a Set?
>> Still waiting for a use case.
> 
> The method means exactly what I just said: the iteration order of one set 
> matches the iteration order of another sequence. I’ve given you one use case 
> and others have given more.

Sorry, the use case you gave was just a clever trick instead of using 
`contains` and Float.isNaN. No one else has provided a use case for 
`elementsEqual` yet.

-Thorsten


> 
>> 
>> -Thorsten
>> 
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 14:44 schrieb Xiaodi Wu :
> 
> 
>> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz  wrote:
>> 
>> 
>>> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu :
>>> 
>>> 
>>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz  wrote:
> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
> :
> 
> 
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>> 
>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>> 
 On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
 
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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.
>> 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

Hi Gwendal, these are use cases for using indices as unordered references which 
certainly are useful. I was looking for use cases depending on the order 
exposed by Sequence, specifically use cases for elementsEqual.

-Thorsten 

> Am 17.10.2017 um 09:03 schrieb Gwendal Roué :
> 
>>> Modeling is, by definition, imperfect. The question is, what imperfect 
>>> model is most useful _to Swift_. The idea is that conforming Set and 
>>> Dictionary to Collection is on balance more useful than not doing so; that 
>>> having two protocols, Sequence and Collection, is on balance more useful 
>>> than having one or three, and that the set of semantic guarantees of 
>>> Collection are on balance more useful than other possible sets of semantic 
>>> guarantees.
>> 
>> That is your idea which is disputed and underlined with arguments whereas 
>> you keep repeating that Set behaves as dictated by its conformance without 
>> giving use cases why this should be useful.
> 
> Hello,
> 
> You can't *control* the ordering of a set or a dictionary, but you can still 
> *rely* on it.
> 
> For example, to find a key in a dictionary that is associated a given value, 
> you can rely on the fact that a dictionary's order is guaranteed to be 
> stable, and that on top of that its indexes can address the dictionary 
> itself, but also its keys and values sequences. The code below has no bug;
> 
> let dict = ["a": "foo", "b": "bar", "c": "needle"]
> 
> // Find a key associated with "needle"
> if let index = dict.values.index(of: "needle") {
> let key = dict.keys[index]
> print(key) // prints "c"
> }
> 
> It's more difficult to find a use case for set's ordering and indexes. But 
> since you ask, here is an example. The goal is to find any element which is 
> not equal to another value, in any collection:
> 
> extension Collection where Element: Equatable {
> /// Returns any element which is not equal to the given element
> func anyElement(notEqualTo v: Element) -> Element? {
> if let i = index(of: v) {
> if let alt = index(i, offsetBy: 1, limitedBy: endIndex), alt != 
> endIndex {
> return self[alt]
> }
> if i == startIndex {
> return nil
> }
> return first
> }
> return first
> }
> }
> 
> Set([1, 2, 3]).anyElement(notEqualTo: 1) // 2 or 3
> Set([1, 2]).anyElement(notEqualTo: 1)// 2
> Set([1]).anyElement(notEqualTo: 1)   // nil
> Set([2]).anyElement(notEqualTo: 1)   // 2
> Set([]).anyElement(notEqualTo: 1)// nil
> 
> That *can* be useful, isn't it?
> 
> Gwendal Roué
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 17, 2017, at 5:44 AM, Xiaodi Wu  wrote:
> 
> 
> On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz  > wrote:
> 
> 
> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu  >:
> 
>> 
>> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz > > wrote:
>>> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
>>> >:
>>> 
>>> 
>>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull >> > wrote:
>>> 
 On Oct 15, 2017, at 9:58 PM, Xiaodi Wu > wrote:
 
 On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull > wrote:
 
> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 01:24 Thorsten Seitz  wrote:

>
>
> Am 17.10.2017 um 03:20 schrieb Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org>:
>
> On Mon, Oct 16, 2017 at 8:03 PM, David Sweeris 
> wrote:
>
>>
>> On Oct 16, 2017, at 1:07 PM, Xiaodi Wu  wrote:
>>
>>
>> On Mon, Oct 16, 2017 at 13:15 David Sweeris  wrote:
>>
>>>
>>> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
>>>
>>>
>>>
>>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution <
>>> swift-evolution@swift.org> wrote:
>>>
>>>
>>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution <
>>> swift-evolution@swift.org> wrote:
>>>
>>>
>>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>>>

 On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:

 On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:

>
> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 01:03 Thorsten Seitz  wrote:

>
>
> Am 17.10.2017 um 01:43 schrieb Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org>:
>
> On Mon, Oct 16, 2017 at 6:10 PM, Jonathan Hull  wrote:
>
>>
>> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>>
>>
>> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
>>
>>>
>>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>>>
>>> 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 that iteration order is undefined and could easily change due to
>>> changes in the private/internal structure of sets/dictionaries.  Algorithms
>>> that rely on that “publicly observable behavior” (i.e. leaking of
>>> internals) will suddenly break.
>>>
>>
>> And an algorithm in which such “sudden breakage” would occur is…?
>>
>>
>> Here are a few off the top of my head:
>>
>> func hasPrefix(Sequence)->Bool
>> func hasSuffix(Sequence)->Bool
>> func containsSubsequence(Sequence)->Bool
>>
>> What do these methods mean with regards to Set’s “publicly observable
>> behavior”?
>>
>
> In what way do these algorithms break? They would continue to
> determine--correctly--whether an instance of Set, when iterated, begins
> with, ends with, or contains (respectively) a subsequence that matches the
> argument.
>
>
> Why do you not answe the question, what these methods *mean* for a Set?
> Still waiting for a use case.
>

The method means exactly what I just said: the iteration order of one set
matches the iteration order of another sequence. I’ve given you one use
case and others have given more.


> -Thorsten
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Tue, Oct 17, 2017 at 00:56 Thorsten Seitz  wrote:

>
>
> Am 17.10.2017 um 00:13 schrieb Xiaodi Wu :
>
>
> On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz  wrote:
>
>> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution <
>> swift-evolution@swift.org>:
>>
>>
>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>>
>>>
>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>>
>>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>>>

 On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Martin R via swift-evolution]

> On 17. Oct 2017, at 09:48, Jonathan Hull via swift-evolution 
>  wrote:
> 
> 
>> On Oct 17, 2017, at 12:04 AM, Gwendal Roué via swift-evolution 
>>  wrote:
>> 
 Modeling is, by definition, imperfect. The question is, what imperfect 
 model is most useful _to Swift_. The idea is that conforming Set and 
 Dictionary to Collection is on balance more useful than not doing so; that 
 having two protocols, Sequence and Collection, is on balance more useful 
 than having one or three, and that the set of semantic guarantees of 
 Collection are on balance more useful than other possible sets of semantic 
 guarantees.
>>> 
>>> That is your idea which is disputed and underlined with arguments whereas 
>>> you keep repeating that Set behaves as dictated by its conformance without 
>>> giving use cases why this should be useful.
>> 
>> Hello,
>> 
>> You can't *control* the ordering of a set or a dictionary, but you can still 
>> *rely* on it.
>> 
>> For example, to find a key in a dictionary that is associated a given value, 
>> you can rely on the fact that a dictionary's order is guaranteed to be 
>> stable, and that on top of that its indexes can address the dictionary 
>> itself, but also its keys and values sequences. The code below has no bug;
>> 
>> let dict = ["a": "foo", "b": "bar", "c": "needle"]
>> 
>> // Find a key associated with "needle"
>> if let index = dict.values.index(of: "needle") {
>> let key = dict.keys[index]
>> print(key) // prints "c"
>> }
> 
> You are using the index from one collection to index into another collection. 
>  Isn’t that something the documentation explicitly tells us not to do?  Or is 
> there a special (documented) guarantee that these collections will always 
> sync indices?

The documentation of Dictionary.values states that

"When iterated over, values appear in this collection in the same order as they 
occur in the dictionary’s key-value pairs."

and similarly for Dictionary.keys. So that should be safe, as I understand it.

Martin

> 
> I guess you could do:
> 
>   if let key = dict.first(where {$1 == “needle}).0 {
>   print(key)
>   }
> 
> …although note that which element is “first” if there are multiple keys with 
> needle as the value may shift around on you as you mess with the dictionary 
> (and also on separate runs even if you don’t mess with the dictionary).
> 
>> It's more difficult to find a use case for set's ordering and indexes. But 
>> since you ask, here is an example. The goal is to find any element which is 
>> not equal to another value, in any collection:
>> 
>> extension Collection where Element: Equatable {
>> /// Returns any element which is not equal to the given element
>> func anyElement(notEqualTo v: Element) -> Element? {
>> if let i = index(of: v) {
>> if let alt = index(i, offsetBy: 1, limitedBy: endIndex), alt != 
>> endIndex {
>> return self[alt]
>> }
>> if i == startIndex {
>> return nil
>> }
>> return first
>> }
>> return first
>> }
>> }
>> 
>> Set([1, 2, 3]).anyElement(notEqualTo: 1) // 2 or 3
>> Set([1, 2]).anyElement(notEqualTo: 1)// 2
>> Set([1]).anyElement(notEqualTo: 1)   // nil
>> Set([2]).anyElement(notEqualTo: 1)   // 2
>> Set([]).anyElement(notEqualTo: 1)// nil
>> 
>> That *can* be useful, isn't it?
> 
> Yes, although this could easily be provided using iteration without indexing.
> 
> 
> Note that my current favorite solution is to simply provide an additional 
> guarantee on set/dictionary that the iteration order will always be the same 
> for the same contents (regardless of history), but the order would still be 
> otherwise arbitrary.  That is a non-source-breaking change (renaming IS 
> source breaking).  It won’t fix everything, but it will fix some of the 
> biggest gotchas.  As a bonus, elementsEqual will 'just work'™ for 
> sets/dictionaries. 
> 
> Thanks,
> Jon
> 
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 17, 2017, at 12:04 AM, Gwendal Roué via swift-evolution 
>  wrote:
> 
>>> Modeling is, by definition, imperfect. The question is, what imperfect 
>>> model is most useful _to Swift_. The idea is that conforming Set and 
>>> Dictionary to Collection is on balance more useful than not doing so; that 
>>> having two protocols, Sequence and Collection, is on balance more useful 
>>> than having one or three, and that the set of semantic guarantees of 
>>> Collection are on balance more useful than other possible sets of semantic 
>>> guarantees.
>> 
>> That is your idea which is disputed and underlined with arguments whereas 
>> you keep repeating that Set behaves as dictated by its conformance without 
>> giving use cases why this should be useful.
> 
> Hello,
> 
> You can't *control* the ordering of a set or a dictionary, but you can still 
> *rely* on it.
> 
> For example, to find a key in a dictionary that is associated a given value, 
> you can rely on the fact that a dictionary's order is guaranteed to be 
> stable, and that on top of that its indexes can address the dictionary 
> itself, but also its keys and values sequences. The code below has no bug;
> 
> let dict = ["a": "foo", "b": "bar", "c": "needle"]
> 
> // Find a key associated with "needle"
> if let index = dict.values.index(of: "needle") {
> let key = dict.keys[index]
> print(key) // prints "c"
> }

You are using the index from one collection to index into another collection.  
Isn’t that something the documentation explicitly tells us not to do?  Or is 
there a special (documented) guarantee that these collections will always sync 
indices?

I guess you could do:

if let key = dict.first(where {$1 == “needle}).0 {
print(key)
}

…although note that which element is “first” if there are multiple keys with 
needle as the value may shift around on you as you mess with the dictionary 
(and also on separate runs even if you don’t mess with the dictionary).

> It's more difficult to find a use case for set's ordering and indexes. But 
> since you ask, here is an example. The goal is to find any element which is 
> not equal to another value, in any collection:
> 
> extension Collection where Element: Equatable {
> /// Returns any element which is not equal to the given element
> func anyElement(notEqualTo v: Element) -> Element? {
> if let i = index(of: v) {
> if let alt = index(i, offsetBy: 1, limitedBy: endIndex), alt != 
> endIndex {
> return self[alt]
> }
> if i == startIndex {
> return nil
> }
> return first
> }
> return first
> }
> }
> 
> Set([1, 2, 3]).anyElement(notEqualTo: 1) // 2 or 3
> Set([1, 2]).anyElement(notEqualTo: 1)// 2
> Set([1]).anyElement(notEqualTo: 1)   // nil
> Set([2]).anyElement(notEqualTo: 1)   // 2
> Set([]).anyElement(notEqualTo: 1)// nil
> 
> That *can* be useful, isn't it?

Yes, although this could easily be provided using iteration without indexing.


Note that my current favorite solution is to simply provide an additional 
guarantee on set/dictionary that the iteration order will always be the same 
for the same contents (regardless of history), but the order would still be 
otherwise arbitrary.  That is a non-source-breaking change (renaming IS source 
breaking).  It won’t fix everything, but it will fix some of the biggest 
gotchas.  As a bonus, elementsEqual will 'just work'™ for sets/dictionaries. 

Thanks,
Jon


___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Gwendal Roué via swift-evolution]

Oops, I apologize for the buggy implementation of the 
Collection.anyElement(notEqualTo:) method I did provide.

My point was just to show that there are useful generic algorithms that can use 
the observable ordering of sets and dictionaries, despite the fact that those 
ordering can not be controlled by the programmer.

Gwendal

> Le 17 oct. 2017 à 09:03, Gwendal Roué via swift-evolution 
>  a écrit :
> 
>>> Modeling is, by definition, imperfect. The question is, what imperfect 
>>> model is most useful _to Swift_. The idea is that conforming Set and 
>>> Dictionary to Collection is on balance more useful than not doing so; that 
>>> having two protocols, Sequence and Collection, is on balance more useful 
>>> than having one or three, and that the set of semantic guarantees of 
>>> Collection are on balance more useful than other possible sets of semantic 
>>> guarantees.
>> 
>> That is your idea which is disputed and underlined with arguments whereas 
>> you keep repeating that Set behaves as dictated by its conformance without 
>> giving use cases why this should be useful.
> 
> Hello,
> 
> You can't *control* the ordering of a set or a dictionary, but you can still 
> *rely* on it.
> 
> For example, to find a key in a dictionary that is associated a given value, 
> you can rely on the fact that a dictionary's order is guaranteed to be 
> stable, and that on top of that its indexes can address the dictionary 
> itself, but also its keys and values sequences. The code below has no bug;
> 
> let dict = ["a": "foo", "b": "bar", "c": "needle"]
> 
> // Find a key associated with "needle"
> if let index = dict.values.index(of: "needle") {
> let key = dict.keys[index]
> print(key) // prints "c"
> }
> 
> It's more difficult to find a use case for set's ordering and indexes. But 
> since you ask, here is an example. The goal is to find any element which is 
> not equal to another value, in any collection:
> 
> extension Collection where Element: Equatable {
> /// Returns any element which is not equal to the given element
> func anyElement(notEqualTo v: Element) -> Element? {
> if let i = index(of: v) {
> if let alt = index(i, offsetBy: 1, limitedBy: endIndex), alt != 
> endIndex {
> return self[alt]
> }
> if i == startIndex {
> return nil
> }
> return first
> }
> return first
> }
> }
> 
> Set([1, 2, 3]).anyElement(notEqualTo: 1) // 2 or 3
> Set([1, 2]).anyElement(notEqualTo: 1)// 2
> Set([1]).anyElement(notEqualTo: 1)   // nil
> Set([2]).anyElement(notEqualTo: 1)   // 2
> Set([]).anyElement(notEqualTo: 1)// nil
> 
> That *can* be useful, isn't it?
> 
> Gwendal Roué
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Gwendal Roué via swift-evolution]

>> Modeling is, by definition, imperfect. The question is, what imperfect model 
>> is most useful _to Swift_. The idea is that conforming Set and Dictionary to 
>> Collection is on balance more useful than not doing so; that having two 
>> protocols, Sequence and Collection, is on balance more useful than having 
>> one or three, and that the set of semantic guarantees of Collection are on 
>> balance more useful than other possible sets of semantic guarantees.
> 
> That is your idea which is disputed and underlined with arguments whereas you 
> keep repeating that Set behaves as dictated by its conformance without giving 
> use cases why this should be useful.

Hello,

You can't *control* the ordering of a set or a dictionary, but you can still 
*rely* on it.

For example, to find a key in a dictionary that is associated a given value, 
you can rely on the fact that a dictionary's order is guaranteed to be stable, 
and that on top of that its indexes can address the dictionary itself, but also 
its keys and values sequences. The code below has no bug;

let dict = ["a": "foo", "b": "bar", "c": "needle"]

// Find a key associated with "needle"
if let index = dict.values.index(of: "needle") {
let key = dict.keys[index]
print(key) // prints "c"
}

It's more difficult to find a use case for set's ordering and indexes. But 
since you ask, here is an example. The goal is to find any element which is not 
equal to another value, in any collection:

extension Collection where Element: Equatable {
/// Returns any element which is not equal to the given element
func anyElement(notEqualTo v: Element) -> Element? {
if let i = index(of: v) {
if let alt = index(i, offsetBy: 1, limitedBy: endIndex), alt != 
endIndex {
return self[alt]
}
if i == startIndex {
return nil
}
return first
}
return first
}
}

Set([1, 2, 3]).anyElement(notEqualTo: 1) // 2 or 3
Set([1, 2]).anyElement(notEqualTo: 1)// 2
Set([1]).anyElement(notEqualTo: 1)   // nil
Set([2]).anyElement(notEqualTo: 1)   // 2
Set([]).anyElement(notEqualTo: 1)// nil

That *can* be useful, isn't it?

Gwendal Roué

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 03:20 schrieb Xiaodi Wu via swift-evolution 
> :
> 
>> On Mon, Oct 16, 2017 at 8:03 PM, David Sweeris  wrote:
>> 
>>> On Oct 16, 2017, at 1:07 PM, Xiaodi Wu  wrote:
>>> 
>>> 
 On Mon, Oct 16, 2017 at 13:15 David Sweeris  wrote:
 
> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
> 
> 
> 
>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution 
>>  wrote:
>> 
>> 
>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution 
>>  wrote:
>> 
>>> 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
> 
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  
>> wrote:
>> 
 On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  
 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 00:15 schrieb Adam Kemp :
> 
> 
>>> On Oct 16, 2017, at 3:08 PM, Thorsten Seitz  wrote:
>>> 
>>> 2. It’s generally useful to be able to ask if two objects that you can 
>>> iterate over are equal by comparing the elements in the order that they’re 
>>> iterated over.
>> 
>> Here I disagree. This operation only makes sense if the iteration order has 
>> underlying well defined semantics. Otherwise the result of that operation 
>> will be a random value, depending on the undefined order. I argue that this 
>> is never useful. That is why I am asking for a use case for that.
> 
> I deliberately didn’t specify in either of these cases whether the thing was 
> ordered or not. I’m not disputing that this only makes sense for ordered 
> things. I’m merely pointing out that making that distinction is impractical 
> for other reasons.
> 
>> There are several solutions for this, e.g. covariant redefinition of the 
>> result type to be ordered in an ordered subclass, or more sophisticated 
>> solutions which could even allow to chose the result type if required to be 
>> different from a default.
>> The latter would allow e.g. mapping over a Set to commonly result in a 
>> generic Iterable but in some cases it might also result in another Set. The 
>> same holds for mapping over an ordered collection like an Array. The result 
>> might commonly be an array but it might also be a Set or something else.
>> Swift currently lacks the necessary capabilities in the type system to 
>> achieve this, though, so we would have to stay with the current solution 
>> that `map` always returns an Array (at least for the moment) — which already 
>> is not very satisfactory in itself.
> 
> Now you’re inventing new language features in order to support your proposed 
> solution to a problem that I still have seen no evidence to support being a 
> significant source of real bugs. And those new language features would still 
> result in a library and language that is harder to use than before. This is 
> not a convincing argument for making a change.

The new language features (which are sorely needed anyway) are not necessary 
for the proposed solution of splitting the protocol. They are necessary to fix 
or improve the definition of map which is currently lacking as well because it 
always returns an Array.
Alternatively we can continue to live with that. This is a separate question.

-Thorsten___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 17.10.2017 um 01:43 schrieb Xiaodi Wu via swift-evolution 
> :
> 
>> On Mon, Oct 16, 2017 at 6:10 PM, Jonathan Hull  wrote:
>> 
>>> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>>> 
>>> 
 On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
 
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>> 
>> 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 that iteration order is undefined and could easily change due to 
 changes in the private/internal structure of sets/dictionaries.  
 Algorithms that rely on that “publicly observable behavior” (i.e. leaking 
 of internals) will suddenly break.
>>> 
>>> And an algorithm in which such “sudden breakage” would occur is…?
>> 
>> Here are a few off the top of my head:
>> 
>> func hasPrefix(Sequence)->Bool
>> func hasSuffix(Sequence)->Bool
>> func containsSubsequence(Sequence)->Bool
>> 
>> What do these methods mean with regards to Set’s “publicly observable 
>> behavior”?
> 
> In what way do these algorithms break? They would continue to 
> determine--correctly--whether an instance of Set, when iterated, begins with, 
> ends with, or contains (respectively) a subsequence that matches the argument.

Why do you not answe the question, what these methods *mean* for a Set?
Still waiting for a use case.

-Thorsten

> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

Even worse, Set([5,4,3,2,1]) will probably return false although it contains 
the same elements.

-Thorsten


> Am 17.10.2017 um 01:40 schrieb Jonathan Hull via swift-evolution 
> :
> 
> To expand on this, Set([1,2,3,4,5]).hasPrefix([1,2,3]) currently returns 
> true.  But let’s say a year from now, we change Set to return an ordering 
> based on hash values (which is entirely reasonable). Suddenly the same code 
> may return true or false. 
> 
> No guarantees will be broken by doing that, but the result has still changed 
> because we are building on top of undefined behavior. Collection says nothing 
> about the ordering over different builds of a program.
> 
> Thanks,
> Jon
> 
>>> On Oct 16, 2017, at 4:11 PM, Jonathan Hull via swift-evolution 
>>>  wrote:
>>> 
>>> 
>>> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>>> 
>>> 
 On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
 
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>> 
>> 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 that iteration order is undefined and could easily change due to 
 changes in the private/internal structure of sets/dictionaries.  
 Algorithms that rely on that “publicly observable behavior” (i.e. leaking 
 of internals) will suddenly break.
>>> 
>>> And an algorithm in which such “sudden breakage” would occur is…?
>> 
>> Here are a few off the top of my head:
>> 
>> func hasPrefix(Sequence)->Bool
>> func hasSuffix(Sequence)->Bool
>> func containsSubsequence(Sequence)->Bool
>> 
>> What do these methods mean with regards to Set’s “publicly observable 
>> behavior”?
>> 
>>> 
 You keep claiming that this bug is a feature because it is the current 
 behavior… but that is tautological reasoning.
 
 Thanks,
 Jon
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 8:03 PM, David Sweeris  wrote:

>
> On Oct 16, 2017, at 1:07 PM, Xiaodi Wu  wrote:
>
>
> On Mon, Oct 16, 2017 at 13:15 David Sweeris  wrote:
>
>>
>> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
>>
>>
>>
>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>>
>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>>
>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>>
>>>
>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>>
>>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>>>

 On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 16, 2017, at 1:07 PM, Xiaodi Wu  wrote:
> 
> 
> On Mon, Oct 16, 2017 at 13:15 David Sweeris  > wrote:
> 
> On Oct 16, 2017, at 09:21, Michael Ilseman  > wrote:
> 
>> 
>> 
>>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution 
>>> > wrote:
>>> 
>>> 
>>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution 
>>> > wrote:
>>> 
 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull > wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  > wrote:
> 
> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  > wrote:
> 
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu > > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Howard Lovatt via swift-evolution]

My preferences in order would be:

  1. Split out of Sequence Iterable/ForEachable (whatever the name) and
have Set and Dictionary conform to this new protocol instead of Sequence.
With further protocols splits made to other 'mixin' protocols to keep the
order of iteration undefined.

  2. Rename elementsEqual, iterableOrderEqual and change the definitions of
all the order dependent methods in the 'collections' hierarchy to
explicitly say "based on iteration order" and to explicitly say that "the
method iterates over the collection to produce their result and if the
collection can only iterate once then subsequent calls will cause a fatal
error".

There is only one reason that I can see for rejecting my 1st option - it's
just too much effort. I don't accept the argument of a breaking change in
the true sense of the word breaking because algorithms over Set/Dictionary
that rely on order are broken and there explicitly cause a compile time
error for these is good. Arguing that it isn't good to deliberately break
these algorithms is like saying that if there is a bug in the compiler that
accepts faulty code we shouldn't fix it because that will break someones
code - no a bug should be flagged.

  -- Howard.

On 17 October 2017 at 10:40, Jonathan Hull via swift-evolution <
swift-evolution@swift.org> wrote:

> To expand on this, Set([1,2,3,4,5]).hasPrefix([1,2,3]) currently returns
> true.  But let’s say a year from now, we change Set to return an ordering
> based on hash values (which is entirely reasonable). Suddenly the same code
> may return true or false.
>
> No guarantees will be broken by doing that, but the result has still
> changed because we are building on top of undefined behavior. Collection
> says nothing about the ordering over different builds of a program.
>
> Thanks,
> Jon
>
> On Oct 16, 2017, at 4:11 PM, Jonathan Hull via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>
>
> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
>
>>
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>>
>> 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 that iteration order is undefined and could easily change due to
>> changes in the private/internal structure of sets/dictionaries.  Algorithms
>> that rely on that “publicly observable behavior” (i.e. leaking of
>> internals) will suddenly break.
>>
>
> And an algorithm in which such “sudden breakage” would occur is…?
>
>
> Here are a few off the top of my head:
>
> func hasPrefix(Sequence)->Bool
> func hasSuffix(Sequence)->Bool
> func containsSubsequence(Sequence)->Bool
>
> What do these methods mean with regards to Set’s “publicly observable
> behavior”?
>
>
> You keep claiming that this bug is a feature because it is the current
>> behavior… but that is tautological reasoning.
>>
>> Thanks,
>> Jon
>>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 6:40 PM, Jonathan Hull  wrote:

> To expand on this, Set([1,2,3,4,5]).hasPrefix([1,2,3]) currently returns
> true.  But let’s say a year from now, we change Set to return an ordering
> based on hash values (which is entirely reasonable). Suddenly the same code
> may return true or false.
>
> No guarantees will be broken by doing that, but the result has still
> changed because we are building on top of undefined behavior. Collection
> says nothing about the ordering over different builds of a program.
>

So that's not breakage. Results are allowed to change; `hasPrefix` should
change if the iteration order changes, and the iteration order is allowed
to change over different builds. Just like how the memory layout is allowed
to change, or anything else not explicitly guaranteed by public API
semantics is allowed to change.

On Oct 16, 2017, at 4:11 PM, Jonathan Hull via swift-evolution <
swift-evolution@swift.org> wrote:


On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:


On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:

>
> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>
> 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 that iteration order is undefined and could easily change due to
> changes in the private/internal structure of sets/dictionaries.  Algorithms
> that rely on that “publicly observable behavior” (i.e. leaking of
> internals) will suddenly break.
>

And an algorithm in which such “sudden breakage” would occur is…?


Here are a few off the top of my head:

func hasPrefix(Sequence)->Bool
func hasSuffix(Sequence)->Bool
func containsSubsequence(Sequence)->Bool

What do these methods mean with regards to Set’s “publicly observable
behavior”?


You keep claiming that this bug is a feature because it is the current
> behavior… but that is tautological reasoning.
>
> Thanks,
> Jon
>

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 6:10 PM, Jonathan Hull  wrote:

>
> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
>
>
> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:
>
>>
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>>
>> 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 that iteration order is undefined and could easily change due to
>> changes in the private/internal structure of sets/dictionaries.  Algorithms
>> that rely on that “publicly observable behavior” (i.e. leaking of
>> internals) will suddenly break.
>>
>
> And an algorithm in which such “sudden breakage” would occur is…?
>
>
> Here are a few off the top of my head:
>
> func hasPrefix(Sequence)->Bool
> func hasSuffix(Sequence)->Bool
> func containsSubsequence(Sequence)->Bool
>
> What do these methods mean with regards to Set’s “publicly observable
> behavior”?
>

In what way do these algorithms break? They would continue to
determine--correctly--whether an instance of Set, when iterated, begins
with, ends with, or contains (respectively) a subsequence that matches the
argument.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

To expand on this, Set([1,2,3,4,5]).hasPrefix([1,2,3]) currently returns true.  
But let’s say a year from now, we change Set to return an ordering based on 
hash values (which is entirely reasonable). Suddenly the same code may return 
true or false. 

No guarantees will be broken by doing that, but the result has still changed 
because we are building on top of undefined behavior. Collection says nothing 
about the ordering over different builds of a program.

Thanks,
Jon

> On Oct 16, 2017, at 4:11 PM, Jonathan Hull via swift-evolution 
>  wrote:
> 
>> 
>> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu > > wrote:
>> 
>> 
>> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull > > wrote:
>> 
>>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu >> > wrote:
>>> 
>>> 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 that iteration order is undefined and could easily change due to changes 
>> in the private/internal structure of sets/dictionaries.  Algorithms that 
>> rely on that “publicly observable behavior” (i.e. leaking of internals) will 
>> suddenly break.
>> 
>> And an algorithm in which such “sudden breakage” would occur is…?
> 
> Here are a few off the top of my head:
> 
> func hasPrefix(Sequence)->Bool
> func hasSuffix(Sequence)->Bool
> func containsSubsequence(Sequence)->Bool
> 
> What do these methods mean with regards to Set’s “publicly observable 
> behavior”?
> 
>> 
>> You keep claiming that this bug is a feature because it is the current 
>> behavior… but that is tautological reasoning.
>> 
>> Thanks,
>> Jon
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org 
> https://lists.swift.org/mailman/listinfo/swift-evolution 
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Jonathan Hull via swift-evolution]

> On Oct 16, 2017, at 1:05 PM, Xiaodi Wu  wrote:
> 
> 
> On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  > wrote:
> 
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu > > wrote:
>> 
>> 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 that iteration order is undefined and could easily change due to changes 
> in the private/internal structure of sets/dictionaries.  Algorithms that rely 
> on that “publicly observable behavior” (i.e. leaking of internals) will 
> suddenly break.
> 
> And an algorithm in which such “sudden breakage” would occur is…?

Here are a few off the top of my head:

func hasPrefix(Sequence)->Bool
func hasSuffix(Sequence)->Bool
func containsSubsequence(Sequence)->Bool

What do these methods mean with regards to Set’s “publicly observable behavior”?

> 
> You keep claiming that this bug is a feature because it is the current 
> behavior… but that is tautological reasoning.
> 
> Thanks,
> Jon

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 15:31 Greg Parker  wrote:

> On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> On Mon, Oct 16, 2017 at 13:15 David Sweeris  wrote:
>
>
>> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
>>
>>
>> Sets are values. If you add, remove, or mutate any elements you have a
>> different Set and thus a potentially different ordering of elements.
>>
>>
>> From the “value semantics” PoV, yes. But from the “unordered collection
>> of values” PoV, Sets/Dictionaries, being unordered, are semantically free
>> to rearrange the in-memory ordering of their elements *without* user
>> intervention.
>>
>
> No, they are not semantically free to do so. The semantics of Collection
> forbid it, because the iteration order must be multi-pass. As long as the
> value is unchanged, the iteration order is unchanged. That is a documented,
> public guarantee of the API.
>
>
> Even if a Set value has a fixed order, a copy of that value may have a
> *different* order. How many generic algorithm implementations are going to
> be confused by that?
>

Is that so? That would be, on reflection, either a hole in the semantic
guarantees of Collection itself or a problematic conformance of Set to
Collection.

Some months ago, Dave A. and others sent out a draft about some refinements
to `Equatable`. There, we enunciated the notion that `==` should compare
equivalence in all "salient" respects, but not necessarily all publicly
observable behaviors. This is why, for instance, it is semantically
acceptable that `+0.0 == -0.0`; we are declaring that the sign of zero is
not a "salient" respect for the purposes of equivalence of floating point
types. However, this relaxed notion of equivalence/substitutability
*cannot* be acceptable for the purposes of copying a value. Take, for
instance:

```
func f(x: T) {
  print(x)
}

print(-0.0) // It is *not OK* if this prints "+0.0".
```

To my simplistic thinking, a copy of an instance of a value type must be
indistinguishable from the original value with respect to all public APIs
(with the only and obvious exception of APIs that inquire into memory
location/layout). When Collection guarantees that conforming types are
multi-pass sequences, it *ought* to guarantee (if it does not do so already
on a proper interpretation of the semantic requirements) that copies are
indistinguishable in iteration order. If it did not do so, then so many
non-trivial algorithms that already operate on generic Collections are
assuming semantics that aren't guaranteed and would in fact pervasively
blow up when given a specially crafted but conformant Collection. This
would apply whether or not Sequence and Collection are modified to exclude
Set and Dictionary, as an "intrinsically ordered" collection type may not
have an intrinsic *linear* order over its elements, and there is no
semantic requirement that the *iteration order* (necessarily linear)
corresponds in any particular way to the "intrinsic order."

Now, if we agree that Collection does in fact (or ought to) guarantee the
stability of iteration order over copies, then the question is, does
today's `Swift.Set` properly meet those guarantees? If indeed, as you say,
copies of an instance of `Set` may internally rearrange its iteration order
on copy, then we do have a problem with the conformance of `Set` to
`Collection`.


>
> --
> Greg Parker gpar...@apple.com Runtime Wrangler
>
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 16, 2017, at 3:08 PM, Thorsten Seitz  wrote:
> 
>> 2. It’s generally useful to be able to ask if two objects that you can 
>> iterate over are equal by comparing the elements in the order that they’re 
>> iterated over.
> 
> Here I disagree. This operation only makes sense if the iteration order has 
> underlying well defined semantics. Otherwise the result of that operation 
> will be a random value, depending on the undefined order. I argue that this 
> is never useful. That is why I am asking for a use case for that.

I deliberately didn’t specify in either of these cases whether the thing was 
ordered or not. I’m not disputing that this only makes sense for ordered 
things. I’m merely pointing out that making that distinction is impractical for 
other reasons.

> There are several solutions for this, e.g. covariant redefinition of the 
> result type to be ordered in an ordered subclass, or more sophisticated 
> solutions which could even allow to chose the result type if required to be 
> different from a default.
> The latter would allow e.g. mapping over a Set to commonly result in a 
> generic Iterable but in some cases it might also result in another Set. The 
> same holds for mapping over an ordered collection like an Array. The result 
> might commonly be an array but it might also be a Set or something else.
> Swift currently lacks the necessary capabilities in the type system to 
> achieve this, though, so we would have to stay with the current solution that 
> `map` always returns an Array (at least for the moment) — which already is 
> not very satisfactory in itself.

Now you’re inventing new language features in order to support your proposed 
solution to a problem that I still have seen no evidence to support being a 
significant source of real bugs. And those new language features would still 
result in a library and language that is harder to use than before. This is not 
a convincing argument for making a change.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 14:21 Thorsten Seitz  wrote:

> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org>:
>
>
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>
>>
>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>>
>>>
>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 16.10.2017 um 22:29 schrieb Adam Kemp :
> 
> 
> 
>> On Oct 16, 2017, at 12:35 PM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>> IMHO `elementsEqual` provides a nice example for a method which only makes 
>> sense on something meaningfully ordered:
>> What is the use case for `elementsEqual` that works with a Set?
> 
> There may not be one, but here’s the problem:
> 
> 1. It’s generally useful for Set to conform to a protocol that allows you to 
> iterate over its elements.

Absolutely. There is no dispute about that.


> 2. It’s generally useful to be able to ask if two objects that you can 
> iterate over are equal by comparing the elements in the order that they’re 
> iterated over.

Here I disagree. This operation only makes sense if the iteration order has 
underlying well defined semantics. Otherwise the result of that operation will 
be a random value, depending on the undefined order. I argue that this is never 
useful. That is why I am asking for a use case for that.


> 
> The argument being made is that these two protocols should be different, but 
> I don’t think the proponents of that idea have fully thought through what 
> that would mean in practice. Consider a function like map, which takes a 
> Sequence and produces another Sequence. This function is useful for both 
> ordered and unordered elements so it would have to be defined in terms of the 
> looser (unordered) type, which means its output type would be unordered. 
> Imagine starting with an ordered enumerable and calling map on it. What’s the 
> result? An unordered enumerable (the return type of map would be unordered to 
> match its input type).

Good point. There are several solutions for this, e.g. covariant redefinition 
of the result type to be ordered in an ordered subclass, or more sophisticated 
solutions which could even allow to chose the result type if required to be 
different from a default.
The latter would allow e.g. mapping over a Set to commonly result in a generic 
Iterable but in some cases it might also result in another Set. The same holds 
for mapping over an ordered collection like an Array. The result might commonly 
be an array but it might also be a Set or something else.
Swift currently lacks the necessary capabilities in the type system to achieve 
this, though, so we would have to stay with the current solution that `map` 
always returns an Array (at least for the moment) — which already is not very 
satisfactory in itself.

-Thorsten


> Now you can’t use any of the methods that require the stricter (ordered) 
> protocol on the result, even though you haven’t actually lost the order. You 
> would have to do something to fix up the type and make the compiler see it as 
> ordered again. Maybe there’s an asOrdered method or something. Imagine having 
> to sprinkle that throughout your code just to make things compile. Does that 
> sound like a usable API?
> 
> 
> let people:[Person] = [] // Ordered
> let orderedNames:[String] = [] // Ordered
> let names = people.map { $0.fullName } // Result is unordered
> return names.elementsEqual(orderedNames) // compile error: names is unordered
> // Maybe: return names.asOrdered().elementsEqual(orderedNames)?
> 
> Avoiding this mess would require overloading such that every function that 
> supports either ordered or unordered would have to be written both ways, 
> which would just be a different mess.
> 
> All of that would be to solve a problem that in practice doesn’t seem to 
> really cause any problems. I’m not aware of any evidence to suggest that this 
> type causes a significant number of bugs, and we have another 
> language/runtime (C#/.Net) with a large number of active developers and code 
> bases with the same design and the same lack of evidence of a problem.
> 
> It seems like we’re being asked to make the library significantly harder to 
> work with in order to solve a set of bugs that, as far as I can tell, doesn’t 
> really exist in practice. I think in order to even consider this we would 
> need to see the evidence that there’s a real problem to solve, and see a 
> solution that didn’t make the library significantly harder to use.

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Greg Parker via swift-evolution]

> On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> On Mon, Oct 16, 2017 at 13:15 David Sweeris  > wrote:
> 
> On Oct 16, 2017, at 09:21, Michael Ilseman  > wrote:
>> 
>> Sets are values. If you add, remove, or mutate any elements you have a 
>> different Set and thus a potentially different ordering of elements.
> 
> From the “value semantics” PoV, yes. But from the “unordered collection of 
> values” PoV, Sets/Dictionaries, being unordered, are semantically free to 
> rearrange the in-memory ordering of their elements without user intervention.
> 
> No, they are not semantically free to do so. The semantics of Collection 
> forbid it, because the iteration order must be multi-pass. As long as the 
> value is unchanged, the iteration order is unchanged. That is a documented, 
> public guarantee of the API.

Even if a Set value has a fixed order, a copy of that value may have a 
*different* order. How many generic algorithm implementations are going to be 
confused by that?


-- 
Greg Parker gpar...@apple.com  Runtime 
Wrangler


___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Adam Kemp via swift-evolution]

> On Oct 16, 2017, at 12:35 PM, Thorsten Seitz via swift-evolution 
>  wrote:
> 
> IMHO `elementsEqual` provides a nice example for a method which only makes 
> sense on something meaningfully ordered:
> What is the use case for `elementsEqual` that works with a Set?

There may not be one, but here’s the problem:

1. It’s generally useful for Set to conform to a protocol that allows you to 
iterate over its elements.
2. It’s generally useful to be able to ask if two objects that you can iterate 
over are equal by comparing the elements in the order that they’re iterated 
over.

The argument being made is that these two protocols should be different, but I 
don’t think the proponents of that idea have fully thought through what that 
would mean in practice. Consider a function like map, which takes a Sequence 
and produces another Sequence. This function is useful for both ordered and 
unordered elements so it would have to be defined in terms of the looser 
(unordered) type, which means its output type would be unordered. Imagine 
starting with an ordered enumerable and calling map on it. What’s the result? 
An unordered enumerable (the return type of map would be unordered to match its 
input type). Now you can’t use any of the methods that require the stricter 
(ordered) protocol on the result, even though you haven’t actually lost the 
order. You would have to do something to fix up the type and make the compiler 
see it as ordered again. Maybe there’s an asOrdered method or something. 
Imagine having to sprinkle that throughout your code just to make things 
compile. Does that sound like a usable API?


let people:[Person] = [] // Ordered
let orderedNames:[String] = [] // Ordered
let names = people.map { $0.fullName } // Result is unordered
return names.elementsEqual(orderedNames) // compile error: names is unordered
// Maybe: return names.asOrdered().elementsEqual(orderedNames)?

Avoiding this mess would require overloading such that every function that 
supports either ordered or unordered would have to be written both ways, which 
would just be a different mess.

All of that would be to solve a problem that in practice doesn’t seem to really 
cause any problems. I’m not aware of any evidence to suggest that this type 
causes a significant number of bugs, and we have another language/runtime 
(C#/.Net) with a large number of active developers and code bases with the same 
design and the same lack of evidence of a problem.

It seems like we’re being asked to make the library significantly harder to 
work with in order to solve a set of bugs that, as far as I can tell, doesn’t 
really exist in practice. I think in order to even consider this we would need 
to see the evidence that there’s a real problem to solve, and see a solution 
that didn’t make the library significantly harder to use.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> 
> On Mon, Oct 16, 2017 at 13:15 David Sweeris  > wrote:
> 
> On Oct 16, 2017, at 09:21, Michael Ilseman  > wrote:
> 
>> 
>> 
>>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution 
>>> > wrote:
>>> 
>>> 
>>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution 
>>> > wrote:
>>> 
 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull > wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  > wrote:
> 
> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  > wrote:
> 
>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu > > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 13:15 David Sweeris  wrote:

>
> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
>
>
>
> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
>
>>
>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
>>
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>>
>>>
>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 10:49 Jonathan Hull  wrote:

>
> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu  wrote:
>
> 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 that iteration order is undefined and could easily change due to
> changes in the private/internal structure of sets/dictionaries.  Algorithms
> that rely on that “publicly observable behavior” (i.e. leaking of
> internals) will suddenly break.
>

And an algorithm in which such “sudden breakage” would occur is...?

You keep claiming that this bug is a feature because it is the current
> behavior… but that is tautological reasoning.
>
> Thanks,
> Jon
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu via swift-evolution]

On Mon, Oct 16, 2017 at 14:55 Kevin Nattinger via swift-evolution <
swift-evolution@swift.org> wrote:

> On Oct 16, 2017, at 11:23 AM, David Sweeris via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> On Oct 16, 2017, at 10:42, BJ Homer via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu :
>
> What useful generic algorithms would this protocol support that are not
> already possible?
>
>
> It would allow expressing generic algorithms depending on an order.
>
> -Thorsten
>
>
> We can already express generic algorithms that depend on an order—any
> generic algorithm that works on a Sequence works on something that is
> ordered. A Swift Set has an undefined order right now, but a generic
> algorithm working on any arbitrary Sequence likely doesn’t care about
> *what* the order, just that an order exists. And a Swift Set does indeed
> have an order. If you have a generic algorithm that only works on inputs
> sorted in a particular manner, then you’ve likely either documented that or
> added a “sortedBy” parameter. Otherwise, you probably just want to be able
> to iterate through everything.
>
> Let’s assume, though, that you wanted to write an algorithm that works
> only on MeaningfullyOrdered inputs.
>
> func extractInfo(_ input: T) { }
> extractInfo(someArray)
>
> What stops the caller from simply wrapping the Set in an Array?
>
> extractInfo(Array(someSet))
>
> The Array constructed here is going to reflect the arbitrary ordering
> provided by Set, but as far as the type system is concerned, the input is
> an Array, which is certainly meaningfully-ordered. Have we gained anything
> by requiring the caller to wrap the input in an array? We’ve made the call
> site a bit more awkward, and we’ve lost a bit of performance. We certainly
> need to be able to convert Sets in to Arrays; to eliminate that would be
> massively source-breaking, and it’s not clear that allowing that conversion
> is actively harmful, so it’s unlikely to change in Swift 5.
>
>
> Should/could we just rename `Set` to `UniquedArray` or something like
> that? This is starting to feel a bit like the access control debate.
>
>
> So essentially convert Set to OrderedSet and not offer a theoretical
> unordered Set? I think that would be acceptable (if we apply it to
> dictionaries as well), BUT that doesn't address the more general case of
> other, potentially custom unordered Sequences.
>

Think of it this way: all Swift stdlib types that model unordered sequences
are in fact ordered—no attempt is made to support the modeling of unordered
sequences as unordered Swift types, custom or built-in.


>
> - Dave Sweeris
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 16, 2017, at 11:23 AM, David Sweeris via swift-evolution 
>  wrote:
> 
> 
> On Oct 16, 2017, at 10:42, BJ Homer via swift-evolution 
> > wrote:
> 
>>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>>> > wrote:
>>> 
 Am 16.10.2017 um 07:19 schrieb Xiaodi Wu >:
>>> 
 What useful generic algorithms would this protocol support that are not 
 already possible?
>>> 
>>> It would allow expressing generic algorithms depending on an order.
>>> 
>>> -Thorsten
>> 
>> We can already express generic algorithms that depend on an order—any 
>> generic algorithm that works on a Sequence works on something that is 
>> ordered. A Swift Set has an undefined order right now, but a generic 
>> algorithm working on any arbitrary Sequence likely doesn’t care about what 
>> the order, just that an order exists. And a Swift Set does indeed have an 
>> order. If you have a generic algorithm that only works on inputs sorted in a 
>> particular manner, then you’ve likely either documented that or added a 
>> “sortedBy” parameter. Otherwise, you probably just want to be able to 
>> iterate through everything.
>> 
>> Let’s assume, though, that you wanted to write an algorithm that works only 
>> on MeaningfullyOrdered inputs. 
>> 
>> func extractInfo(_ input: T) { }
>> extractInfo(someArray)
>> 
>> What stops the caller from simply wrapping the Set in an Array?
>> 
>> extractInfo(Array(someSet))
>> 
>> The Array constructed here is going to reflect the arbitrary ordering 
>> provided by Set, but as far as the type system is concerned, the input is an 
>> Array, which is certainly meaningfully-ordered. Have we gained anything by 
>> requiring the caller to wrap the input in an array? We’ve made the call site 
>> a bit more awkward, and we’ve lost a bit of performance. We certainly need 
>> to be able to convert Sets in to Arrays; to eliminate that would be 
>> massively source-breaking, and it’s not clear that allowing that conversion 
>> is actively harmful, so it’s unlikely to change in Swift 5.
> 
> Should/could we just rename `Set` to `UniquedArray` or something like that? 
> This is starting to feel a bit like the access control debate.

So essentially convert Set to OrderedSet and not offer a theoretical unordered 
Set? I think that would be acceptable (if we apply it to dictionaries as well), 
BUT that doesn't address the more general case of other, potentially custom 
unordered Sequences.

> 
> - Dave Sweeris
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 16.10.2017 um 19:42 schrieb BJ Homer :
> 
>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu >> >:
>> 
>>> What useful generic algorithms would this protocol support that are not 
>>> already possible?
>> 
>> It would allow expressing generic algorithms depending on an order.
>> 
>> -Thorsten
> 
> We can already express generic algorithms that depend on an order—any generic 
> algorithm that works on a Sequence works on something that is ordered. A 
> Swift Set has an undefined order right now, but a generic algorithm working 
> on any arbitrary Sequence likely doesn’t care about what the order, just that 
> an order exists. And a Swift Set does indeed have an order. If you have a 
> generic algorithm that only works on inputs sorted in a particular manner, 
> then you’ve likely either documented that or added a “sortedBy” parameter. 
> Otherwise, you probably just want to be able to iterate through everything.
> 
> Let’s assume, though, that you wanted to write an algorithm that works only 
> on MeaningfullyOrdered inputs. 
> 
> func extractInfo(_ input: T) { }
> extractInfo(someArray)
> 
> What stops the caller from simply wrapping the Set in an Array?
> 
> extractInfo(Array(someSet))
> 
> The Array constructed here is going to reflect the arbitrary ordering 
> provided by Set, but as far as the type system is concerned, the input is an 
> Array, which is certainly meaningfully-ordered. Have we gained anything by 
> requiring the caller to wrap the input in an array? We’ve made the call site 
> a bit more awkward, and we’ve lost a bit of performance.
> We certainly need to be able to convert Sets in to Arrays; to eliminate that 
> would be massively source-breaking, and it’s not clear that allowing that 
> conversion is actively harmful, so it’s unlikely to change in Swift 5.
> 
> So I agree with Xiaodi; I don’t see what we would gain by splitting the 
> protocols, other than some conceptual purity. Some have expressed concern 
> over the existence of someSet.first, but even if we removed it, it would 
> still be available as Array(someSet).first. And we still haven't any examples 
> of actual algorithms that would surprise the user by behaving incorrectly 
> when given an arbitrarily-ordered sequence, so it’s hard to make the argument 
> that this restriction is actively harmful.
> 
> I agree that isOrderedEqual(to:) is a better name for elementsEqual()

IMHO `elementsEqual` provides a nice example for a method which only makes 
sense on something meaningfully ordered:
What is the use case for `elementsEqual` that works with a Set?

-Thorsten___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 16.10.2017 um 18:19 schrieb Michael Ilseman :
> 
> 
> 
>> On Oct 16, 2017, at 7:20 AM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>> 
>> 
>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu > >:
>> 
>>> On Sun, Oct 15, 2017 at 11:57 PM, Thorsten Seitz >> > wrote:
>>> 
>>> 
>>> Am 16.10.2017 um 00:41 schrieb Xiaodi Wu via swift-evolution 
>>> >:
>>> 
 On Sun, Oct 15, 2017 at 2:32 PM, Kevin Nattinger > wrote:
> […]
> Sets, as a mathematical concept, have no intrinsic order. However, 
> instances of `Set`, which can be iterated over, *do* have at least one 
> order which can be said to be intrinsic in the following sense: as long 
> as iteration is possible, no API design can prevent that order from being 
> observed and associated with the instance. Put another way, if you can 
> use an instance of a type in a for...in loop, intrinsic to that 
> functionality is a publicly visible order.
 
 You keep saying this, I keep saying it’s only a technical “order” that is 
 an implementation detail
 
 You keep saying it's an implementation detail, which it emphatically is 
 *not*. It's a *public guarantee* by the protocol that you can use an 
 instance of `Set` in a `for...in` loop, thereby exposing a publicly 
 visible order. An implementation detail is something
>>> 
>>> Being able to use a Set in a for...in loop does *not* make it ordered! The 
>>> purpose is is just being able to do something with each element. That a 
>>> for...loop works sequentially is just a side effect. Just imagine we had 
>>> parallelized for...in loops.
>>> 
>>> No, it is not at all a "side effect." A for...in loop is a way of 
>>> controlling the flow of code which accesses elements in a sequence one 
>>> after another, and the correct behavior of code inside the loop depends on 
>>> these semantics. A "parallel for" loop would be a totally different thing; 
>>> arbitrary for...in loops can't be automatically "upgraded" to a "parallel 
>>> for" loop because they have different semantics, and types that support 
>>> "parallel for" would likely have to conform to a protocol other than 
>>> `Sequence`.
>> 
>> Exactly.
>> 
 that could go away with an alternative implementation. By contrast, no 
 implementation that permits an instance of `Set` being iterated over in a 
 `for...in` loop can avoid exposing at least one publicly visible order, 
 because it's not a matter of implementation. Put another way, by allowing 
 iteration, a type necessarily exposes at least one publicly visible order 
 and thereby models a sequence in at least one way.
>>> 
>>> Wrong. I could easily implement Set or another type to iterate in a random 
>>> order over its elements, so each iteration would expose a different 
>>> (meaningless) order.
>>> 
>>> No, you cannot implement `Set` in this way because it conforms to 
>>> `Collection`, which guarantees a multi-pass sequence. Set *must expose the 
>>> same order on every iteration*.
>> 
>> Set conforming to Collection is even worse than just conforming to Sequence 
>> as a quote from the documentation shows: "In addition to the operations that 
>> collections inherit from the Sequence protocol, you gain access to methods 
>> that depend on accessing an element at a specific position in a collection."
>> Clearly the elements of a Set do not have specific positions.
>> 
> 
> That’s not at all clear to me, could you elaborate? My understanding is that 
> elements of Set definitely *do* have a position, and that’s why you can use 
> an index on a set to retrieve the element. The same index on the same set 
> retrieves the same element.

That might be true, by virtue of implementation. But the notion of a Set is 
unordered (OrderedSet would be different but with a meaningful and stable  
order) so the notion of positions within a Set do not make sense IMHO. The 
indices provided by the Collection interface do might even make sense as 
references for a set but the concept of distances between such indices is just 
weird for sets.

-Thorsten


> 
> 
>> Furthermore my argument still stands for types derived from Sequence, so 
>> sidestepping it by pointing out that the situation is even worse for the 
>> current implementation of Set won't work. Can you explain why a type derived 
>> from Sequence which will iterate over its elements in random order should 
>> have methods like dropFirst()?
>> 
>> 
>>>  
>>> This demonstrates that being able to be used in a for...in loop is about 
>>> doing somthing with each element and not about element order.
>>> 
>>> Again, Sequence *already doesn't* require the order to be meaningful or 
>>> 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 16.10.2017 um 17:49 schrieb Jonathan Hull via swift-evolution 
> :
> 
> 
>> On Oct 16, 2017, at 7:20 AM, Xiaodi Wu > > wrote:
>> 
>> 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 that iteration order is undefined and could easily change due to changes 
> in the private/internal structure of sets/dictionaries.  Algorithms that rely 
> on that “publicly observable behavior” (i.e. leaking of internals) will 
> suddenly break.  You keep claiming that this bug is a feature because it is 
> the current behavior… but that is tautological reasoning.

Indeed.

-Thorsten

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Thorsten Seitz via swift-evolution]

> Am 16.10.2017 um 16:20 schrieb Xiaodi Wu via swift-evolution 
> :
> 
> 
> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  > wrote:
> 
>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu > > wrote:
>> 
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull > > wrote:
>> 
>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu >> > 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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

> On Oct 16, 2017, at 10:43 AM, BJ Homer via swift-evolution 
>  wrote:
> 
>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>> > wrote:
>> 
>>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu >> >:
>> 
>>> What useful generic algorithms would this protocol support that are not 
>>> already possible?
>> 
>> It would allow expressing generic algorithms depending on an order.
>> 
>> -Thorsten
> 
> We can already express generic algorithms that depend on an order—any generic 
> algorithm that works on a Sequence works on something that is ordered. A 
> Swift Set has an undefined order right now, but a generic algorithm working 
> on any arbitrary Sequence likely doesn’t care about what the order, just that 
> an order exists. And a Swift Set does indeed have an order. If you have a 
> generic algorithm that only works on inputs sorted in a particular manner, 
> then you’ve likely either documented that or added a “sortedBy” parameter. 
> Otherwise, you probably just want to be able to iterate through everything.
> 
> Let’s assume, though, that you wanted to write an algorithm that works only 
> on MeaningfullyOrdered inputs. 
> 
> func extractInfo(_ input: T) { }
> extractInfo(someArray)
> 
> What stops the caller from simply wrapping the Set in an Array?
> 
> extractInfo(Array(someSet))
> 
> The Array constructed here is going to reflect the arbitrary ordering 
> provided by Set, but as far as the type system is concerned, the input is an 
> Array, which is certainly meaningfully-ordered. Have we gained anything by 
> requiring the caller to wrap the input in an array?

We force the user to acknowledge that the unspecified order is acceptable to 
them, as opposed to sorting. Much like the `uniquingKeysWith` argument on 
Dictionary.init(keysAndValues:uniquingKeysWith:). That one even has a sane 
default behavior used in many other languages (`{$1}`) and still doesn't offer 
that as a default; whereas a set's iteration order has no sane default. I think 
it would even be acceptable (or even desired) to have the set's Iterator be 
MeaningfullyOrdered, so the user could bypass the array and use 
`someSet.makeIterator()`, which would probably have little if any performance 
or memory overhead.

> We’ve made the call site a bit more awkward, and we’ve lost a bit of 
> performance. We certainly need to be able to convert Sets in to Arrays; to 
> eliminate that would be massively source-breaking, and it’s not clear that 
> allowing that conversion is actively harmful, so it’s unlikely to change in 
> Swift 5.
> 
> So I agree with Xiaodi; I don’t see what we would gain by splitting the 
> protocols, other than some conceptual purity.

Conceptual purity is, e.g. why protocols with associated types are such a pain 
in the ass to work with. Sequence makes plenty of sense and is concise and 
clear (and used in, e.g. Java, C#), why should I spell it Any, or whatever it ends up being. 4 years into the 
language and two of the majorly touted benefits of the language (protocols and 
generics) play so poorly with each other that it is one of if not THE major 
pain point in the language. All because a couple people wanted conceptual 
purity.

I'm quite sure I've seen the conceptual purity argument used in favor of many 
other suggestions on this list, though I don't have the time to go through and 
find them.

> Some have expressed concern over the existence of someSet.first, but even if 
> we removed it, it would still be available as Array(someSet).first. And we 
> still haven't any examples of actual algorithms that would surprise the user 
> by behaving incorrectly when given an arbitrarily-ordered sequence, so it’s 
> hard to make the argument that this restriction is actively harmful.

equalElements(), the original motivation for this proposal, is actively harmful 
on unordered Sequences. On any two instances of any unordered Sequence that are 
`==`, it could come back true or false. And adding and removing an element to 
one of them (so the same instance is back in the same state), could change the 
result. I don't think anyone new to the language would expect that. 

> I agree that isOrderedEqual(to:) is a better name for elementsEqual()

Much more acceptable than the proposed name.

> 
> -BJ
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

A Set has indices because they are useful to use with the type. Regardless of 
whether Set conforms to Collection, or even Sequence, indices are useful and 
meaningful for Sets. Even if the entire protocol hierarchy were to be 
redesigned, Set would provide indices. If Set didn’t implement any protocols at 
all, Set would still provide indices. Independent of whether Set even provides 
an Iterator, Set would still provide Indices.


> On Oct 16, 2017, at 10:19 AM, Kevin Nattinger  wrote:
> 
>>> […]
>>> Set conforming to Collection is even worse than just conforming to Sequence 
>>> as a quote from the documentation shows: "In addition to the operations 
>>> that collections inherit from the Sequence protocol, you gain access to 
>>> methods that depend on accessing an element at a specific position in a 
>>> collection."
>>> Clearly the elements of a Set do not have specific positions.
>>> 
>> 
>> That’s not at all clear to me, could you elaborate? My understanding is that 
>> elements of Set definitely *do* have a position, and that’s why you can use 
>> an index on a set to retrieve the element. The same index on the same set 
>> retrieves the same element.
> 
> A Set only has "indices" because it confirms to a protocol where almost all 
> the requirements are meaningless for an unordered collection. Or at best, for 
> the same reason it has an "order": as a side-effect of the fact that it can 
> be iterated over, you can give indices for each element on a specific 
> iteration; those indices are meaningless for the set itself, and should not 
> be used for anything but a full, order-independent iteration.

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

Sets being values are not an implementation detail. They have value semantics, 
and that is part of the guarantee of the type. This is perhaps the most 
important concept in the standard library.


> On Oct 16, 2017, at 10:27 AM, Kevin Nattinger  wrote:
> 
>>> 
>>> How is the iteration order of an unordered set or dictionary “publicly 
>>> observable”? If either is implemented such that it can asynchronously 
>>> optimize its storage (maybe by rebalancing a tree or merging two 
>>> non-contiguous array segments or something), its iteration order could 
>>> change without changing what values it contains. Seems like consecutive 
>>> calls to “elementsEquals” (or whatever we’re calling it) should return the 
>>> same answer, if we don’t add, remove, or mutate elements.
>>> 
>> 
>> Sets are values. If you add, remove, or mutate any elements you have a 
>> different Set and thus a potentially different ordering of elements.
> 
> An implementation detail. We could make it a class* and AFAICT that wouldn't 
> break any guarantees on Sequence; and the argument applies equally well to 
> any other unordered Sequence, which has no value type or semantics constraint.
> 
> *: obviously we won't, I don't think anyone is advocating that.
> 

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 16, 2017, at 10:42, BJ Homer via swift-evolution 
>  wrote:
> 
>>> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>>>  wrote:
>>> 
>>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu :
>> 
>>> What useful generic algorithms would this protocol support that are not 
>>> already possible?
>> 
>> It would allow expressing generic algorithms depending on an order.
>> 
>> -Thorsten
> 
> We can already express generic algorithms that depend on an order—any generic 
> algorithm that works on a Sequence works on something that is ordered. A 
> Swift Set has an undefined order right now, but a generic algorithm working 
> on any arbitrary Sequence likely doesn’t care about what the order, just that 
> an order exists. And a Swift Set does indeed have an order. If you have a 
> generic algorithm that only works on inputs sorted in a particular manner, 
> then you’ve likely either documented that or added a “sortedBy” parameter. 
> Otherwise, you probably just want to be able to iterate through everything.
> 
> Let’s assume, though, that you wanted to write an algorithm that works only 
> on MeaningfullyOrdered inputs. 
> 
> func extractInfo(_ input: T) { }
> extractInfo(someArray)
> 
> What stops the caller from simply wrapping the Set in an Array?
> 
> extractInfo(Array(someSet))
> 
> The Array constructed here is going to reflect the arbitrary ordering 
> provided by Set, but as far as the type system is concerned, the input is an 
> Array, which is certainly meaningfully-ordered. Have we gained anything by 
> requiring the caller to wrap the input in an array? We’ve made the call site 
> a bit more awkward, and we’ve lost a bit of performance. We certainly need to 
> be able to convert Sets in to Arrays; to eliminate that would be massively 
> source-breaking, and it’s not clear that allowing that conversion is actively 
> harmful, so it’s unlikely to change in Swift 5.

Should/could we just rename `Set` to `UniquedArray` or something like that? 
This is starting to feel a bit like the access control debate.

- Dave Sweeris___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[David Sweeris via swift-evolution]

> On Oct 16, 2017, at 09:21, Michael Ilseman  wrote:
> 
> 
> 
>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution 
>>  wrote:
>> 
>> 
>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution 
>>  wrote:
>> 
>>> 
 On Mon, Oct 16, 2017 at 05:48 Jonathan Hull  wrote:
 
> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu  wrote:
> 
>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull  wrote:
>> 
 On Oct 14, 2017, at 10:48 PM, Xiaodi Wu  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 

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[BJ Homer via swift-evolution]

> On Oct 16, 2017, at 8:20 AM, Thorsten Seitz via swift-evolution 
>  wrote:
> 
>> Am 16.10.2017 um 07:19 schrieb Xiaodi Wu > >:
> 
>> What useful generic algorithms would this protocol support that are not 
>> already possible?
> 
> It would allow expressing generic algorithms depending on an order.
> 
> -Thorsten

We can already express generic algorithms that depend on an order—any generic 
algorithm that works on a Sequence works on something that is ordered. A Swift 
Set has an undefined order right now, but a generic algorithm working on any 
arbitrary Sequence likely doesn’t care about what the order, just that an order 
exists. And a Swift Set does indeed have an order. If you have a generic 
algorithm that only works on inputs sorted in a particular manner, then you’ve 
likely either documented that or added a “sortedBy” parameter. Otherwise, you 
probably just want to be able to iterate through everything.

Let’s assume, though, that you wanted to write an algorithm that works only on 
MeaningfullyOrdered inputs. 

func extractInfo(_ input: T) { }
extractInfo(someArray)

What stops the caller from simply wrapping the Set in an Array?

extractInfo(Array(someSet))

The Array constructed here is going to reflect the arbitrary ordering provided 
by Set, but as far as the type system is concerned, the input is an Array, 
which is certainly meaningfully-ordered. Have we gained anything by requiring 
the caller to wrap the input in an array? We’ve made the call site a bit more 
awkward, and we’ve lost a bit of performance. We certainly need to be able to 
convert Sets in to Arrays; to eliminate that would be massively 
source-breaking, and it’s not clear that allowing that conversion is actively 
harmful, so it’s unlikely to change in Swift 5.

So I agree with Xiaodi; I don’t see what we would gain by splitting the 
protocols, other than some conceptual purity. Some have expressed concern over 
the existence of someSet.first, but even if we removed it, it would still be 
available as Array(someSet).first. And we still haven't any examples of actual 
algorithms that would surprise the user by behaving incorrectly when given an 
arbitrarily-ordered sequence, so it’s hard to make the argument that this 
restriction is actively harmful.

I agree that isOrderedEqual(to:) is a better name for elementsEqual()

-BJ___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

>> 
>> How is the iteration order of an unordered set or dictionary “publicly 
>> observable”? If either is implemented such that it can asynchronously 
>> optimize its storage (maybe by rebalancing a tree or merging two 
>> non-contiguous array segments or something), its iteration order could 
>> change without changing what values it contains. Seems like consecutive 
>> calls to “elementsEquals” (or whatever we’re calling it) should return the 
>> same answer, if we don’t add, remove, or mutate elements.
>> 
> 
> Sets are values. If you add, remove, or mutate any elements you have a 
> different Set and thus a potentially different ordering of elements.

An implementation detail. We could make it a class* and AFAICT that wouldn't 
break any guarantees on Sequence; and the argument applies equally well to any 
other unordered Sequence, which has no value type or semantics constraint.

*: obviously we won't, I don't think anyone is advocating that.

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Kevin Nattinger via swift-evolution]

>> […]
>> Set conforming to Collection is even worse than just conforming to Sequence 
>> as a quote from the documentation shows: "In addition to the operations that 
>> collections inherit from the Sequence protocol, you gain access to methods 
>> that depend on accessing an element at a specific position in a collection."
>> Clearly the elements of a Set do not have specific positions.
>> 
> 
> That’s not at all clear to me, could you elaborate? My understanding is that 
> elements of Set definitely *do* have a position, and that’s why you can use 
> an index on a set to retrieve the element. The same index on the same set 
> retrieves the same element.

A Set only has "indices" because it confirms to a protocol where almost all the 
requirements are meaningless for an unordered collection. Or at best, for the 
same reason it has an "order": as a side-effect of the fact that it can be 
iterated over, you can give indices for each element on a specific iteration; 
those indices are meaningless for the set itself, and should not be used for 
anything but a full, order-independent iteration.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Draft] Rename Sequence.elementsEqual

[Michael Ilseman via swift-evolution]

> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution 
>  wrote:
> 
> 
> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution 
> > wrote:
> 
>> 
>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull > > wrote:
>> 
>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu >> > wrote:
>>> 
>>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull >> > wrote:
>>> 
 On Oct 14, 2017, at 10:48 PM, Xiaodi Wu > 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