Merge pull request #296 from treeowl/fromDescList
[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 --
32 -- * J. Nievergelt and E.M. Reingold,
33 -- \"/Binary search trees of bounded balance/\",
34 -- SIAM journal of computing 2(1), March 1973.
35 --
36 -- Note that the implementation is /left-biased/ -- the elements of a
37 -- first argument are always preferred to the second, for example in
38 -- 'union' or 'insert'. Of course, left-biasing can only be observed
39 -- when equality is an equivalence relation instead of structural
40 -- equality.
41 --
42 -- /Warning/: The size of the set must not exceed @maxBound::Int@. Violation of
43 -- this condition is not detected and if the size limit is exceeded, its
44 -- behaviour is undefined.
45 -----------------------------------------------------------------------------
46
47 module Data.Set (
48 -- * Strictness properties
49 -- $strictness
50
51 -- * Set type
52 #if !defined(TESTING)
53 Set -- instance Eq,Ord,Show,Read,Data,Typeable
54 #else
55 Set(..)
56 #endif
57
58 -- * Operators
59 , (\\)
60
61 -- * Query
62 , S.null
63 , size
64 , member
65 , notMember
66 , lookupLT
67 , lookupGT
68 , lookupLE
69 , lookupGE
70 , isSubsetOf
71 , isProperSubsetOf
72
73 -- * Construction
74 , empty
75 , singleton
76 , insert
77 , delete
78
79 -- * Combine
80 , union
81 , unions
82 , difference
83 , intersection
84
85 -- * Filter
86 , S.filter
87 , partition
88 , split
89 , splitMember
90 , splitRoot
91
92 -- * Indexed
93 , lookupIndex
94 , findIndex
95 , elemAt
96 , deleteAt
97
98 -- * Map
99 , S.map
100 , mapMonotonic
101
102 -- * Folds
103 , S.foldr
104 , S.foldl
105 -- ** Strict folds
106 , foldr'
107 , foldl'
108 -- ** Legacy folds
109 , fold
110
111 -- * Min\/Max
112 , findMin
113 , findMax
114 , deleteMin
115 , deleteMax
116 , deleteFindMin
117 , deleteFindMax
118 , maxView
119 , minView
120
121 -- * Conversion
122
123 -- ** List
124 , elems
125 , toList
126 , fromList
127
128 -- ** Ordered list
129 , toAscList
130 , toDescList
131 , fromAscList
132 , fromDescList
133 , fromDistinctAscList
134 , fromDistinctDescList
135
136 -- * Debugging
137 , showTree
138 , showTreeWith
139 , valid
140
141 #if defined(TESTING)
142 -- Internals (for testing)
143 , bin
144 , balanced
145 , link
146 , merge
147 #endif
148 ) where
149
150 import Data.Set.Base as S
151
152 -- $strictness
153 --
154 -- This module satisfies the following strictness property:
155 --
156 -- * Key arguments are evaluated to WHNF
157 --
158 -- Here are some examples that illustrate the property:
159 --
160 -- > delete undefined s == undefined