Set

Set is a base trait for collections that have a notion of uniques of the elements. It is defined as trait Set[A] extends Iterable[A] with SetOps[A, Set, Set[A]] with Equals. We can see that it is effectively an Iterable that has some additional operations defined in SetOps and adds a notion of equality among sets. The sub-hierarchy of Set is represented in the following diagram:

The previously mentioned SetOps adds a few methods on top of IterableOps. These methods are shown here:

• Element retrieval: contains and apply return true if this set contains a given element.
• Equality: subsetOf and subsets check whether this set is a subset of another set, or return all subsets of this set, possibly with a given size.
• Combinations with another set: intersect, &, diff, &~, concat, ++, union, and |. These methods compute the intersection, difference, or union of this and another set.

There are few classes in the hierarchy that augment Set with further properties:

• SortedSet extends Set with SortedOps[A, +C] and has two immutable and two mutable implementations—two TreeSets and two BitSets. SortedOps embodies following methods that depend on the notion of Ordering:
• Key retrieval: firstKey and lastKey return the first or last element of this collection.
• Subcollection retrieval: range, rangeFrom, rangeUntil, and rangeTo create a ranged projection of this collection, satisfying given criteria.

Because of the overloading, SortedSet has many overloaded methods defined twice, with and without ordering. If an operation is intended to be applied to the underlying unsorted Set, the type has to be coerced:

scala> import scala.collection.SortedSet
import scala.collection.SortedSet
scala> val set = SortedSet(1,2,3)
set: scala.collection.SortedSet[Int] = TreeSet(1, 2, 3)
scala> val ordered = set.map(math.abs)
ordered: scala.collection.SortedSet[Int] = TreeSet(1, 2, 3)
scala> val unordered = set.to(Set).map(math.abs)
unordered: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

Please note that direct type-ascription will not work in the case of Set because its definition is invariant:

scala> val set1: Set[Int] = SortedSet(1,2,3)
                                     ^
       error: type mismatch;
        found : scala.collection.SortedSet[Int]
        required: Set[Int]

The invariance of Set is related to the fact that Set[A] extends a function, A => Boolean, that returns true if the set contains a given element. Thus, sets can be used in places where such one argument function is expected:

scala> ordered.forall(set)
res3: Boolean = true

There are four more specific set implementations in addition to TreeSet and BitSet:

• ListSet implements immutable sets using a list-based data structure.
• The immutable HashSet realizes immutable sets using a Compressed Hash-Array Mapped Prefix-tree (CHAMP)
• The mutable HashSet and LinkedHashSet implement mutable sets using a hash table, storing the data unordered and ordered, respectively.

The sets are closely related to Map, which represents a collection with elements represented as a pair of keys and values.