On Fri, Oct 13, 2017 at 3:06 PM, Jonathan Hull <jh...@gbis.com> wrote:
> It has been a while, but I believe a lexicographical ordering is basically > a mapping from a set to the natural numbers (which should, in effect, > provide a total ordering). The mapping itself can be arbitrary, but the > same set of things should never map to two different sequences (which just > happens to be the example given). > > This tells me that “lexicographicallyPrecedes” is actually misnamed unless > it refers to something which has a defined totally ordering. > By defining lexicographical equivalence and precedence, a total order is defined for the set of all sequences that have the same element type. That is, defining lexicographical equivalence and precedence for sequences of Foos imposes a total ordering over the set of all sequences of Foos. Notice that `lexicographicallyPrecedes` refers to the singular sequence being ordered with respect to other sequences, not to the elements of the sequence. If we are looking to rename elementsEqual (which I would expect to check if > the same elements are present regardless of ordering), I would recommend > *elementOrderingEqual* or something like that that references that the > answer will be affected by the internal representation/ordering of the > sequence. > > Thanks, > Jon > > On Oct 13, 2017, at 11:10 AM, Jarod Long via swift-evolution < > swift-evolution@swift.org> wrote: > > The name that feels natural to me would be `sequentiallyEquals`. I don't > dispute that the term "lexicographical" is used correctly here, although at > least for me personally, it's not a word that I encounter frequently enough > to understand what this method would do without reading the documentation. > Like Kevin, if I were to guess what the method did without checking, I > would probably think that it compared lexicographically-sorted versions of > the collections. > > But the consistency with `lexicographicallyPrecedes` is a pretty strong > argument, although `sequentiallyPrecedes` would also feel more natural to > me there, and my suspicion about the mentioned lack of evidence that the > method has been a pitfall for users is that it's not actually used often > enough out in the wild to have heard much about it. That's just a guess > though. This proposal is the first time I've learned of its existence. > > In any case, my ideal version of this proposal would use > `sequentiallyEquals` and also rename `lexicographicallyPrecedes` to > `sequentiallyPrecedes`, but I still like the proposal overall as-is. Thanks > for bringing it forward! > > Jarod > > On Oct 12, 2017, 16:24 -0700, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org>, wrote: > > Rename Sequence.elementsEqual > > - Proposal: SE-NNNN > <https://gist.github.com/xwu/NNNN-rename-elements-equal.md> > - Authors: Xiaodi Wu <https://github.com/xwu> > - Review Manager: TBD > - Status: *Awaiting review* > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#introduction> > Introduction > > The current behavior of Sequence.elementsEqual is potentially confusing > to users given its name. Having surveyed the alternative solutions to this > problem, it is proposed that the method be renamed to Sequence. > lexicographicallyEquals. > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#motivation> > Motivation > > As outlined by Ole Begemann > <https://twitter.com/olebegemann/status/916291785185529857>, use of > Sequence.elementsEqual(_:) can lead to surprising results if the > sequences compared are unordered: > > var set1: Set<Int> = Set(1...5)var set2: Set<Int> = Set((1...5).reversed()) > > set1 == set2 // trueset1.elementsEqual(set2) // false > > This result does reflect the *intended and documented* behavior of the > elementsEqual(_:) method, which performs a *lexicographical* elementwise > comparison. That is, the method first compares set1.first to set2.first, > then (if the two elements compare equal) compares the next element stored > internally in set1 to the next element stored internally in set2, and so > on. > > In almost all circumstances where a set is compared to another set, or a > dictionary is compared to another dictionary, users should use == instead > of elementsEqual(_:). > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#proposed-solution>Proposed > solution > > The proposed solution is the result of an iterative process of reasoning, > presented here: > > The first and most obvious solution is to remove the elementsEqual(_:) > method altogether in favor of ==. This prevents its misuse. However, > because elementsEqual(_:) is a generic method on Sequence, we can use it > to compare an instance of UnsafeBufferPointer<Int> to an instance of [Int]. > This is a useful and non-redundant feature which would be eliminated if the > method is removed altogether. > > A second solution <https://github.com/apple/swift/pull/12318> is to > create overloads that forbid the use of the elementsEqual(_:) method > specifically in non-generic code. This would prevent misuse in non-generic > code; however, it would also forbid legitimate mixed-type comparisons in > non-generic code while failing to prevent misuse in generic code. The > solution also creates a difference in the behavior of generic and > non-generic code calling the same method, which is potentially confusing, > without solving the problem completely. > > A third solution is to dramatically overhaul the protocol hierarchy for > Swift sequences and collections so that unordered collections no longer > have members such as first and elementsEqual(_:). However, this would be > a colossal and source-breaking undertaking, and it is unlikely to be > satisfactory in addressing all the axes of differences among sequence and > collection types: > > - Finite versus infinite > - Single-pass versus multi-pass > - Ordered versus unordered > - Lazy versus eager > - Forward/bidirectional/random-access > > A fourth solution is proposed here. It is predicated on the following > observation: > > *Another method similar to elementsEqual(_:) already exists on Sequence > named lexicographicallyPrecedes(_:). Like first, elementsEqual(_:), > drop(while:), and others, it relies on the internal order of elements in a > manner that is not completely suitable for an unordered collection. > However, like first and unlike elementsEqual(_:), this fact is called out > in the name of the method; unsurprisingly, like first and unlike > elementsEqual(_:), there is no evidence that lexicographicallyPrecedes(_:) > has been a pitfall for users.* > > This observation suggests that a major reason for confusion over > elementsEqual(_:) stems from its name. So, *it is proposed that > elementsEqual(_:) should be renamed to lexicographicallyEquals(_:)*. The > function will remain somewhat of a poor fit for unordered collections, but > no more so than many other methods that cannot trivially be removed from > the API of unordered collections (as discussed above). The key is that, > with such a renaming, the behavior of this method will no longer be > confusing. > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#detailed-design>Detailed > design > > extension Sequence where Element : Equatable { > @available(*, deprecated, message: "Use '==' if possible to compare two > sequences of the same type, or use 'lexicographicallyEquals' to compare two > ordered sequences.") > public func elementsEqual<Other : Sequence>( > _ other: Other > ) -> Bool where Other.Element == Element { > return lexicographicallyEquals(other) > } > > public func lexicographicallyEquals<Other : Sequence>( > _ other: Other > ) -> Bool where Other.Element == Element { > // The body of this method is unchanged. var iter1 = > self.makeIterator() > var iter2 = other.makeIterator() > while true { > switch (iter1.next(), iter2.next()) { > case let (e1?, e2?): > if e1 != e2 { return false } > case (_?, nil), (nil, _?): > return false > case (nil, nil): > return true > } > } > } > } > > A parallel change will be made with respect to elementsEqual(_:by:); that > is, it will be deprecated in favor of lexicographicallyEquals(_:by:). > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#source-compatibility>Source > compatibility > > Existing code that uses elementsEqual will gain a deprecation warning. > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#effect-on-abi-stability>Effect > on ABI stability > > None. > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#effect-on-api-resilience>Effect > on API resilience > > This proposal adds new methods to the public API of Sequence and > conforming types. > > <https://gist.github.com/xwu/1f0ef4e18a7f321f22ca65a2f56772f6#alternatives-considered>Alternatives > considered > > It is to be noted that lexicographicallyPrecedes(_:by:) and > elementsEqual(_:by:) are essentially the same method, since both perform > a lexicographical comparison using a custom predicate. However, there is > not a good unifying name. (lexicographicallyCompares(to:by:) reads > poorly.) Moreover, the predicate supplied is intended to have very > different semantics, and maintaining two distinct methods may be a superior > fit with the typical user's mental model of the intended behavior and may > also be clearer to readers of the code. Therefore, this proposal does not > seek to unify the two methods; instead, elementsEqual(_:by:) will be > renamed lexicographicallyEquals(_:by:) as detailed 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