> Le 16 oct. 2017 à 07:20, Xiaodi Wu via swift-evolution > <swift-evolution@swift.org> a écrit : > >> On Sun, Oct 15, 2017 at 11:57 PM, Thorsten Seitz <tseit...@icloud.com> wrote: >> >> >>> 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. > > 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() 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
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
