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