Re: [swift-evolution] /*Let it be*/ func() -> @discardable Bool {} /*Rather Than*/ @discardableResult func() -> Bool {}

[Chris Lattner via swift-evolution]

> On Oct 15, 2017, at 5:55 AM, Mike Kluev via swift-evolution 
>  wrote:
> 
> On 15 October 2017 at 13:35, Geordie Jay  > wrote:
> Also we're not talking about whether the Bool itself is discardable. For 
> example, it makes no sense to write:
> 
> let something: discardable Bool = true
> 
> you can't write this either:
> 
> let something: inout Bool = true
> 
> that doesn't mean "inout" should be "@inputOutput" before the parameter name 
> in function signature.
> 
> my litmus test is: "if we did it now in swift 0.0 what would we do". 
> discardable before type passes this test, @discardableResult before function 
> doesn't.
>  

FWIW, the official litmus test for Swift 5 is explained here:
https://github.com/apple/swift-evolution/ 


-Chris



___
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 

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

[Michael Ilseman via swift-evolution]

> 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.


> 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 even 
>> repeatable.
> 
> I know. That's why I am arguing that certain methods of Sequence make no 
> sense. At least we have reached that common ground. 
> So why do you insist on Sequence having methods like dropFirst() if the 
> notion of "first" does not make any sense?
> 
>> Notice that, above, I said at least one order. A conforming type could
>> expose as many different orders as iterations, but that changes nothing. I 
>> can still map an instance of that type to get an array of elements, and that 
>> array will reveal some order which is the result of the inner workings of 
>> the type.
>> 
>> The latter is an 

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

[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.

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

[David Sweeris via swift-evolution]

> 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 for 

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

[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 called it
>>> .arbitraryOrder).
>>>
>>> I believe it would not be source breaking.
>>>
>>
>> That is indeed something slightly different.
>>
>> In an ideal world--and my initial understanding of what you were
>> suggesting--Set and Dictionary would each have a member like 

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

[Thorsten Seitz via swift-evolution]

>> 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.

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 even 
> repeatable.

I know. That's why I am arguing that certain methods of Sequence make no sense. 
At least we have reached that common ground. 
So why do you insist on Sequence having methods like dropFirst() if the notion 
of "first" does not make any sense?

> Notice that, above, I said at least one order. A conforming type could
> expose as many different orders as iterations, but that changes nothing. I 
> can still map an instance of that type to get an array of elements, and that 
> array will reveal some order which is the result of the inner workings of the 
> type.
> 
>> The latter is an additional property which should be expressed in an 
>> additional protocol like Kevin suggested.
> 
> What useful generic algorithms would this protocol support that are not 
> already possible?

It would allow expressing generic algorithms depending on an order.

-Thorsten


> 
>> -Thorsten
>> 
>> 
>> 
>>>  
 and can’t be relied upon for anything and so we shouldn’t provide methods 
 that rely on it. I think this part of the discussion has reached the 
 “agree to disagree” stage.
 
>> […]
>> You’re a fan of the principal of least 

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

[Benjamin Garrigues via swift-evolution]

> Le 16 oct. 2017 à 07:20, Xiaodi Wu via swift-evolution 
>  a écrit :
> 
>> 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`.
>>> 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*.
>  
>> 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 even 
> repeatable. Notice that, above, I said at least one order. A conforming type 
> could expose as many different orders as iterations, but that changes 
> nothing. I can still map an instance of that type to get an array of 
> elements, and that array will reveal some order which is the result of the 
> inner workings of the type.
> 
>> The latter is an additional property which should be expressed in an 
>> additional protocol like Kevin suggested.
> 
> What useful generic algorithms would this protocol support that are not 
> already possible?

Imho , the original issue isn't to create more powerful generic algorithms, but 
to prevent errors on concrete ones using set.first ( which could mislead people 
into believing swift sets are ordered sets).
As another person said, it seems sets aren't a sequence, but rather 
"sequenceable" ( aka : you can spawn a sequence out of it). Whereas arrays are 
storing their elements as a sequence and so conflating the two notions of 
sequence and collection isn't as much of a gap (everything that applies to the 
iterator may very well apply to the array as well).

Do you have a link on a design document that explained the rational for 
conflating the notion of collections with the iterator ? 
At this point i'm not trying to argue anymore because you think pretty sure 
that it's a good idea, and the fact that .net also has the same design makes me 
think i may have missed something, so i'm just trying to understand this choice.


> 
>> -Thorsten
>> 
>> 
>> 
>>>  
 and can’t be relied upon for anything and so we shouldn’t provide methods 
 that rely on it. I think this part of the discussion has reached the 
 “agree to disagree” stage.
 
>> […]
>> You’re a fan of the principal of least surprise. Tell me, which would be 
>> less surprising: Set.dropFirst()