Data.IntSet

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

IntSet is an opaque, zero-cost newtype over IntMap(Unit). The wrapper keeps the set/map APIs distinct while reusing the single canonical trie implementation: a set is determined by its elements, iteration is ascending regardless of insertion order, and structural equality is set equality.

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.

Types

`IntSet`

newtype IntSet = IntSet(IntMap(Unit))

A set of fixed-width integers. Its trie and unit payload are private.

Functions and Values

`intset_empty`

intset_empty : Data.IntSet.IntSet

The empty set.

intset_is_empty(intset_empty)

true

`intset_singleton`

intset_singleton : (I64) -> Data.IntSet.IntSet

The set containing x alone.

intset_to_list(intset_singleton(7i64))

[7]

`intset_insert`

intset_insert : (I64, Data.IntSet.IntSet) -> Data.IntSet.IntSet

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.IntSet.IntSet) -> Bool

True when x is a member.

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

true

`intset_delete`

intset_delete : (I64, Data.IntSet.IntSet) -> Data.IntSet.IntSet

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.IntSet.IntSet) -> Int

The number of elements.

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

`intset_is_empty`

intset_is_empty : (Data.IntSet.IntSet) -> Bool

True when the set has no elements.

intset_is_empty(intset_empty)

true

`intset_to_list`

intset_to_list : (Data.IntSet.IntSet) -> 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.IntSet.IntSet

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.IntSet.IntSet, Data.IntSet.IntSet) -> Data.IntSet.IntSet

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.IntSet.IntSet, Data.IntSet.IntSet) -> Data.IntSet.IntSet

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.IntSet.IntSet, Data.IntSet.IntSet) -> Data.IntSet.IntSet

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.IntSet.IntSet) -> Data.IntSet.IntSet ! {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.IntSet.IntSet) -> 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]))

`intset_map`

intset_map : forall e0. ((I64) -> I64 ! {e0}, Data.IntSet.IntSet) -> Data.IntSet.IntSet ! {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]

Keyboard shortcuts

Prism