Factor Data.Set into Data.Set.Base and 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 -- |
7 -- Module : Data.Set
8 -- Copyright : (c) Daan Leijen 2002
9 -- License : BSD-style
10 -- Maintainer : libraries@haskell.org
11 -- Stability : provisional
12 -- Portability : portable
13 --
14 -- An efficient implementation of sets.
15 --
16 -- These modules are intended to be imported qualified, to avoid name
17 -- clashes with Prelude functions, e.g.
18 --
19 -- > import Data.Set (Set)
20 -- > import qualified Data.Set as Set
21 --
22 -- The implementation of 'Set' is based on /size balanced/ binary trees (or
23 -- trees of /bounded balance/) as described by:
24 --
25 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
26 -- Journal of Functional Programming 3(4):553-562, October 1993,
27 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
28 --
29 -- * J. Nievergelt and E.M. Reingold,
30 -- \"/Binary search trees of bounded balance/\",
31 -- SIAM journal of computing 2(1), March 1973.
32 --
33 -- Note that the implementation is /left-biased/ -- the elements of a
34 -- first argument are always preferred to the second, for example in
35 -- 'union' or 'insert'. Of course, left-biasing can only be observed
36 -- when equality is an equivalence relation instead of structural
37 -- equality.
38 -----------------------------------------------------------------------------
39
40 module Data.Set (
41 -- * Strictness properties
42 -- $strictness
43
44 -- * Set type
45 #if !defined(TESTING)
46 Set -- instance Eq,Ord,Show,Read,Data,Typeable
47 #else
48 Set(..)
49 #endif
50
51 -- * Operators
52 , (\\)
53
54 -- * Query
55 , S.null
56 , size
57 , member
58 , notMember
59 , lookupLT
60 , lookupGT
61 , lookupLE
62 , lookupGE
63 , isSubsetOf
64 , isProperSubsetOf
65
66 -- * Construction
67 , empty
68 , singleton
69 , insert
70 , delete
71
72 -- * Combine
73 , union
74 , unions
75 , difference
76 , intersection
77
78 -- * Filter
79 , S.filter
80 , partition
81 , split
82 , splitMember
83
84 -- * Map
85 , S.map
86 , mapMonotonic
87
88 -- * Folds
89 , S.foldr
90 , S.foldl
91 -- ** Strict folds
92 , foldr'
93 , foldl'
94 -- ** Legacy folds
95 , fold
96
97 -- * Min\/Max
98 , findMin
99 , findMax
100 , deleteMin
101 , deleteMax
102 , deleteFindMin
103 , deleteFindMax
104 , maxView
105 , minView
106
107 -- * Conversion
108
109 -- ** List
110 , elems
111 , toList
112 , fromList
113
114 -- ** Ordered list
115 , toAscList
116 , toDescList
117 , fromAscList
118 , fromDistinctAscList
119
120 -- * Debugging
121 , showTree
122 , showTreeWith
123 , valid
124
125 #if defined(TESTING)
126 -- Internals (for testing)
127 , bin
128 , balanced
129 , join
130 , merge
131 #endif
132 ) where
133
134 import Data.Set.Base as S
135
136 -- $strictness
137 --
138 -- This module satisfies the following strictness property:
139 --
140 -- * Key arguments are evaluated to WHNF
141 --
142 -- Here are some examples that illustrate the property:
143 --
144 -- > delete undefined s == undefined