> Am 16.10.2017 um 00:41 schrieb Xiaodi Wu via swift-evolution > <swift-evolution@swift.org>: > > On Sun, Oct 15, 2017 at 2:32 PM, Kevin Nattinger <sw...@nattinger.net> 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. > 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. 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. The latter is an additional property which should be expressed in an additional protocol like Kevin suggested. -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() actually drops a random element, or Set >>>> doesn’t have a dropFirst()? And if you think dropFirst() removing an >>>> element at random is not surprising, please explain why. >>> >>> I think Set.dropFirst removing the first element that I observe on >>> iteration is the least surprising answer, because Swift tells me that the >>> stdlib Set models a set but that it is also a sequence. >> >> Your logic is backwards. You’re saying it’s “least surprising” because >> that’s how it’s currently implemented, not that it should be implemented >> that way because it’s least surprising. > > No, I'm saying it's least surprising because any type that supports iterated > access thereby exposes an order--not as an implementation detail but as a > matter of public API--and in the absence of any other order, "first" must > refer to that order so exposed. >>>>>>>>> […] >>>> >>>> And that’s PRECISELY why lexicographicallyEqual does not make sense to >>>> apply to unordered sets. There is no lexicographical comparison possible, >>>> so why do you keep insisting they should have a method that falsely claims >>>> to lexicographically compare them? >>> >>> I agree! It doesn't make sense if no comparison is possible! But Swift >>> tells me that a `Set` is a `Sequence`! >> >> You keep making the circular argument that a Set should do things because it >> currently does them. If you want to argue against changing things, argue >> that things shouldn’t be changed, not that the current implementation is >> correct because it is the current implementation. > > No, I'm arguing that `Set`, by supporting iterated access, is not wrong to > conform to a protocol called `Sequence` because it does have an intrinsic and > publicly observable order, which is not an accident of a particular > implementation but is inherent to any type that supports iterated access. > Now, whether it's the *best choice* to conform `Set` to `Sequence` and offer > order-dependent functions is a matter of taste, but it isn't *wrong*. >>> […] >>> You will always have to account for this possibility, because Swift's >>> `Equatable` explicitly allows "special values" to be not equal to >>> themselves. This is, at least in part, in order to accommodate the IEEE >>> decree that NaN != NaN: >> >>> >>> ``` >>> let x = [Double.nan] >>> x.elementsEqual(x) // false >>> ``` >> >> NaN is special, one-shot and unordered sequences are not. Unless you think >> that all unordered and single-pass sequences should compare false for >> `elementsEqual`, this is irrelevant for any sequence that doesn’t contain >> NaN and well-defined (false) for any that does. > > Certainly, not all single-pass sequences should compare false to themselves, > but some should: for instance, an infinite single-pass stream of all 1's > should compare true to itself, but an infinite single-pass stream of > alternating 1's and 0's should compare false to itself. If you write generic > code that calls `elementsEqual`, it is pervasively incorrect to test for > identity by assuming that elementsEqual will return true on reflexive > comparison. NaN is only one of many reasons why such code would blow up. > >> >>> Changing this behavior is way beyond the scope of this thread (and has been >>> the topic of hours (actually, weeks and weeks) of fun on this list >>> previously). >> >> Yes, I’ve seen the discussion on NaN and Comparable. It’s not the same >> discussion. >> >>> […] >>>>>> 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. >>> Wouldn't it then suffice to document, say, that a set's iteration order is >>> the insertion order? >> >> Now this actually gave me pause. I guess it does match what I said, but I >> still take issue with the fact that two Sets could compare `==` but not >> `elementsEqual`. I think that defining iteration order as insertion order >> adds a piece of publicly documented state that goes beyond what a Set really >> is. What you describe is really an OrderedSet, just without the >> random-access manipulation. > > a) There is no semantic requirement on the part of `==` to be equivalent to > an elementwise comparison when it is defined on a collection; in fact, one > could imagine that some exotic sequence might legitimately define equality in > a way that has nothing to do with elementwise comparison. Put another way, > `==` returning `true` does not imply `elementsEqual` returning `true`, and > `elementsEqual` returning `true` does not imply `==` returning `true`. This > applies equally to ordered collections and is independent of the question of > how to model unordered collections. > > b) You keep writing that some Foo is really some Bar, but those are really > just names. What would be the harm if Swift's `Set` indeed simply models an > ordered set without random-access manipulation? > >> I’ll have to mull this over to see if I can come up with a coherent and >> (more) specific requirement for what makes an Iterable a Sequence, since >> clearly “documented” isn’t enough. Perhaps something along the lines that >> any two Sequences that compare equal must iterate the same. >> >>> […] >>> Apple documentation calls this one of the "order-dependent" methods. It is >>> surely acceptable for a type that conforms to an order-dependent protocol >>> to have methods that are order-dependent; they do, however, have to be >>> clearly order-dependent to avoid confusion on unordered types. >> >> I’m not clear on what you’re trying to get across here. It seems you’re >> saying unordered types shouldn’t have order-dependent methods, which is >> exactly what I’ve been arguing. > > No, I'm saying, essentially, that there are no truly unordered types in > Swift; `Set` and `Dictionary` lead double lives modeling unordered > collections on the one hand and ordered collections on the other. The > order-dependent methods can continue to exist; they just need to be clearly > named so that users know when they're using an instance of `Set` in the > manner of an unordered collection and when they're using an instance of `Set` > in the manner of an ordered collection. > >> >>> [...] >>>> Then there are all the methods that imply a specific order of iteration. >>>> If the “sequence” is unordered, who knows what you’ll get? It is >>>> incredibly easy for an engineer to write a method that implicitly relies >>>> on a passed sequence being intrinsically ordered and another engineer to >>>> pass it an unordered “sequence.” The first engineer could neglect to >>>> document the dependency, or even not notice it; or the second engineer >>>> could just fail to read the documentation thoroughly enough. There is >>>> currently no way for the compiler to enforce passing only an object that >>>> is (or at least claims to be) intrinsically ordered. >>> >>> It is also incredibly easy for such an engineer to use `for...in` instead >>> to accomplish the same task, generic over ordered and unordered sequences >>> whatever you name such distinguished protocols. I think your beef really >>> still boils down to Set being compatible with `for...in` at all, as Jon >>> acknowledges. >> >> Not providing ordered functions for unordered collections makes the >> developers think about what they actually need. If any object will do, they >> can use for…in, .makeIterator().next(), or an `anyObject()` we provide as a >> convenience. If they actually need the first from some specific order, it’s >> a reminder they need to sort the objects first to get the right one. > > The whole point of protocol hierarchies is to enable useful generic > algorithms. Here, the purpose of having a protocol that unites both ordered > and unordered collections is to permit the writing of generic algorithms that > operate on both; a user would want the first item from an ordered collection > or an arbitrary item (but the same one on multiple passes) from an unordered > collection. The name for that is currently `first`. Brent demonstrated a > trivial one-line example of such a use. > >> That’s particularly useful for functions that actually need an ordered >> sequence; using OrderedSequence instead of Iterable (just as placeholders) >> would be a firm reminder not to pass in an unordered collection. >> >>>>> […] >>> >>> As I said, you're welcome to tackle the protocol hierarchy, but I really >>> doubt it's within the realm of realistic endpoints for Swift 5. I'm just >>> trying to propose a narrowly targeted pragmatic solution to one specific >>> limited harm that might be deliverable by the next point release. As a >>> great man once said, Swift is a pragmatic language. >> >> If you want a pragmatic solution, fix the bug in functionality, don’t try >> and rename the method to something obscure to cover it up. > > What I'm arguing is that there *is no bug in functionality*, only a naming > problem. It is true that the current protocol hierarchy would not be my > preferred design, but that's a matter of taste in terms of, again, where to > draw the line between too much modeling or not enough. But that's not > tantamount to a *bug*. > >> If you want to limit the harm, override `equalObjects` on unordered >> sequences to use `==` (very strongly preferred), or always `false` (less >> desirable, but at least consistent) >> >>>>> […] >> >>> >>> The Swift stdlib deliberately eschews modeling everything in protocol >>> hierarchies with the highest level of granularity. There's some fudging, >>> deliberately, to find a happy medium between obtuse and approachable, >>> between too many/too specialized and not enough. For example, I pushed for >>> protocols such as `Field` and `Ring` at the top of the numeric hierarchy, >>> which might allow complex number types to slot into the hierarchy more >>> sensibly, for example. But we have a compromise protocol `Numeric` which >>> doesn't quite have the same guarantees but is much more approachable. >>> Notice that we also don't break down numeric protocols into `Addable`, >>> `Subtractable`, etc.; we also have that fudge factor built into >>> `Equatable`, as I mentioned. >> >> Eh, one or two corner cases on a protocol is probably fine. What’s not fine >> is over half (Sequence) or almost all (Collection) the methods not being >> applicable. There is a very clear gap there. We don’t need to fix >> everything, but this is something that can and should be addressed. > > This would be based on the premise that an instance of `Set` has no intrinsic > order; I disagree for the reasons above. > _______________________________________________ > 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
