Data.IntSet

Sets of 64-bit integers, reusing the patricia trie.

An IntSet is IntMap(Unit), the same big-endian radix trie carrying no payload, exactly as Data.Set is Data.Map at Unit. Sharing the type rather than declaring a second one keeps a single trie implementation, so the canonical-shape argument in Data.IntMap is made once and covers both: a set is determined by its elements, its iteration order is ascending regardless of insertion order, and structural equality is set equality. Set algebra is the map algebra at Unit, where the union’s left bias cannot be observed. Sharing the type also avoids a second instance head; instance resolution keys on the head type constructor, so a distinct IntSet newtype would need its own Eq and Show while an alias-free reuse inherits IntMap’s.

Elements are I64 for the reason keys are in Data.IntMap: branching is a bit test on a fixed-width word. Opt-in: not in Base.

Functions and Values

intset_empty

intset_empty : Data.IntMap.IntMap(Unit)

The empty set.

intset_is_empty(intset_empty)

true

intset_singleton

intset_singleton : (I64) -> Data.IntMap.IntMap(Unit)

The set containing x alone.

intset_to_list(intset_singleton(7i64))

[7]

intset_insert

intset_insert : (I64, Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit)

Add x (a no-op when already present).

intset_to_list(intset_insert(2i64, intset_insert(1i64, intset_empty)))

[1, 2]

intset_member

intset_member : (I64, Data.IntMap.IntMap(Unit)) -> Bool

True when x is a member.

intset_member(2i64, intset_from_list([1i64, 2i64, 3i64]))

true

intset_delete

intset_delete : (I64, Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit)

Remove x (a no-op when absent).

intset_to_list(intset_delete(2i64, intset_from_list([1i64, 2i64, 3i64])))

[1, 3]

intset_size

intset_size : (Data.IntMap.IntMap(Unit)) -> Int

The number of elements.

intset_size(intset_from_list([1i64, 2i64, 2i64, 3i64]))

3

intset_is_empty

intset_is_empty : (Data.IntMap.IntMap(Unit)) -> Bool

True when the set has no elements.

intset_is_empty(intset_empty)

true

intset_to_list

intset_to_list : (Data.IntMap.IntMap(Unit)) -> List(I64)

The elements in ascending order, negatives first.

intset_to_list(intset_from_list([3i64, 1i64, 2i64, 1i64]))

[1, 2, 3]

intset_from_list

intset_from_list : (List(I64)) -> Data.IntMap.IntMap(Unit)

Build a set from a list, dropping duplicates.

intset_to_list(intset_from_list([3i64, 1i64, 2i64, 1i64]))

[1, 2, 3]

intset_union

intset_union : (Data.IntMap.IntMap(Unit), Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit)

Every element in either set, merged by walking the two tries together.

intset_to_list(intset_union(intset_from_list([1i64, 2i64]), intset_from_list([2i64, 3i64])))

[1, 2, 3]

intset_intersection

intset_intersection : (Data.IntMap.IntMap(Unit), Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit)

The elements in both sets.

intset_to_list(
  intset_intersection(
    intset_from_list([1i64, 2i64, 3i64]),
    intset_from_list([2i64, 3i64, 4i64]),
  ),
)

[2, 3]

intset_difference

intset_difference : (Data.IntMap.IntMap(Unit), Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit)

The elements of s1 that are not in s2.

intset_to_list(
  intset_difference(intset_from_list([1i64, 2i64, 3i64]), intset_from_list([2i64, 3i64])),
)

[1]

intset_filter

intset_filter : forall e0. ((I64) -> Bool ! {e0}, Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit) ! {e0}

The elements satisfying keep.

intset_to_list(intset_filter(\(x) -> x > 1i64, intset_from_list([1i64, 2i64, 3i64])))

[2, 3]

intset_fold

intset_fold : forall e0 a. ((a, I64) -> a ! {e0}, a, Data.IntMap.IntMap(Unit)) -> a ! {e0}

Fold f(acc, x) over the elements in ascending order.

intset_fold(\(acc, x) -> acc + x, 0i64, intset_from_list([1i64, 2i64, 3i64]))

6

intset_map

intset_map : forall e0. ((I64) -> I64 ! {e0}, Data.IntMap.IntMap(Unit)) -> Data.IntMap.IntMap(Unit) ! {e0}

Apply f to every element, rebuilding the set (f need not be injective).

intset_to_list(intset_map(\(x) -> x * 2i64, intset_from_list([1i64, 2i64, 3i64])))

[2, 4, 6]