Skip to content

Set is a core class in 4.0 and keeps insertion order

Level: 201 · working knowledge: the 4.0 change, and the hash/eql? contract behind every element

One line: In Ruby 4.0 Set needs no require and is written in C, Set[3, 1, 2] iterates as 3, 1, 2, and an element is identified by hash and eql? — Python's set is a builtin too, but it iterates in hash-table order and refuses an unhashable element at the door.

Before 4.0, Set lived in set.rb, a Ruby-level class wrapping a Hash, and a program said require "set" (autoloaded on first use from 3.2) (Not machine-checked here.). In 4.0 it is a core class implemented in C: defined?(Set) answers before any require, require "set" returns false because there is nothing left to load, and Set.instance_method(:add).source_location is nil because there is no Ruby file to point at. What did not change is the model underneath: a Set behaves as a Hash of keys (Not machine-checked here.). That gives it Hash's insertion order, so to_a, first and each walk the elements in the order they were added; it gives it Hash's identity rule, so two elements are one when eql? says so and their hash values agree — == alone does not count — and it gives it Hash's blind spot, an element mutated after insertion is not found until reset rehashes. The operators |, &, - and ^ return Sets, the predicates <=, <, subset? and disjoint? compare them, === makes a Set usable in when, and the Enumerable methods (map, select, sort) return Arrays, as they do for any Enumerable. SortedSet is gone — removed in 3.0, a gem now (Not machine-checked here.).

Verified output of set_is_a_core_class_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

 1. defined?(Set), require "set"  (core: nothing to load)            ["constant", false]
 2. Set.instance_method(:add).source_location  (C, no file)          nil
 3. Set[3, 1, 2], [3, 1].to_set, Set.new(1..3)                       [Set[3, 1, 2], Set[3, 1], Set[1, 2, 3]]
 4. Set[3, 1, 2].to_a; after delete(1) then add(1)                   [[3, 1, 2], [3, 2, 1]]
 5. s = Set[1, 2]; s << 3 (returns s); s.add?(3); s.add?(4)          [Set[1, 2, 3, 4], nil, Set[1, 2, 3, 4]]
 6. Set[1, 2] | Set[2, 3], &, -, ^                                   [Set[1, 2, 3], Set[2], Set[1], Set[1, 3]]
 7. Set[1] <= Set[1, 2], subset?, <, Set[1].disjoint?(Set[2])        [true, true, true, true]
 8. Set[1, 2] == Set[2, 1], Set[Set[1]].include?(Set[1])             [true, true]
 9. Set[1, 2] === 2; case 2 when Set[1, 2]                           [true, "in"]
