A set of partially ordered values k.

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

\(\mathcal{O}(1)\). The number of elements in this set.

\(\mathcal{O}(w\log n)\). Is the key a member of the map? See also notMember.

\(\mathcal{O}(w\log n)\). Is the key not a member of the map? See also member.

\(\mathcal{O}(w\log n)\). Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLT 3 (fromList [3, 5])
[]
>>> lookupLT 6 (fromList [3, 5])
[3]

\(\mathcal{O}(w\log n)\). Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGT 3 (fromList [6, 5])
[6]
>>> lookupGT 5 (fromList [3, 5])
[]

\(\mathcal{O}(w\log n)\). Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLE 2  (fromList [3, 5])
[]
>>> lookupLE 3  (fromList [3, 5])
[3]
>>> lookupLE 10 (fromList [3, 5])
[5]

\(\mathcal{O}(w\log n)\). Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGE 3 (fromList [3, 5])
[3]
>>> lookupGE 5 (fromList [3, 10])
[10]
>>> lookupGE 6 (fromList [3, 5])
[]

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper subset? (ie. a subset but not equal).

\(\mathcal{O}(1)\). The empty set.

\(\mathcal{O}(1)\). A set with a single element.

\(\mathcal{O}(w\log n)\). If the key is already present in the map, the associated value is replaced with the supplied value. insert is equivalent to insertWith const.

\(\mathcal{O}(w\log n)\). Delete an element from a set.

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). The union of two sets, preferring the first set when equal elements are encountered.

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). The union of a list of sets: (unions == foldl union empty).

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference of two sets.

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). The intersection of two sets. Elements of the result come from the first set, so for example

>>> data AB = A | B deriving Show
>>> instance Eq AB where _ == _ = True
>>> instance PartialOrd AB where _ `leq` _ = True
>>> singleton A `intersection` singleton B
fromList [A]
>>> singleton B `intersection` singleton A
fromList [B]

\(\mathcal{O}(n)\). Filter all elements that satisfy the predicate.

\(\mathcal{O}(n)\). Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate.

\(\mathcal{O}(wn\log n)\). map f s is the set obtained by applying f to each element of s.

It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y

\(\mathcal{O}(n)\). mapMonotonic f s == map f s, but works only when f is strictly increasing. The precondition is not checked. Semi-formally, for every chain ls in s we have:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapMonotonic f s == map f s

Right-associative fold of a structure.

In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Note that, since the head of the resulting expression is produced by an application of the operator to the first element of the list, foldr can produce a terminating expression from an infinite list.

For a general Foldable structure this should be semantically identical to,

foldr f z = foldr f z . toList

Left-associative fold of a structure.

In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Note that to produce the outermost application of the operator the entire input list must be traversed. This means that foldl' will diverge if given an infinite list.

Also note that if you want an efficient left-fold, you probably want to use foldl' instead of foldl. The reason for this is that latter does not force the "inner" results (e.g. z f x1 in the above example) before applying them to the operator (e.g. to (f x2)). This results in a thunk chain O(n) elements long, which then must be evaluated from the outside-in.

For a general Foldable structure this should be semantically identical to,

foldl f z = foldl f z . toList

\(\mathcal{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.

\(\mathcal{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.

\(\mathcal{O}(w\log n)\). The minimal keys of the set.

\(\mathcal{O}(w\log n)\). The maximal keys of the set.

\(\mathcal{O}(n)\). The elements of a set in unspecified order.

\(\mathcal{O}(n)\). The elements of a set in unspecified order.

\(\mathcal{O}(wn\log n)\). Build a set from a list of keys.