set — Unordered set type

The Set type allows the representation of an unordered set of values, with efficient insertion and lookup. Being represented internally as a hash table, membership can be tested in amortised O(1) time. As with arrays, insertion is non-destructive and requires that a copy of the set is made.

type Set(a)

A set of values, with no duplicates or ordering. All values have the same type a.

Note

The eq function should not be used to test if two sets are equal, as it may return false negatives. This is because two sets may have the same values, but a different internal hash table arrangement. Instead, use set_eq.

set_init(capacity :: Num) :: Set(a)

Creates an empty set, with capacity as the initial capacity for the hash table. The capacity has no bearing on the semantics of the set, since it will be automatically expanded if it runs out of room.

set_empty(set :: Set(a)) :: Num

Tests if set is empty. 1 if it is empty, 0 otherwise.

set_length(set :: Set(a)) :: Num

The number of elements in set.

set_capacity(set :: Set(a)) :: Num

The capacity of set. This has no bearing on the semantics of set, since it will be automatically expanded if it runs out of room. This shows the current size of the internal hash table.

set_insert(set :: Set(a), value :: a) :: Set(a)

Inserts a value into set, non-destructively. Returns a new, updated set. If value is already in set, this simply returns set unmodified.

set_member(set :: Set(a), item :: a) :: Num

Returns 1 if any element of set compares equal (according to eq) to item; 0 otherwise. This performs an efficient hash table lookup.

array_to_set(array :: Array(a)) :: Set(a)

Convert array to a Set of the same elements. This discards duplicate elements.

set_to_array(set :: Set(a)) :: Array(a)

Convert set to an Array of the same elements.

Note

The order of the elements in the resulting array is undefined. It should not be relied upon.

set_eq(xs :: Set(a), ys :: Set(a)) :: Num

Determine whether xs and ys contain the same elements. This is preferred over eq, because it compares the set elements without regards to the order they were inserted. For example, array_to_set([8, 13]) may not equal array_to_set([13, 8]), but those sets will compare equal under this function.

Note that this uses eq to compare the set elements, so it will not correctly compare a set of sets.

set_union(xs :: Set(a), ys :: Set(a)) :: Set(a)

Finds the union of xs and ys. The resulting set contains all of the elements that appear in either set.

set_intersection(xs :: Set(a), ys :: Set(a)) :: Set(a)

Finds the intersection of xs and ys. The resulting set contains only the elements that appear in both sets.