Data.Set.Private

WARNING

This module is considered internal.

The Package Versioning Policy does not apply.

This contents of this module may change in any way whatsoever and without any warning between minor versions of this package.

Authors importing this module are expected to track development closely.

Description

An efficient implementation of sets.

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

 import Data.Set (Set)
 import qualified Data.Set as Set

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, http://www.swiss.ai.mit.edu/~adams/BB/.
• J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

Bounds for union, intersection, and difference are as given by

• Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Just Join for Parallel Ordered Sets", https://arxiv.org/abs/1602.02120v3.

Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Of course, left-biasing 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, the behavior of the set is completely undefined.

Since: 0.5.9

Set type

data Set a

A set of values a.

Constructors

Bin !Size !a !(Set a) !(Set a)

Tip

type Size = Int

insertBy' :: (a -> a -> Ordering) -> a -> Set a -> Maybe (Set a)

O(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.

empty :: Set a

O(1). The empty set.