The IntSet type represents a set of elements of type Int. An IntSet
is strict in its elements.
For a walkthrough of the most commonly used functions see their
sets introduction.
These modules are intended to be imported qualified, to avoid name
clashes with Prelude functions, e.g.
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
Implementation
The implementation is based on big-endian patricia trees. This data
structure performs especially well on binary operations like union
and intersection. Additionally, benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced set implementation (see Data.Set).
D.R. Morrison,
"PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric",
Journal of the ACM, 15(4), October 1968, pages 514-534,
https://doi.org/10.1145/321479.321481.
Additionally, this implementation places bitmaps in the leaves of the tree.
Their size is the natural size of a machine word (32 or 64 bits) and greatly
reduces the memory footprint and execution times for dense sets, e.g. sets
where it is likely that many values lie close to each other. The asymptotics
are not affected by this optimization.
Performance information
The time complexity is given for each operation in
big-O notation, with n
referring to the number of entries in the map and W referring to the
number of bits in an Int (32 or 64).
Operations like member, insert, and delete have a worst-case
complexity of O(\min(n,W)). This means that the operation can become
linear in the number of elements with a maximum of W -- the number of
bits in an Int (32 or 64). These peculiar asymptotics are determined by the
depth of the Patricia trees:
even for an extremely unbalanced tree, the depth cannot be larger than
the number of elements n,
each level of a Patricia tree determines at least one more bit
shared by all subelements, so there could not be more
than W levels.
If all n elements in the tree are between 0 and N (or, say, between
-N and N), the estimate can be refined to O(\min(n, \log N)). If
the set is sufficiently "dense", this becomes O(\min(n, \log n)) or
simply the familiar O(\log n), matching balanced binary trees.
The most performant scenario for IntSet are elements from a contiguous
subset, in which case the complexity is proportional to \log n, capped
by W. The worst scenario are exponentially growing elements (1,2,4,
ldots,2^n), for which complexity grows as fast as n but again is capped
by W.
Binary set operations like union and intersection take
O(\min(n, m \log \frac{2^W}{m})) time, where m and n
are the sizes of the smaller and larger input sets respectively.
O(n). Build a set from an ascending list of elements.
Warning: This function should be used only if the elements are in
non-decreasing order. This precondition is not checked. Use fromList if the
precondition may not hold.
O(n). Build a set from an ascending list of distinct elements.
Warning: This function should be used only if the elements are in
strictly increasing order. This precondition is not checked. Use fromList
if the precondition may not hold.
O(\min(n,W)). Take while a predicate on the elements holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Drop while a predicate on the elements holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Divide a set at the point where a predicate on the elements stops holding.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
O(\min(n,W)). The expression (split x set) is a pair (set1,set2)
where set1 comprises the elements of set less than x and set2
comprises the elements of set greater than x.
O(1). Decompose a set into pieces based on the structure of the underlying
tree. This function is useful for consuming a set in parallel.
No guarantee is made as to the sizes of the pieces; an internal, but
deterministic process determines this. However, it is guaranteed that the
pieces returned will be in ascending order (all elements in the first submap
less than all elements in the second, and so on).
Note that the current implementation does not return more than two subsets,
but you should not depend on this behaviour because it can change in the
future without notice. Also, the current version does not continue
splitting all the way to individual singleton sets -- it stops at some
point.
mapMonotonic f s == map f s, but works only when f is strictly increasing.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls]
==> mapMonotonic f s == map f s
where ls = toList s
Warning: This function should be used only if f is monotonically
strictly increasing. This precondition is not checked. Use map if the
precondition may not hold.
O(n). A strict version of foldr. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n). A strict version of foldl. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n \min(n,W)). The expression (showTreeWith hang wide map) shows
the tree that implements the set. If hang is
True, a hanging tree is shown otherwise a rotated tree is shown. If
wide is True, an extra wide version is shown.