[swift-evolution] [Draft] Rename Sequence.elementsEqual
Xiaodi Wu
xiaodi.wu at gmail.com
Sat Oct 14 23:48:54 CDT 2017
On Sat, Oct 14, 2017 at 11:25 PM, Jonathan Hull <jhull at gbis.com> wrote:
> Because the mathematical term you talk about has conditions which must be
> met to be used/valid. Namely:
>
> 1) The “Alphabet” of elements must be totally ordered
> 2) The lexicographical comparison must be applied to ordered sequences of
> elements from that alphabet
>
> Neither of those conditions are met for an unordered generic collection
> (e.g. a set of equatable, but not comparable elements).
>
This is diametrically the opposite claim that Michael just made. Here, you
argue that the confusion stems from the extension of the term to sequences
with elements that are equatable but not comparable because there *isn't* a
total ordering for the elements. Michael just said that the term is
confusing particularly with Ints *because* they have an obvious total
ordering (i.e., they are comparable). And in fact, the apparently common
misconception is that the function would instead sort the elements of each
sequence by that ordering, which is obviously inapplicable for equatable
but not comparable elements, and such a misconception is therefore
impossible in that scenario.
_The very first result on Google_ defines lexicographical comparison
unambiguously for C++:
> Lexicographical comparison is a operation with the following properties:
>
> - Two ranges are compared element by element.
> - The first mismatching element defines which range is
> lexicographically *less* or *greater* than the other.
> - If one range is a prefix of another, the shorter range is
> lexicographically *less* than the other.
> - If two ranges have equivalent elements and are of the same length,
> then the ranges are lexicographically *equal*.
> - An empty range is lexicographically *less* than any non-empty range.
> - Two empty ranges are lexicographically *equal*.
>
> The purpose behind choosing "lexicographicallyEquals" was that it is a
term that has an established meaning, easily googled, that describes the
algorithm exactly and unambiguously in two words. If you have seen this
term in use, you will know what the Swift method does. If you have not seen
this term, then even in the absence of Swift documentation, a single search
will lead you to the correct answer. I am simply in disbelief that
apparently many people will see a term with which they are unfamiliar,
assume it means something it does not, and use the function without
consulting the documentation or looking up the term.
The underlying issue here is that the “ordering” of the sequence coming out
> of a set/dictionary is undefined and may rely on internal implementation
> details. Building anything on top of that is problematic because the
> foundation is undefined. Lexicographical’s connotation of applying a total
> order only compounds that original issue, especially if the elements are
> strings or some other sequential data type.
>
Right, and the purpose of this proposal is to give it such a name that it
is obvious that this function is probably not what you want in comparing
two concrete sets (much as it is obvious on first glance that `first` is
probably not useful when working with concrete sets), without going down
the road of attempting to rip out the established protocol hierarchy.
On Oct 14, 2017, at 8:45 PM, Xiaodi Wu via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> On Sat, Oct 14, 2017 at 8:11 PM, Michael Ilseman <milseman at apple.com>
> wrote:
>
>> I think that “match” is a word to avoid for this, as this doesn’t have
>> anything to do with pattern matching, fuzzy matching, etc., while “equals”
>> is precisely the concept we’re using.
>>
>> What about the name “sequentiallyEquals”? Highlight the fact that we’re
>> talking about sequential ordering, i.e. whatever order the sequence
>> provides, as opposed to first doing some lexicographical ordering of
>> elements themselves.
>>
>> var a: Set<Int> = [3, 1, 2]
>> a.sequentiallyEquals([1,2,3]) // result depends on application of
>> equality in a (potentially-arbitrary) sequential ordering
>>
>> Whereas I could see the following being more confusing:
>>
>> var a: Set<Int> = [3, 1, 2]
>> a.lexicographicallyEquals([1,2,3]) // result depends on application of
>> equality, but what meaning does “lexicographically” convey?
>>
>> It’s not immediately clear to someone new to the API that
>> “lexicographically” speaks to the nature of the sequence’s
>> (potentially-arbitrary) order, irrespective of element. It could give the
>> false impression that it speaks to some nature of the elements themselves,
>> in this case Ints, which have an obvious lexicographical ordering. I don’t
>> know how frequent that misconception would be in practice, but it does
>> cause me to do a double-take in this contrived example.
>>
>>
> I'm entirely puzzled that apparently large numbers of people believe
> lexicographical comparison, a term with a very specific mathematical
> definition and no colloquial use, to mean what it does not. I'd like to
> avoid inventing Swift-specific new terms for this particular concept which
> is not at all unique to Swift. The other plausible terms I can see with
> some other use might be "elementwise equals" or "entrywise equals" or
> "coordinatewise equals."
>
>
>>
>> On Oct 14, 2017, at 1:04 PM, Benjamin G via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>> To answer more precisely this request (which remains valid no matter the
>> protocol hierarchy). I propose
>>
>> "matchesSequence" ( or simply "matches" or "match", whatever is more
>> coherent with the naming guidelines).
>>
>> So
>> var a: [Int] = [1,2,3]
>> a.matchesSequence([1,2,3]) returns true.
>>
>> I first thought that the verb "matching" was too heavily associated to
>> regular expressions, but i think that it's the correct equivalent for
>> something as general as a sequence.
>>
>>
>>
>>
>>
>>
>>
>> On Fri, Oct 13, 2017 at 1:24 AM, Xiaodi Wu via swift-evolution <
>> swift-evolution at 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 at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171014/8d513195/attachment.html>
More information about the swift-evolution
mailing list