Finite Sets
The
Set e type represents a set of elements of type
e. Most operations require that
e be an instance of
the
Ord class. A
Set is strict in its elements.
For a walkthrough of the most commonly used functions see the
sets
introduction.
This module is intended to be imported qualified, to avoid name
clashes with Prelude functions, e.g.
import Data.Set (Set)
import qualified Data.Set as Set
Note that the implementation is generally
left-biased.
Functions that take two sets as arguments and combine them, such as
union and
intersection, prefer the entries in the first
argument to those in the second. Of course, this bias can only be
observed when equality is an equivalence relation instead of
structural equality.
Warning
The size of the set must not exceed
maxBound::Int. Violation
of this condition is not detected and if the size limit is exceeded,
its behaviour is undefined.
Implementation
The implementation of
Set is based on
size balanced
binary trees (or trees of
bounded balance) as described by:
- Stephen Adams, "Efficient sets—a balancing act", Journal of
Functional Programming 3(4):553-562, October 1993,
https://doi.org/10.1017/S0956796800000885,
https://groups.csail.mit.edu/mac/users/adams/BB/index.html.
- J. Nievergelt and E.M. Reingold, "Binary search trees of
bounded balance", SIAM journal of computing 2(1), March 1973.
https://doi.org/10.1137/0202005.
- Yoichi Hirai and Kazuhiko Yamamoto, "Balancing weight-balanced
trees", Journal of Functional Programming 21(3):287-307, 2011,
https://doi.org/10.1017/S0956796811000104
Bounds for
union,
intersection, and
difference
are as given by
Performance information
The time complexity is given for each operation in
big-O
notation, with <math> referring to the number of entries in
the set.
Operations like
member,
insert, and
delete take
<math> time.
Binary set operations like
union and
intersection take
<math> time, where <math> and <math> are the sizes
of the smaller and larger input sets respectively.