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