10. map, select, sort, | : the class each returns; select's owner    [Array, Array, Array, Set, Enumerable]
11. s.delete(9) (returns s, no error), s.delete?(9)                  [Set[1, 2, 3, 4], nil]
12. Set[1].freeze << 2                                               FrozenError: can't modify frozen Set: Set[1]
13. Set[x, x'].size for Plain, ByValue (eql?+hash), EqOnly (==)      [2, 1, 2]
14. Set[[1, 2]].include?([1, 2]), Set[1, 1.0, true].size             [true, 3]
15. arr << 2 after Set[arr]: include?([1, 2]), then after reset      [false, true]
16. defined?(SortedSet)  (removed in 3.0; a gem now)                 nil
17. Set.new("hello".chars).to_a, Set[3, 1, 2].first(2)               [["h", "e", "l", "o"], [3, 1]]
18. Set[1, 2] <=> Set[1, 2, 3], Set[1] <=> Set[2]                    [-1, nil]

Reading the output

Rows 1–2 are the 4.0 facts: the constant exists with nothing required, the require returns false, and the C implementation has no source location.

Rows 3–4: three ways to build a Set, inspect in the Set[...] form 4.0 prints, and the order. Set[3, 1, 2] walks as 3, 1, 2; deleting 1 and adding it back moves it to the end.

Rows 5–9 are the algebra. << returns the Set (so it chains) and add? returns nil when the element was already there; the four operators and the four predicates do what their names say; two Sets with the same elements are ==, and a Set can be an element of a Set; === is membership, which is what when Set[1, 2] tests.

Rows 10–11: map, select and sort come from Enumerable and return Arrays, while | returns a Set; delete of a missing element is not an error, and delete? answers nil for one.

Row 12: a frozen Set raises FrozenError on <<.

Rows 13–15 are the identity rule. Two Plain objects with the same value are two elements; two ByValue objects, which define eql? and hash, are one; two EqOnly objects, which define only ==, are still two. An Array is a fine element because Array defines both. 1, 1.0 and true are three elements. And the mutated-Array element of row 15 is invisible to include? until reset.

Rows 16–18: SortedSet is gone; a Set built from the characters of "hello" keeps them in first-seen order; <=> orders Sets by inclusion and answers nil for two Sets neither of which contains the other.

Compared with Python

The twin asks set and frozenset the same eighteen questions. set is a builtin (rows 1–2), with a literal {3, 1, 2} — but {} is a dict, so the empty set is set(). Row 4 is the difference in the title: a Python set iterates in hash-table order, not insertion order. Small integers hash to themselves, so {3, 1, 2} walks as 1, 2, 3 and {8, 1} as 8, 1 — and for strings the order changes from one process to the next (Not machine-checked here.), which is why row 17 sorts and why the ordered-dedupe idiom is dict.fromkeys, not set. add returns None and there is no add? (row 5); the operators and predicates match Ruby's (rows 6–7); a set cannot hold a set — {{1}} is a TypeError — and frozenset is the hashable form (row 8): it can sit inside a set, and it equals the plain set with the same elements. Comprehensions build sets, and sorted gives a list (row 10); discard is Ruby's delete and remove raises (row 11); frozenset has no add at all (row 12). Rows 13–14 are where the rule differs: Python identifies elements by __eq__ and __hash__, and defining __eq__ without __hash__ makes a class unhashable, so EqOnly cannot enter a set at all — Ruby lets it in as two elements. A list is refused the same way, so a stale element (row 15) cannot happen. And {1, 1.0, True} is one element, because 1 == 1.0 == True and all three hash alike; the Python library's Comparing int and float ↗ measures that equality on its own. Python has no sorted set either (row 16: sorted, or bisect into a list), and no <=>: two incomparable sets answer False to both < and > (row 18).

Verified output of set_is_a_core_class_py.py — regenerated by tools/run_examples.py, never hand-typed.

 1. "set" in dir(builtins), type(set()), type({})                    [True, 'set', 'dict']
 2. hasattr(set.add, "__code__")  (built in: no Python source)       False
 3. {3, 1, 2}, set([3, 1]), frozenset(range(1, 4))                   [{1, 2, 3}, {1, 3}, frozenset({1, 2, 3})]
 4. list({3, 1, 2}); after discard(1), add(1); list({8, 1})          [[1, 2, 3], [1, 2, 3], [8, 1]]
 5. s = {1, 2}; s.add(3) (returns None); 3 in s; s.add(4)            [None, True, None]
 6. {1, 2} | {2, 3}, &, -, ^                                         [{1, 2, 3}, {2}, {1}, {1, 3}]
 7. {1} <= {1, 2}, issubset, <, {1}.isdisjoint({2})                  [True, True, True, True]
 8. {1, 2} == {2, 1}; {{1}}; {frozenset({1})}; frozenset({1}) == {1} [True, TypeError, True, True]
 9. 2 in {1, 2}; match 2: case x if x in {1, 2}                      [True, 'in']
10. comprehension, filter, sorted, | : the type each returns         ['set', 'list', 'list', 'set']
11. s.discard(9) (returns None, no error), s.remove(9)               [None, KeyError]
12. frozenset({1}).add(2)                                            AttributeError
13. len({x, x'}) for Plain, ByValue (__eq__+__hash__), EqOnly        [2, 1, 'TypeError']
14. {[1, 2]}; (1, 2) in {(1, 2)}; len and repr of {1, 1.0, True}     [TypeError, True, 1, {1}]
15. a list is refused at insertion (row 14): no stale element        -
16. no sorted set: sorted(s), or bisect.bisect([1, 3, 5], 4)         [[1, 2, 3], 2]
17. sorted(set("hello")), list(dict.fromkeys("hello"))               [['e', 'h', 'l', 'o'], ['h', 'e', 'l', 'o']]
18. {1, 2} < {1, 2, 3}, {1} < {2}, {1} > {2}  (no <=>)               [True, False, False]

Try it

  1. Two days of attendance, each a list of names with duplicates: use Sets to print who came both days, who came only on Monday, only on Tuesday, on exactly one day, and on either day, and check that the both-days Set is a subset of Monday's. Keep first-seen order where a Set gives it to you, and say where you had to sort.
  2. Reimplement Array#uniq as first_seen(array) with a Set as the "seen" tracker and add? as the test, then run it on [3, 1, 3, 2, 1] and compare with uniq and with to_set.to_a — all three should agree, and you should be able to say why the third one does.
Solution to 1

set_is_a_core_class_kata_rb.rb in full — pasted here by tools/run_examples.py from the file CI runs.

# Kata: attendance over two days -- who came both days, one day only, either day.
# A Set drops the duplicates and, in Ruby, keeps first-seen order. The results of
# the set operators are sorted for the printout, so the answer does not depend
# on which operand the operator happens to walk first.

monday  = %w[ada bob cy ada dee]
tuesday = %w[dee bob eve bob fay]
m = monday.to_set
t = tuesday.to_set

puts "monday          #{m.to_a.inspect}  (duplicate ada dropped, order kept)"
puts "tuesday         #{t.to_a.inspect}  (duplicate bob dropped)"
puts "both days       #{(m & t).sort.inspect}"
puts "monday only     #{(m - t).sort.inspect}"
puts "tuesday only    #{(t - m).sort.inspect}"
puts "exactly one day #{(m ^ t).sort.inspect}"
puts "either day      #{(m | t).sort.inspect}"
puts "both-days is a subset of monday? #{(m & t) <= m}"
puts "first seen, either day: #{(monday + tuesday).to_set.to_a.inspect}"

Verified output of set_is_a_core_class_kata_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

monday          ["ada", "bob", "cy", "dee"]  (duplicate ada dropped, order kept)
tuesday         ["dee", "bob", "eve", "fay"]  (duplicate bob dropped)
both days       ["bob", "dee"]
monday only     ["ada", "cy"]
tuesday only    ["eve", "fay"]
exactly one day ["ada", "cy", "eve", "fay"]
either day      ["ada", "bob", "cy", "dee", "eve", "fay"]
both-days is a subset of monday? true
first seen, either day: ["ada", "bob", "cy", "dee", "eve", "fay"]

See also