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