Hey folks. While working on Advent of Code, I ran into the need for a contains(_:) for ClosedRange. What I found was that I had one available, but because I had imported RegexBuilder in my source file, it was one of the contains(_:) extension methods that were added onto Collection as part of SE-0357. As a result, I was unexpectedly performing O(n) operations on my ranges when O(1) would've been possible.
To correspond to the existing overlaps(_:) method, I'd like to propose a contains(_:) or isSuperset(of:) method to be included into the standard library for ClosedRange, and Range if possible. It seems like a strange gap in the existing API. I saw this was last proposed back in 2017, so maybe this is worth raising once again. Hopefully the community will find this a positive inclusion.
This is all good feedback. I raised this pitch without much knowledge of the underlying math or computer science, so I appreciate it. I'll make sure to update the OP with the relevant signatures and behaviors with regard to their relations.
The only concern I have with a name other than contains(_:) is that exposure of the new Collection extension in _StringProcessing. This method is public, undocumented, and O(n), all of which can be unexpected for users working with Ranges. I would want any solution we implement to have an API impact in this case. That said, I appreciate the desire for consistency (despite not directly conforming SetAlgebra), and I vaguely recall Swift's API design ethos standing against having multiple methods to express the same thing, like we see in Ruby.
Sounds like there's a problem with that method being available on range types because it is inappropriate to use; if so, we should fix the problem, whether by deprecating or some other method to warn users, independent of what APIs are added.
As a general principle, I'd argue that a string processing facility exposing unnecessarily inefficient operations on non-string processing types should be considered a bug.
Sequence.contains(_: some Sequence<Element>) should be in the standard library.
I'm happy that it exists in some form now (only for Collection, like with sadly much of the Algorithms package), but it does need to be handled better.
contains and isSuperset mean the same thing for ranges, because their elements are both unique and ordered, but contains more clearly demonstrates the idea of order. These overloads need to be added to the standard library to fix the problem:
I don't think that question makes any sense. There's tons of stuff in the standard library which assumes a Sequence is neither of those. If you want to have those be type-safe argument to contains, you'll need more protocols that derive from Sequence.
Because for everything that's provided to us for Collection, we need to go implement the Sequence version ourselves. It's not respectful of everyone's time, especially when people making the decision to work on Collection are getting paid well for it.
Let me rephrase—what type exists which can conform to Sequence but not Collection for which this contains API implemented on Sequence would behave usefully while relying on only the guarantees of that protocol?
It’s good that you brought that up. There’s a lot I could say about these types. But that’s for another time.
Saliently for this conversation, though, these types should be random access collections, but they are not—and most if not all of the technical hold-up comes down to that. (There are not sufficient semantic guarantees made by Strideable such that it is possible to actually implement random access when striding over values of an arbitrary Strideable type.)
I say that this is salient here because, if we were to vend a “plain” Collection conformance to make the existing contains available for stride types, or if we were to make contains available on all Sequence types for that purpose as suggested above, we would be exacerbating rather than solving @sky’s issue which prompted this thread. Namely, there would be yet another O(n) implementation of an algorithm that users will want to reach for that’d be wildly inefficient for the most common strides.
Hence my question: is there an example of a type which can conform to Sequence but not Collectionfor which this contains API implemented on Sequence would behave usefully—and thus be “respectful” to make available so that users don’t have to write their own?
The stride types don’t fit the bill because, to my mind at least, it is much better to have the user manually call isMultiple(of: 3) to make their own efficient version of contains for an integer stride-by-3 instance, than to vend an O(n) implementation which will repeatedly add 3.