f330a1eb61fb54dc1daa8f0bb07385ebb832ced9
[packages/containers.git] / Data / Set.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
3 {-# LANGUAGE Safe #-}
4 #endif
5
6 #include "containers.h"
7
8 -----------------------------------------------------------------------------
9 -- |
10 -- Module : Data.Set
11 -- Copyright : (c) Daan Leijen 2002
12 -- License : BSD-style
13 -- Maintainer : libraries@haskell.org
14 -- Portability : portable
15 --
16 -- An efficient implementation of sets.
17 --
18 -- These modules are intended to be imported qualified, to avoid name
19 -- clashes with Prelude functions, e.g.
20 --
21 -- > import Data.Set (Set)
22 -- > import qualified Data.Set as Set
23 --
24 -- The implementation of 'Set' is based on /size balanced/ binary trees (or
25 -- trees of /bounded balance/) as described by:
26 --
27 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
28 -- Journal of Functional Programming 3(4):553-562, October 1993,
29 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
30 -- * J. Nievergelt and E.M. Reingold,
31 -- \"/Binary search trees of bounded balance/\",
32 -- SIAM journal of computing 2(1), March 1973.
33 --
34 -- Bounds for 'union', 'intersection', and 'difference' are as given
35 -- by
36 --
37 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
38 -- \"/Just Join for Parallel Ordered Sets/\",
39 -- <https://arxiv.org/abs/1602.02120v3>.
40 --
41 -- Note that the implementation is /left-biased/ -- the elements of a
42 -- first argument are always preferred to the second, for example in
43 -- 'union' or 'insert'. Of course, left-biasing can only be observed
44 -- when equality is an equivalence relation instead of structural
45 -- equality.
46 --
47 -- /Warning/: The size of the set must not exceed @maxBound::Int@. Violation of
48 -- this condition is not detected and if the size limit is exceeded, its
49 -- behaviour is undefined.
50 -----------------------------------------------------------------------------
51
52 module Data.Set (
53 -- * Strictness properties
54 -- $strictness
55
56 -- * Set type
57 #if !defined(TESTING)
58 Set -- instance Eq,Ord,Show,Read,Data,Typeable
59 #else
60 Set(..)
61 #endif
62
63 -- * Operators
64 , (\\)
65
66 -- * Query
67 , S.null
68 , size
69 , member
70 , notMember
71 , lookupLT
72 , lookupGT
73 , lookupLE
74 , lookupGE
75 , isSubsetOf
76 , isProperSubsetOf
77
78 -- * Construction
79 , empty
80 , singleton
81 , insert
82 , delete
83 , powerSet
84
85 -- * Combine
86 , union
87 , unions
88 , difference
89 , intersection
90 , cartesianProduct
91 , disjointUnion
92
93 -- * Filter
94 , S.filter
95 , takeWhileAntitone
96 , dropWhileAntitone
97 , spanAntitone
98 , partition
99 , split
100 , splitMember
101 , splitRoot
102
103 -- * Indexed
104 , lookupIndex
105 , findIndex
106 , elemAt
107 , deleteAt
108 , S.take
109 , S.drop
110 , S.splitAt
111
112 -- * Map
113 , S.map
114 , mapMonotonic
115
116 -- * Folds
117 , S.foldr
118 , S.foldl
119 -- ** Strict folds
120 , foldr'
121 , foldl'
122 -- ** Legacy folds
123 , fold
124
125 -- * Min\/Max
126 , lookupMin
127 , lookupMax
128 , findMin
129 , findMax
130 , deleteMin
131 , deleteMax
132 , deleteFindMin
133 , deleteFindMax
134 , maxView
135 , minView
136
137 -- * Conversion
138
139 -- ** List
140 , elems
141 , toList
142 , fromList
143
144 -- ** Ordered list
145 , toAscList
146 , toDescList
147 , fromAscList
148 , fromDescList
149 , fromDistinctAscList
150 , fromDistinctDescList
151
152 -- * Debugging
153 , showTree
154 , showTreeWith
155 , valid
156
157 #if defined(TESTING)
158 -- Internals (for testing)
159 , bin
160 , balanced
161 , link
162 , merge
163 #endif
164 ) where
165
166 import Data.Set.Internal as S
167
168 -- $strictness
169 --
170 -- This module satisfies the following strictness property:
171 --
172 -- * Key arguments are evaluated to WHNF
173 --
174 -- Here are some examples that illustrate the property:
175 --
176 -- > delete undefined s == undefined