Pitch: Reform SetAlgebra

When SetAlgebra was designed to cover Set and OptionSet, @gribozavr and I did a fairly complete analysis of the set space. We ended up with SetAlgebra because at the time a general solution was seen as prematurely adding complexity. The whiteboard pictures are here, and I don’t remember everything but they do show that the space includes distinctions other than just whether the set is iterable. In particular, some sets can be inverted, and some can’t.

As for the accessibility of the terms “intensional” and “extensional”, FWIW, they are totally unfamiliar to me and I consider myself pretty well-versed in nerdisms.

14 Likes

the fact that there are this many people saying they don’t know the terms, which i assume is a pretty experienced subset of swift users, should tell us these are terrible name choices

3 Likes

That was probably the right call at the time, but the situation has changed since – now we know more about how move-only types will work, we know that we must change SetAlgebra (or rule out any set containing a move-only type).

We can either change it by introducing a protocol hierarchy, or by ditching the current capability of retrieving the existing set element when inserting. Since the current arrangement also rules out one useful set type in particular, and that the getting-back-an-exsting-element feature is useful, I feel like it tips it towards finer granularity being worthwhile.

I think this needs a slight extra qualification: only some sets can be inverted and return Self, right? A bitset or predicate set can return Self, but Set can't, for example. But you could invert a Set by returning a PredicateSet. That's one of the nice features of predicate sets – they can act as an adaptor on any other set.

(If inversion returning Self were particularly useful, I guess you could add an Inverted associated type, defaulted to PredicateSet. Probably overkill though.)

3 Likes

Just throwing this here: Yet another interesting precedent is Iterable used in CaseIterable.

Yes, I should have said “inverted in place.” Anyway, the larger point here is that if you want to figure out the right protocols for covering the domain of sets, you need to list and analyze the known important set-like data structures. IIUC part of the cited motivation for this proposal is to avoid locking the language into a refinement hierarchy that doesn’t support all the important set representations. Predicate sets are definitely part of that picture, but just considering Set<T> and predicate sets is probably not enough.

1 Like

Well that one instance was retired and FWIW, speaking as an author of that name I wouldn’t support using it as precedent.

2 Likes

Since we're now past branch date and this seems to need a bit more iteration to reach consensus, I'm going to close this out for now.

I just wanted to recap what this means for move-only types in the future (apologies for any mangling of this description):

The thinking is that when move-only types are introduced, there will be something like a Copyable protocol, to which all types implicitly conform, including all types pre the version that introduces move-only types. But new types introduced will be able to "opt out" of this implicit conformance, in order to declare themselves move-only.

This also means conformance to protocols can be conditionalized. So Set: SetAlgebra would become something like Set: SetAlgebra where Element: Copyable. Thus, sets of move-only types wouldn't conform to SetAlgebra.

You can either consider this not too big a deal (if you don't think SetAlgebra is an especially important a protocol) or an issue that will need to be fixed when we introduce these new features by deprecating SetAlgebra and replacing it with two new protocols as proposed here (but needing two new names... SetAlgebra already being taken).