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.
Functions and Values
set_empty
set_empty : forall a b. Map(a, Unit, b)
The empty set.
set_insert
set_insert : forall a b. (b, Map(b, Unit, a)) -> Map(b, Unit, a)
Add x to the set (a no-op if already present).
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
True when x is a member of the set.
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)
Remove x from the set (a no-op if absent).
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.
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.
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)
Build a set from a list, dropping duplicates.
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)
Every element in either set.
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)
The elements in both sets.
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)
The elements of s1 that are not in s2.
set_to_list(set_difference(set_from_list([1, 2, 3]), set_from_list([2, 3])))
[1]