Data.Set
Ordered sets, reusing the balanced-tree map.
There is no Set type. A set is exactly a Map(k, Unit), which is what the signatures below say and what the reference documents: the module is a naming layer over Data.Map, not an abstraction over it. So a set is also a map wherever one is expected, map_size and map_keys read it directly (which is how set_size and set_to_list are defined), and only the Unit value discipline of these functions keeps its values uniform.
Set algebra stays O(n log n) and preserves iteration order. Base includes this module.
Like Map, a set’s representation depends on the canonical Ord instance used to build it. The compiler classifies Ord and Hash as representation-affecting in store::coherence::is_representation_affecting. Set identity does not currently encode that instance, so programs exchanging a set across an assembly boundary must agree on its canonical ordering.
In the complexity bounds below, n is the number of elements in a set. A bound stated in comparisons excludes the cost of the Ord comparison itself.
Functions and Values
set_empty
set_empty : forall a b. Map(a, Unit, b)
The empty set. Time complexity: O(1).
set_insert
set_insert : forall a b. (b, Map(b, Unit, a)) -> Map(b, Unit, a) given Ord(b)
Add x to the set (a no-op if already present). Time complexity: O(log n) comparisons.
set_to_list(set_insert(2, set_insert(1, set_empty)))
[1, 2]
set_member
set_member : forall a b. (b, Map(b, Unit, a)) -> Bool given Ord(b)
True when x is a member of the set. Time complexity: O(log n) comparisons.
set_member(2, set_from_list([1, 2, 3]))
true
set_delete
set_delete : forall a b. (b, Map(b, Unit, a)) -> Map(b, Unit, a) given Ord(b)
Remove x from the set (a no-op if absent). Time complexity: O(log n) comparisons.
set_to_list(set_delete(2, set_from_list([1, 2, 3])))
[1, 3]
set_size
set_size : forall a b c. (Map(a, b, c)) -> Int
The number of elements. Time complexity: O(n); the underlying map does not cache its size.
set_size(set_from_list([1, 2, 2, 3]))
3
set_to_list
set_to_list : forall a b c. (Map(a, b, c)) -> List(a)
The elements in ascending order. Time complexity: O(n).
set_to_list(set_from_list([3, 1, 2, 1]))
[1, 2, 3]
set_from_list
set_from_list : forall a b. (List(b)) -> Map(b, Unit, a) given Ord(b)
Build a set from a list, dropping duplicates. Time complexity: O(n log n) comparisons for an input of n elements.
set_to_list(set_from_list([3, 1, 2, 1]))
[1, 2, 3]
set_union
set_union : forall a b c. (Map(c, Unit, a), Map(c, Unit, b)) -> Map(c, Unit, a) given Ord(c)
Every element in either set. Time complexity: O(m log(n + m)) comparisons, where m is the size of s2.
set_to_list(set_union(set_from_list([1, 2]), set_from_list([2, 3])))
[1, 2, 3]
set_intersection
set_intersection : forall a b c d. (Map(d, Unit, a), Map(d, Unit, b)) -> Map(d, Unit, c) given Ord(d)
The elements in both sets. Time complexity: O(N log N) comparisons, where N is the combined input size.
set_to_list(set_intersection(set_from_list([1, 2, 3]), set_from_list([2, 3, 4])))
[2, 3]
set_difference
set_difference : forall a b c d. (Map(d, Unit, a), Map(d, Unit, b)) -> Map(d, Unit, c) given Ord(d)
The elements of s1 that are not in s2. Time complexity: O(N log N) comparisons, where N is the combined input size.
set_to_list(set_difference(set_from_list([1, 2, 3]), set_from_list([2, 3])))
[1]