Add general merge functions for maps
[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 , partition
94 , split
95 , splitMember
96 , splitRoot
97
98 -- * Indexed
99 , lookupIndex
100 , findIndex
101 , elemAt
102 , deleteAt
103
104 -- * Map
105 , S.map
106 , mapMonotonic
107
108 -- * Folds
109 , S.foldr
110 , S.foldl
111 -- ** Strict folds
112 , foldr'
113 , foldl'
114 -- ** Legacy folds
115 , fold
116
117 -- * Min\/Max
118 , findMin
119 , findMax
120 , deleteMin
121 , deleteMax
122 , deleteFindMin
123 , deleteFindMax
124 , maxView
125 , minView
126
127 -- * Conversion
128
129 -- ** List
130 , elems
131 , toList
132 , fromList
133
134 -- ** Ordered list
135 , toAscList
136 , toDescList
137 , fromAscList
138 , fromDescList
139 , fromDistinctAscList
140 , fromDistinctDescList
141
142 -- * Debugging
143 , showTree
144 , showTreeWith
145 , valid
146
147 #if defined(TESTING)
148 -- Internals (for testing)
149 , bin
150 , balanced
151 , link
152 , merge
153 #endif
154 ) where
155
156 import Data.Set.Base as S
157
158 -- $strictness
159 --
160 -- This module satisfies the following strictness property:
161 --
162 -- * Key arguments are evaluated to WHNF
163 --
164 -- Here are some examples that illustrate the property:
165 --
166 -- > delete undefined s == undefined