[ruby-core:102040] [Ruby master Feature#16989] Sets: need ♥️

[duerst@it.aoyama.ac.jp]

Issue #16989 has been updated by duerst (Martin Dürst).


marcandre (Marc-Andre Lafortune) wrote in #note-26:
> I still don't see the benefit of not simply having `Set` in core.

One direction that distinguishes Ruby from some other programming languages is big classes. A typical example is that there's no `Stack` class, the stack interface is just part of `Array`. I don't know the history, but I think the original idea was to make the set interface also be part of Array. Your `ary & set` example also alludes to that idea. Most of that interface (maybe all) is currently available, but it's not very efficient. Using `Hash` for sets eliminates the efficiency problem, as we know.

> Moreover, does this make `ary & set` possible? efficient?

I haven't checked the details, but it shouldn't be too difficult to implement this, in a reasonably efficient way. If there are any efficiency problems, they would be on the Array side, not on the Hash side.

Another advantage of using Hash may be that we can get to a syntax that is very close to the actual Mathematical set syntax. We would like to write `{1, 2, 3}`, which may even be possible. At the least, it should be possible to move to the following: `{1 => Hash::DummyValue, 2, 3}`, i.e. if the first key has a special value, then the remaining values can be left out. We may want to choose a better name for `Hash::DummyValue`, maybe something like `Hash::SetDummy`.



----------------------------------------
Feature #16989: Sets: need ♥️
https://bugs.ruby-lang.org/issues/16989#change-89892

* Author: marcandre (Marc-Andre Lafortune)
* Status: Assigned
* Priority: Normal
* Assignee: knu (Akinori MUSHA)
----------------------------------------
I am opening a series of feature requests on `Set`, all of them based on this usecase.

The main usecase I have in mind is my recent experience with `RuboCop`. I noticed a big number of frozen arrays being used only to later call `include?` on them. This is `O(n)` instead of `O(1)`.

Trying to convert them to `Set`s causes major compatibility issues, as well as very frustrating situations and some cases that would make them much less efficient.

Because of these incompatibilities, `RuboCop` is in the process of using a custom class based on `Array` with optimized `include?` and `===`. `RuboCop` runs multiple checks on Ruby code. Those checks are called cops. `RuboCop` performance is (IMO) pretty bad and some cops  currently are in `O(n^2)` where n is the size of the code being inspected. Even given these extremely inefficient cops, optimizing the 100+ such arrays (most of which are quite small btw) gave a 5% speed boost.

RuboCop PRs for reference: https://github.com/rubocop-hq/rubocop-ast/pull/29
https://github.com/rubocop-hq/rubocop/pull/8133

My experience tells me that there are many other opportunities to use `Set`s that are missed because `Set`s are not builtin, not known enough and have no shorthand notation.

In this issue I'd like to concentrate the discussion on the following request: `Set`s should be core objects, in the same way that `Complex` were not and are now. Some of the upcoming feature requests would be easier (or only possible) to implement were `Set`s builtin.



-- 
https://bugs.ruby-lang.org/