Merge tag 'v0.5.2.1' of git://github.com/haskell/containers into ghc-head
[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 -- * Indexed
85 , lookupIndex
86 , findIndex
87 , elemAt
88 , deleteAt
89
90 -- * Map
91 , S.map
92 , mapMonotonic
93
94 -- * Folds
95 , S.foldr
96 , S.foldl
97 -- ** Strict folds
98 , foldr'
99 , foldl'
100 -- ** Legacy folds
101 , fold
102
103 -- * Min\/Max
104 , findMin
105 , findMax
106 , deleteMin
107 , deleteMax
108 , deleteFindMin
109 , deleteFindMax
110 , maxView
111 , minView
112
113 -- * Conversion
114
115 -- ** List
116 , elems
117 , toList
118 , fromList
119
120 -- ** Ordered list
121 , toAscList
122 , toDescList
123 , fromAscList
124 , fromDistinctAscList
125
126 -- * Debugging
127 , showTree
128 , showTreeWith
129 , valid
130
131 #if defined(TESTING)
132 -- Internals (for testing)
133 , bin
134 , balanced
135 , join
136 , merge
137 #endif
138 ) where
139
140 import Data.Set.Base as S
141
142 -- $strictness
143 --
144 -- This module satisfies the following strictness property:
145 --
146 -- * Key arguments are evaluated to WHNF
147 --
148 -- Here are some examples that illustrate the property:
149 --
150 -- > delete undefined s == undefined