SE-0270 (Review #2): Add Collection Operations on Noncontiguous Elements

[dabrahams (Dave Abrahams)]

@nnnnnnnn

dabrahams:
Why is the first method's first parameter a RangeSet? Its algorithm will work with any representation of a set of a collection's indices. In fact, all it needs is a predicate that tells us whether the element at a given index should be gathered.

This isn't really true — there's going to be a significant difference between performing a gather when using a RangeSet to represent the indices vs a predicate. In particular, using a predicate for the common cases of an empty range, a single element, or a single range of elements will require iterating over the entire collection, while an algorithm that is designed to work with a RangeSet will be able to perform the gather with a single rotation, or to skip the operation entirely. These aren't Big-O differences, but they are differences for the most common intended usages of this method.

Ahh… well, now this comes down to what we mean by “the algorithm.” I view what you're doing here as composing two generic algorithms—gather and rotate—to create a specialized version of gather for RangeSet. This specialization is almost certainly an optimization for empty RangeSets and probably also for those containing everything in a single range. Nothing wrong with that: probably there should be a version of the algorithm specialized for RangeSet, eventually. I realize this is highly subjective, but I just can't get over the feeling that shipping it without the generic gather and rotate is backwards. If we just implement the generic algorithms, they're useful right now for RangeSet, Set<Index>, and predicates. The specialization for RangeSet is nice-to-have, but I consider the fundamental generic algorithms essential.

There is a generalization possible — this kind of optimization doesn't require a RangeSet per se, but a type that can vend a collection (or possibly a sequence?) of sorted, nonoverlapping ranges. A protocol that describes such a type would more or less codify the implementation of RangeSet into a protocol, however, and it's not clear to me what other types would usefully conform.

Me neither, and to boot, I don't think it's a sensible concept. We don't really have an optimization strategy when you get beyond a single contiguous range, do we? That suggests that being sorted isn't even important. But even if we did have such a strategy, there's not enough in such a concept to justify its existence as a protocol; we'd just want an algorithm that accepted a Collection of ranges, with the precondition that it was sorted. Thinking through how this concept (and the more-general PredicateSet) would play out is what convinced me to propose the predicate version of gather instead of pushing for preotocols.

There is definitely a place for a predicate-based version of gather . While I don't agree that the (Element, Index) -> Bool version that you suggest as the "one true gather" can do everything we need, it does point to a serious issue with extending the use of the standard library's typical (Element) -> Bool predicates to the realm of mutating collection methods. If this is indeed a problem to solve, we're already in trouble, as we've added removeAll(where:) with only an element-based predicate, and don't have a way of working with indices at all.

For this reason, I think it makes sense to remove the gather(at:where:) method from this proposal and look at finding the right way to handle this, for gather , removeAll , and any other mutating collection methods we might add in the future.

Instead of just saying you don't agree with it, maybe you could explain what's wrong with the binary predicate approach. I haven't heard anything that convinces me there's a better form for the “one true generic gather.” Build as many specialized/convenience implementations as you like on top of it, but AFAICT, it's still the one.

As an additional note, your examples of how convoluted the code is to convert a Set of indices into a RangeSet are quite illustrative. That is certainly a common operation that the type should support directly, likely by bringing back the RangeSet initializer that takes a sequence of indices and the collection that they index.

Now we're coupling separate concerns again.

How about we start by making it unnecessary to build a RangeSet if you already have a set of indices, and see if people need it, and then really think about how to do this right. It seems to me that if anything, the method that does that construction should be on Collection rather than RangeSet, since a RangeSet of indices is potentially relevant to every Collection but there are many RangeSets that are completely unrelated to any Collection.

dabrahams:

Is RangeSet Really an OK Name?

I disagree with the reasoning expressed here. There's no need to give a set of ranges another name, as it has already has a name: Set<Range<T>> .

No; since a Range<T> is not necessarily Hashable, you can't always form that type. So to make a generic set of any Range type, you'd build it just like your RangeSet, as a sorted data structure, but it would semantically be a set of Range<T> rather than a set of T.

But I also think this is some kind of logical fallacy I don't know the name of. The fact that you can't ensure nobody will ever misinterpret a name doesn't mean you shouldn't try to head off the really easy misinterpretations:

Adding an extra word to the name RangeSet also doesn't meaningfully disambiguate these things — if someone is confused that a RangeSet is literally a set of ranges, couldn't someone else reasonably be confused that a RangeBasedSet is that same thing?

This sort of thing is always a matter of degree. Sure, someone else could reasonably be confused, but it's a whole lot less likely. The word “based” is a good cue that Range is playing a different role than Element, because—among other things—RangeBasedSet is a worse name for a set of ranges than RangeSet. If nothing else, it's a prompt to ask yourself, “what is the word ‘based’ adding here?” and then be motivated to find out what the name means.

dabrahams:

RangeSet treats Range s as sets; should we name operations accordingly?

I think this approach leads to a less discoverable, less understandable set of methods for common operations. It is true that you can think of a single Range as a contiguous set of indices, but that doesn’t require that we shift all Range -related API to treat them as sets.

That statement reveals a fundamental difference in the way we're understanding most of the naming questions here. From my point of view, the APIs here are only “Range-related” to the same extent that Array<T>.indices is: Range is just a participating type and says nothing about the semantics or role of the range instance in the API.

Even if there were no Collection protocol forcing us not to encode the specific type in the name indices, we would never have called it Array<T>.range because we have a more-specific relevant and meaningful thing to say about it than simply reflecting its type. In the same way, all of the ranges participating in these APIs play a role of contiguous set of element values.

So it's about the roles things play. If you're going to argue that rangeSet.insert(contentsOf: someRange) is more understandable (and discoverable, but that is much lower priority) than rangeSet.formUnion(someRange), then I think you need to explain why we shouldn't have someSet.insert(contentsOf: someOtherSet). I could totally be convinced that's how we should spell that operation, but I cannot imagine any good argument for spelling these two APIs, which have the same semantics, inconsistently.

After all, you can apply the same reasoning to a single element of a Set , but we don't add individual members to a set by calling mySet.formUnion("new element") .

Sorry, I don't understand this argument. The weirdness of OptionSet aside, It seems to rely on a false equivalence.

dabrahams:

RangeSet([0..<10, 10..<20])

Doesn't look symmetric with the previous one, and seems to imply we're building a set of ranges. Should it be:

RangeSet(union: [0..<10, 10..<20])

I'm not opposed to your point about adding a label to the parameter, though I don't think it's strictly necessary. init(unionOf:) or init(merging:) both seem appealing.

I don't think it's “strictly necessary” either. The question is, what is the best API, and why? If you're not sure, let's talk through the advantages and disadvantages of each one.

dabrahams:

The obvious alternatives are s.formUnion(someRange) and s.subtract(someRange) , which are both consistent with the set role of the parameter and more compact at the use site. I used to be rather ambivalent about suggesting this change, but seeing the usage written out, it now looks like a no-brainer to me.

As stated above, I'm not keen on this renaming. The type needs methods for working with individual ranges, and renaming them in pursuit of consistency with SetAlgebra would hide them from people who are looking for methods they recognize.

I'm sorry, I must be missing something. That argument seems to be based on the idea that your design is already out there in wide use or something? If there's anything extant that could set an expectation, it's the prior art that semantic union operations on sets include the word “union” in their names.

contiguousSubsets is a step in the wrong direction — the elements of that collection are individual ranges, not sets, even if you can construe them in that way. This feels like an over-emphasis of one somewhat tortured perspective on the fact that a single range can be used semantically as the base case for a RangeSet .

This again reflects our fundamental differences with regard to naming. We wouldn't name an API Array<T>.ints just because it returns a collection of Int. The fact that this API returns a collection of Range is not an argument for calling it ranges, as far as I can tell. See also my reply to John.

dabrahams:

a.range(at: i) is misleading; it strongly implies a is a collection of Range s. The name I originally suggested to Nate was a.rangeOfElement(at: i) , but I actually think a.regionOfElement(at: i) is more appropriate (see last bullet). This is an example where spending a few characters to avoid a potential misreading is totally worth it. Clarity is more important than brevity .

I worry that the medicine of adding this method to Collection is worse than the disease it was intended to cure. This may just need to be cut. I'm definitely not looking to add a new term of art at this point — coming up with a term like "region" isn't necessary to describe something that we already describe as a "range".

As I've been trying to say, we don't already describe a range of positions in a collection by simply saying “range.” There's no precedent in Swift for talking about “a range of a collection” as far as I know, and to use it that way would implicitly establish a new term of art. I'm not attached to region, and actually, we already have a term of art for this: “subrange.” We intentionally used that word instead of range when naming removeSubrange because it is clearer:

var rs = [1..<2, 3..<4, 5..<6]
rs.removeRange(1..<2)     // if we had made the wrong naming choice
print(rs.contains(1..<2)) // prints "true"!

dabrahams:

I've never been pleased with removeAll(where: p) [...]

removeAll(where: p) is more or less a brand-new method — I think we'd need to show actual harm being caused by the name before we could consider renaming. IIRC the "all" part of the name is to indicate that more than one element may be removed, explicitly distinguishing it from remove(at:) and remove(Element) .

I understand the rationale behind the name, and I know it's new-ish to RangeReplaceableCollection, which is why I feel somewhat more comfortable challenging its use as a precedent for RangeSet—less extant material depends on it than something that's been around for a few releases. The problem with using “all” to indicate that more than one element may be removed is that it even more strongly implies that all the elements will be removed. removeElements(where:) would do the job without encouraging the wrong interpretation. This is obviously not something to do lightly, but if we are to make a change, sooner is better than later and I wanted to raise it, but perhaps it should go to a different thread.

Reading more about scatter and gather, there is a bit of an unfortunate overlap in naming. I'm not totally convinced that any of these specific alternatives wins outright for me. move and moveElements feel a bit problematic, because of those words' relationship to moving from unsafe memory and Swift's future move semantics, but I'm not sure those problems are disqualifying. I do like Kyle's proposed shift name, since it works well for single elements, single ranges, and discontiguous elements. The conflict I know of is with that name Javascript's shift / unshift , but we already have names for those operations.

Yeah, I'm not sure we've hit on the answer yet either. Other ideas might spring from words like “arrange” or “condense.”