Add powerSet to Data.Set
[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
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 , lookupMin
125 , lookupMax
126 , findMin
127 , findMax
128 , deleteMin
129 , deleteMax
130 , deleteFindMin
131 , deleteFindMax
132 , maxView
133 , minView
134
135 -- * Conversion
136
137 -- ** List
138 , elems
139 , toList
140 , fromList
141
142 -- ** Ordered list
143 , toAscList
144 , toDescList
145 , fromAscList
146 , fromDescList
147 , fromDistinctAscList
148 , fromDistinctDescList
149
150 -- * Debugging
151 , showTree
152 , showTreeWith
153 , valid
154
155 #if defined(TESTING)
156 -- Internals (for testing)
157 , bin
158 , balanced
159 , link
160 , merge
161 #endif
162 ) where
163
164 import Data.Set.Internal as S
165
166 -- $strictness
167 --
168 -- This module satisfies the following strictness property:
169 --
170 -- * Key arguments are evaluated to WHNF
171 --
172 -- Here are some examples that illustrate the property:
173 --
174 -- > delete undefined s == undefined