Nuke include/Typeable.h, create include/containers.h instead.
[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
43 module Data.Set (
44 -- * Strictness properties
45 -- $strictness
46
47 -- * Set type
48 #if !defined(TESTING)
49 Set -- instance Eq,Ord,Show,Read,Data,Typeable
50 #else
51 Set(..)
52 #endif
53
54 -- * Operators
55 , (\\)
56
57 -- * Query
58 , S.null
59 , size
60 , member
61 , notMember
62 , lookupLT
63 , lookupGT
64 , lookupLE
65 , lookupGE
66 , isSubsetOf
67 , isProperSubsetOf
68
69 -- * Construction
70 , empty
71 , singleton
72 , insert
73 , delete
74
75 -- * Combine
76 , union
77 , unions
78 , difference
79 , intersection
80
81 -- * Filter
82 , S.filter
83 , partition
84 , split
85 , splitMember
86 , splitRoot
87
88 -- * Indexed
89 , lookupIndex
90 , findIndex
91 , elemAt
92 , deleteAt
93
94 -- * Map
95 , S.map
96 , mapMonotonic
97
98 -- * Folds
99 , S.foldr
100 , S.foldl
101 -- ** Strict folds
102 , foldr'
103 , foldl'
104 -- ** Legacy folds
105 , fold
106
107 -- * Min\/Max
108 , findMin
109 , findMax
110 , deleteMin
111 , deleteMax
112 , deleteFindMin
113 , deleteFindMax
114 , maxView
115 , minView
116
117 -- * Conversion
118
119 -- ** List
120 , elems
121 , toList
122 , fromList
123
124 -- ** Ordered list
125 , toAscList
126 , toDescList
127 , fromAscList
128 , fromDistinctAscList
129
130 -- * Debugging
131 , showTree
132 , showTreeWith
133 , valid
134
135 #if defined(TESTING)
136 -- Internals (for testing)
137 , bin
138 , balanced
139 , link
140 , merge
141 #endif
142 ) where
143
144 import Data.Set.Base as S
145
146 -- $strictness
147 --
148 -- This module satisfies the following strictness property:
149 --
150 -- * Key arguments are evaluated to WHNF
151 --
152 -- Here are some examples that illustrate the property:
153 --
154 -- > delete undefined s == undefined