Data.Set

Ordered sets, reusing the balanced-tree map.

Set algebra stays O(n log n) and preserves iteration order. The prelude opens this module.

Reserved (a later release): like Map, a set’s identity will carry the content hash of the canonical Ord instance it was built with, so a set that crosses an assembly boundary commits to the ordering it was ordered by, and two programs that canonicalize different Ord(k) cannot silently exchange one. The representation-affecting classes (Ord, Hash) live in one place on the compiler side (store::coherence::is_representation_affecting); this is the container-side half of that reservation.

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_member

set_member : forall a b. (b, Map(b, Unit, a)) -> Bool

True when x is a member of the set.

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_size

set_size : forall a b c. (Map(a, b, c)) -> Int

The number of elements.

set_to_list

set_to_list : forall a b c. (Map(a, b, c)) -> List(a)

The elements in ascending order.

set_from_list

set_from_list : forall a b. (List(b)) -> Map(b, Unit, a)

Build a set from a list, dropping duplicates.

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_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_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.