Add Set#pick and Set#pop
A very common operation on sets is to take an arbitrary element from them at O(1) cost. I know typically
it's suggested that library additions go out as a gem to see community review. However, to me it seems
to be a glaring omission to lack such an operation on a built-in, fundamental data structure, so I've
gone straight to the bug tracker.
I wasn't too sure which method names to use as I've often heard "take" in lieu of "pop," so I just used the
names Wikipedia uses. Consider them flexible. "Pick" selects an arbitrary element, and "pop" selects and
I've provided a very simple patch that implements the necessary behavior. Thoughts?
#1 [ruby-core:35645] Updated by Marc-Andre Lafortune almost 6 years ago
- Priority changed from Normal to 3
There is no difference between your
Set#pick and the existing
Set#first. As such, there is no need for
One can get the effect of
Set#pop by calling the existing
Set#delete with the result of
Set#first (with the same O(1) efficiency).
I find problematic that a method called
pop would take the first element; it could be renamed to
shift, say, or take the last element instead. More importantly, though, I am not convinced that this functionality is that frequently used.
#2 [ruby-core:35714] Updated by Michael Edgar almost 6 years ago
The ruby-core e-mail I sent appeared to not attach to the issue on Redmine. I apologize for the noise.
The existence of
Set#first is an artifact of Set including Enumerable and the very idea of "first" on a Set is an odd notion. A set by itself does not have ordering. I have implemented it to pick the first element because it is simplest, but someone calling "pick" on a set does not care which element it is. If one would prefer implementing it as an alias to first, I'd be fine with that.
On a personal note to emphasize why I find this issue compelling: one reason I enjoy using Ruby because often my code reads just as I would describe it to a colleague - reading "element = set.first" is not something many would agree is a sensible way to describe the act of picking an arbitrary element from a mathematical set.
Yes, one could implement #pop with #delete and #first, which again relies on a notion of ordering in a set. One can implement #proper_subset with #subset and a comparison, as can one implement #proper_superset with #superset and a comparison. Yet they are in the Set class because they are fundamental operations. #add? and #delete? can also be implemented with #add and #include?/#delete and #include? respectively, yet they are included in the Set class because they are useful and common operations on a set.
pop is too close the Array method of the same name, I understand the confusion, but I don't get why picking first/last makes a difference. Anyone asking to remove an arbitrary element from a Set surely doesn't care where it lies in an underlying hash table. I am surprised one would argue that the Set class rarely needs the notion of selecting an element from it. Rarely am I presented with an algorithm using sets that does not require simply getting an element or picking one out of a set.
#3 [ruby-core:35724] Updated by zimba tm almost 6 years ago
#pop is often associated to stack operations, which implies an order. Unless a better name is found, isn't set.delete(set.take) enough ?
#take can be an alias of #first but I'm not sure if Enumerable should be included in Set in the first place. In my POV, Enumerable is for elements that have a particular order.
#6 [ruby-core:43447] Updated by Thomas Sawyer almost 5 years ago
I would expect
Array#pick to work too. Which then leads one to think Array might support the equivalent of
Set#pop as well. But since Array already has
#pop it's not really a good idea to reuse same term, although in the case of Set,
#pop might be an alias for such method.
So what might such methods be called then? Well, if we look at hand-dandy
Looks like it uses #at_rand/#at_rand! and #pick/pick!, where #pick has the additional option of returning a random subset if a size is given as argument.