Data.Set
module Data
Immutable collections of distinct elements.
Opt-in: nothing here is in scope until using Data.Set, which brings both flavours below into scope at once.
using Data.SetMembership is decided by structural equality: the same equality == and map keys use, so records and tuples are compared by value, not identity. Every method answers with a new set; the ! forms (add!, delete!) build a new set and rebind the receiver variable rather than modifying anything in place.
let tags = Set.from(["kex", "beam", "kex"])
tags.count # => 2
tags.contains?("beam") # => true
tags.add("erlang").items # => ["beam", "erlang", "kex"]There are two flavours, differing only in how they store their elements:
Set sorted, so iteration is in ascending element order and the
elements must be Orderable.
UnorderedSet hash-backed, so membership does not pay for ordering and
the elements need only be comparable. Iteration order is
unspecified: never write a test against it.Reach for Set when you will read the elements back out, and for UnorderedSet when the set exists to answer contains? quickly.
== between two sets needs no overload of its own: each flavour keeps its backing canonical (sorted and duplicate free, or a map) so comparing the records structurally already IS set equality.
Both wrap structures the runtime already has (a list and a map), so no set is opaque: .items is always a real list you can hand to anything.
Those two backings are also the ones the BEAM's own set libraries use: a Set is laid out exactly like an ordsets term and an UnorderedSet exactly like a sets v2 term, so the operations here can be routed to the native BIFs later without changing what a set IS. What rules out adopting gb_sets instead is the other backend: a tree-walk interpreter cannot produce an opaque BEAM term, and a set that only one backend can build is not a set the prelude can offer.
record Set<A>
A set whose elements are kept sorted and duplicate free.
Build one with Set.from rather than by hand: the record literal does no deduplication and no sorting, and every method here relies on both. Reading items back is the field itself, so handing a set's elements to list code costs nothing.
Set.from([3, 1, 2]).items # => [1, 2, 3]Fields
items[A]optional
record UnorderedSet<A>
A set backed by a map from each member to true; its keys ARE the elements.
Build one with UnorderedSet.from. Iteration order is whatever the map hands back, so use items.sort when you need a stable order.
UnorderedSet.from([3, 1, 2]).contains?(2) # => trueFields
slots{A: Bool}optional
module Data.Set
Constructors for the sorted Set.
function from
Builds a sorted set from a list, discarding duplicates.
This is the normal way to make a Set. Deduplication goes through a map rather than List.uniq: map keys are unique under exactly the structural equality a set wants, and each element costs one insertion instead of a scan of everything kept so far.
from(items)Parameters
items[A]- the elements, in any order and with any duplicates
Returns: Set<A> — the distinct elements, sorted
Examples
Set.from([3, 1, 2, 3]) # => Set(1, 2, 3)
Set.from("hello".chars) # => Set(e, h, l, o)Removing duplicates from a list
Set.from(["b", "a", "b"]).items # => ["a", "b"]constant empty Set<A>
The set with no elements. Also the Monoid identity, so s.combine(Set.empty) is s.
module Data.UnorderedSet
Constructors for the hash-backed UnorderedSet.
function from
Builds an unordered set from a list, discarding duplicates.
Nothing is sorted, so unlike Set.from this does not require the elements to be Orderable.
from(items)Parameters
items[A]- the elements, in any order and with any duplicates
Returns: UnorderedSet<A> — the distinct elements
Examples
UnorderedSet.from([3, 1, 2, 3]).count # => 3A fast membership test over a large list
let stopWords = UnorderedSet.from(["the", "a", "of"])
words.reject { |w| stopWords.contains?(w) }constant empty UnorderedSet<A>
The unordered set with no elements. Also the Monoid identity.
make Set<A> implements Enumerable, Foldable, Monoid, Showable
reduce
Folds over the elements in ascending order.
This is Set's Enumerable primitive; each, find, any? and the rest are built on it. The collection-returning operations are overridden below, because Enumerable's defaults answer with a list.
reduce(acc, f) : B -> (B -> A -> B) -> BParameters
accA- the initial accumulator
fB -> A -> B- combines the accumulator with each element
Returns: B — the final accumulator
Examples
Set.from([1, 2, 3]).reduce(0) { |sum, x| sum + x } # => 6combine
Combines two sets by union. The Monoid operation.
combine(other) : Set<A> -> Set<A>Parameters
otherSet<A>- the set to combine with
Returns: Set<A> — every element of either set
Examples
Merging many sets into one
[Set.from([1]), Set.from([2]), Set.from([1, 3])]
.reduce(Set.empty) { |acc, s| acc.combine(s) }
# => Set(1, 2, 3)contains?
Returns true when value is a member.
contains?(value) : A -> BoolParameters
valueA- the element to look for
Returns: Bool — true when it is present
Examples
Set.from([1, 2, 3]).contains?(2) # => true
Set.from([1, 2, 3]).contains?(9) # => falseFiltering a list against an allow-list
let allowed = Set.from(["get", "post"])
methods.filter { |m| allowed.contains?(m.lowerCase) }add
Returns a new set with value added. Adding an element that is already a member changes nothing: that is what makes a set a set.
Use add! to rebind the receiver variable.
add(value) : A -> Set<A>Parameters
valueA- the element to add
Returns: Set<A> — a set including value
Examples
Set.from([1, 2]).add(3) # => Set(1, 2, 3)
Set.from([1, 2]).add(2) # => Set(1, 2)Accumulating as you go
var seen = Set.empty
ids.each { |id| seen.add!(id) }delete
Returns a new set without value. Removing something that is not a member changes nothing.
Use delete! to rebind the receiver variable.
delete(value) : A -> Set<A>Parameters
valueA- the element to remove
Returns: Set<A> — a set without value
Examples
Set.from([1, 2, 3]).delete(2) # => Set(1, 3)
Set.from([1, 2, 3]).delete(9) # => Set(1, 2, 3)union
Returns every element of either set.
union(other) : Set<A> -> Set<A>Parameters
otherSet<A>- the other set
Returns: Set<A> — the union
Examples
Set.from([1, 2]).union(Set.from([2, 3])) # => Set(1, 2, 3)Collecting every tag used across posts
posts.reduce(Set.empty) { |all, p| all.union(Set.from(p.tags)) }intersect
Returns the elements both sets have.
intersect(other) : Set<A> -> Set<A>Parameters
otherSet<A>- the other set
Returns: Set<A> — the intersection
Examples
Set.from([1, 2, 3]).intersect(Set.from([2, 3, 4])) # => Set(2, 3)
Set.from([1]).intersect(Set.from([2])) # => Set()Which requested permissions the user actually has
requested.intersect(granted)difference
Returns the elements of this set that other does not have.
Order matters: a.difference(b) and b.difference(a) are different questions. Use symmetricDifference when you want both answers.
difference(other) : Set<A> -> Set<A>Parameters
otherSet<A>- the set to subtract
Returns: Set<A> — the elements only this set has
Examples
Set.from([1, 2, 3]).difference(Set.from([2])) # => Set(1, 3)Which required fields are still missing
required.difference(Set.from(form.keys))symmetricDifference
Returns the elements in exactly one of the two sets: everything they do not agree on.
symmetricDifference(other) : Set<A> -> Set<A>Parameters
otherSet<A>- the other set
Returns: Set<A> — the symmetric difference
Examples
Set.from([1, 2]).symmetricDifference(Set.from([2, 3])) # => Set(1, 3)What changed between two snapshots
before.symmetricDifference(after)subset?
Returns true when every element of this set is also in other. The empty set is a subset of everything.
subset?(other) : Set<A> -> BoolParameters
otherSet<A>- the candidate superset
Returns: Bool — true when this set is contained in other
Examples
Set.from([1, 2]).subset?(Set.from([1, 2, 3])) # => true
Set.from([1, 9]).subset?(Set.from([1, 2, 3])) # => falseAn authorisation check
required.subset?(granted)superset?
Returns true when this set has every element of other. The mirror image of subset?.
superset?(other) : Set<A> -> BoolParameters
otherSet<A>- the candidate subset
Returns: Bool — true when this set contains all of other
Examples
Set.from([1, 2, 3]).superset?(Set.from([1, 2])) # => true
Set.from([1, 2]).superset?(Set.from([1, 9])) # => falsedisjoint?
Returns true when the two sets share no element.
disjoint?(other) : Set<A> -> BoolParameters
otherSet<A>- the other set
Returns: Bool — true when the intersection is empty
Examples
Set.from([1, 2]).disjoint?(Set.from([3])) # => true
Set.from([1, 2]).disjoint?(Set.from([2, 3])) # => falseChecking that two rulesets cannot both apply
allowList.disjoint?(denyList)+
Unions with another set, or with a plain list.
The list form is the everyday way to add one element without naming a method: `s ` [x]`.
+(other) : Set<A> -> Set<A>
+(other) : [A] -> Set<A>Parameters
otherSet<A> | [A]- the elements to add
Returns: Set<A> — the union
Examples
Set.from([1, 2]) ` [3] # => Set(1, 2, 3)
Set.from([1]) + Set.from([2]) # => Set(1, 2)-
Removes another set's elements, or a plain list's.
-(other) : Set<A> -> Set<A>
-(other) : [A] -> Set<A>Parameters
otherSet<A> | [A]- the elements to remove
Returns: Set<A> — the difference
Examples
Set.from([1, 2, 3]) - [2] # => Set(1, 3)
Set.from([1, 2, 3]) - Set.from([2, 3]) # => Set(1)map
Applies f to every element and returns a set of the results.
Mapping a set may collapse elements: if f sends two members to the same value, the result has one. That is not a loss of information so much as the point of a set: Set.from([1, -1]).map(~abs) has one member.
map(f) : (A -> B) -> Set<B>Parameters
fA -> B- applied to each element
Returns: Set<B> — the distinct results
Examples
Set.from([1, 2, 3]).map { |x| x * 2 } # => Set(2, 4, 6)
Set.from([1, -1]).map { |x| x.abs } # => Set(1)Collecting the distinct extensions in a file list
Set.from(paths).map { |p| p.split(".").last.or("") }filter
Returns a new set with only the elements pred accepts.
filter(pred) : (A -> Bool) -> Set<A>Parameters
predA -> Bool- the test applied to each element
Returns: Set<A> — the matching elements
Examples
Set.from([1, 2, 3]).filter { |x| x > 1 } # => Set(2, 3)reject
Returns a new set without the elements pred accepts. The complement of filter.
reject(pred) : (A -> Bool) -> Set<A>Parameters
predA -> Bool- the test applied to each element
Returns: Set<A> — the elements that failed the predicate
Examples
Set.from([1, 2, 3]).reject { |x| x > 1 } # => Set(1)make Set<A> implements Blankable
make UnorderedSet<A> implements Enumerable, Foldable, Monoid, Showable
reduce
Folds over the elements.
The order is whatever the underlying map hands back: unspecified, and not to be relied on. Use a Set when the order of the fold matters.
reduce(acc, f) : B -> (B -> A -> B) -> BParameters
accB- the initial accumulator
fB -> A -> B- combines the accumulator with each element
Returns: B — the final accumulator
Examples
UnorderedSet.from([1, 2, 3]).reduce(0) { |sum, x| sum + x } # => 6combine
Combines two sets by union. The Monoid operation.
combine(other) : UnorderedSet<A> -> UnorderedSet<A>Parameters
otherUnorderedSet<A>- the set to combine with
Returns: UnorderedSet<A> — every element of either set
contains?
Returns true when value is a member.
This is the operation the flavour exists for: a map lookup, with no ordering to maintain.
contains?(value) : A -> BoolParameters
valueA- the element to look for
Returns: Bool — true when it is present
Examples
UnorderedSet.from([1, 2, 3]).contains?(2) # => true
UnorderedSet.from([1, 2, 3]).contains?(9) # => falseadd
Returns a new set with value added. Adding an existing member changes nothing.
Use add! to rebind the receiver variable.
add(value) : A -> UnorderedSet<A>Parameters
valueA- the element to add
Returns: UnorderedSet<A> — a set including value
Examples
UnorderedSet.from([1]).add(2).count # => 2
UnorderedSet.from([1]).add(1).count # => 1delete
Returns a new set without value. Removing a non-member changes nothing.
Use delete! to rebind the receiver variable.
delete(value) : A -> UnorderedSet<A>Parameters
valueA- the element to remove
Returns: UnorderedSet<A> — a set without value
Examples
UnorderedSet.from([1, 2]).delete(1).count # => 1union
Returns every element of either set.
union(other) : UnorderedSet<A> -> UnorderedSet<A>Parameters
otherUnorderedSet<A>- the other set
Returns: UnorderedSet<A> — the union
Examples
UnorderedSet.from([1, 2]).union(UnorderedSet.from([2, 3])).count # => 3intersect
Returns the elements both sets have.
intersect(other) : UnorderedSet<A> -> UnorderedSet<A>Parameters
otherUnorderedSet<A>- the other set
Returns: UnorderedSet<A> — the intersection
Examples
UnorderedSet.from([1, 2, 3]).intersect(UnorderedSet.from([2, 3, 4])).items.sort
# => [2, 3]difference
Returns the elements of this set that other does not have.
difference(other) : UnorderedSet<A> -> UnorderedSet<A>Parameters
otherUnorderedSet<A>- the set to subtract
Returns: UnorderedSet<A> — the elements only this set has
Examples
UnorderedSet.from([1, 2, 3]).difference(UnorderedSet.from([2])).items.sort
# => [1, 3]symmetricDifference
Returns the elements in exactly one of the two sets.
symmetricDifference(other) : UnorderedSet<A> -> UnorderedSet<A>Parameters
otherUnorderedSet<A>- the other set
Returns: UnorderedSet<A> — the symmetric difference
Examples
UnorderedSet.from([1, 2]).symmetricDifference(UnorderedSet.from([2, 3])).items.sort
# => [1, 3]subset?
Returns true when every element of this set is also in other.
subset?(other) : UnorderedSet<A> -> BoolParameters
otherUnorderedSet<A>- the candidate superset
Returns: Bool — true when this set is contained in other
Examples
UnorderedSet.from([1, 2]).subset?(UnorderedSet.from([1, 2, 3])) # => truesuperset?
Returns true when this set has every element of other.
superset?(other) : UnorderedSet<A> -> BoolParameters
otherUnorderedSet<A>- the candidate subset
Returns: Bool — true when this set contains all of other
Examples
UnorderedSet.from([1, 2, 3]).superset?(UnorderedSet.from([1, 2])) # => truedisjoint?
Returns true when the two sets share no element.
disjoint?(other) : UnorderedSet<A> -> BoolParameters
otherUnorderedSet<A>- the other set
Returns: Bool — true when the intersection is empty
Examples
UnorderedSet.from([1, 2]).disjoint?(UnorderedSet.from([3])) # => true+
Unions with another unordered set, or with a plain list.
+(other) : UnorderedSet<A> -> UnorderedSet<A>
+(other) : [A] -> UnorderedSet<A>Parameters
otherUnorderedSet<A> | [A]- the elements to add
Returns: UnorderedSet<A> — the union
Examples
(UnorderedSet.from([1, 2]) + [3]).count # => 3-
Removes another unordered set's elements, or a plain list's.
-(other) : UnorderedSet<A> -> UnorderedSet<A>
-(other) : [A] -> UnorderedSet<A>Parameters
otherUnorderedSet<A> | [A]- the elements to remove
Returns: UnorderedSet<A> — the difference
Examples
(UnorderedSet.from([1, 2, 3]) - [2]).count # => 2map
Applies f to every element and returns an unordered set of the results. Elements that map to the same value collapse into one.
map(f) : (A -> B) -> UnorderedSet<B>Parameters
fA -> B- applied to each element
Returns: UnorderedSet<B> — the distinct results
Examples
UnorderedSet.from([1, 2, 3]).map { |x| x * 2 }.items.sort # => [2, 4, 6]filter
Returns a new unordered set with only the elements pred accepts.
filter(pred) : (A -> Bool) -> UnorderedSet<A>Parameters
predA -> Bool- the test applied to each element
Returns: UnorderedSet<A> — the matching elements
Examples
UnorderedSet.from([1, 2, 3]).filter { |x| x > 1 }.items.sort # => [2, 3]reject
Returns a new unordered set without the elements pred accepts.
reject(pred) : (A -> Bool) -> UnorderedSet<A>Parameters
predA -> Bool- the test applied to each element
Returns: UnorderedSet<A> — the elements that failed the predicate
Examples
UnorderedSet.from([1, 2, 3]).reject { |x| x > 1 }.items # => [1]