« back to all changes in this revision
Viewing changes to src/UU/DData/MultiSet.hs
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Arjan Oosting
- Date: 2006-11-18 16:24:30 UTC
- Revision ID: james.westby@ubuntu.com-20061118162430-24ddyj27kj0uk17v
Tags: upstream-0.9.2
Import upstream version 0.9.2
- files added:
- src
- src/UU
- src/UU/DData
- src/UU/Parsing
- src/UU/Pretty
- src/UU/Scanner
- src/UU/Util
added
removed
src/UU/DData/MultiSet.hs
1
--------------------------------------------------------------------------------
2
{-| Module : MultiSet
3
Copyright : (c) Daan Leijen 2002
4
License : BSD-style
5
6
Maintainer : daan@cs.uu.nl
7
Stability : provisional
8
Portability : portable
9
10
An implementation of multi sets on top of the "Map" module. A multi set
11
differs from a /bag/ in the sense that it is represented as a map from elements
12
to occurrence counts instead of retaining all elements. This means that equality
13
on elements should be defined as a /structural/ equality instead of an
14
equivalence relation. If this is not the case, operations that observe the
15
elements, like 'filter' and 'fold', should be used with care.
16
-}
17
---------------------------------------------------------------------------------}
18
module UU.DData.MultiSet (
19
-- * MultiSet type
20
MultiSet -- instance Eq,Show
21
22
-- * Operators
23
, (\\)
24
25
-- *Query
26
, isEmpty
27
, size
28
, distinctSize
29
, member
30
, occur
31
32
, subset
33
, properSubset
34
35
-- * Construction
36
, empty
37
, single
38
, insert
39
, insertMany
40
, delete
41
, deleteAll
42
43
-- * Combine
44
, union
45
, difference
46
, intersection
47
, unions
48
49
-- * Filter
50
, filter
51
, partition
52
53
-- * Fold
54
, fold
55
, foldOccur
56
57
-- * Min\/Max
58
, findMin
59
, findMax
60
, deleteMin
61
, deleteMax
62
, deleteMinAll
63
, deleteMaxAll
64
65
-- * Conversion
66
, elems
67
68
-- ** List
69
, toList
70
, fromList
71
72
-- ** Ordered list
73
, toAscList
74
, fromAscList
75
, fromDistinctAscList
76
77
-- ** Occurrence lists
78
, toOccurList
79
, toAscOccurList
80
, fromOccurList
81
, fromAscOccurList
82
83
-- ** Map
84
, toMap
85
, fromMap
86
, fromOccurMap
87
88
-- * Debugging
89
, showTree
90
, showTreeWith
91
, valid
92
) where
93
94
import Prelude hiding (map,filter)
95
import qualified Prelude (map,filter)
96
97
import qualified UU.DData.Map as M
98
99
{--------------------------------------------------------------------
100
Operators
101
--------------------------------------------------------------------}
102
infixl 9 \\ --
103
104
-- | /O(n+m)/. See 'difference'.
105
(\\) :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
106
b1 \\ b2 = difference b1 b2
107
108
{--------------------------------------------------------------------
109
MultiSets are a simple wrapper around Maps, 'Map.Map'
110
--------------------------------------------------------------------}
111
-- | A multi set of values @a@.
112
newtype MultiSet a = MultiSet (M.Map a Int)
113
114
{--------------------------------------------------------------------
115
Query
116
--------------------------------------------------------------------}
117
-- | /O(1)/. Is the multi set empty?
118
isEmpty :: MultiSet a -> Bool
119
isEmpty (MultiSet m)
120
= M.isEmpty m
121
122
-- | /O(1)/. Returns the number of distinct elements in the multi set, ie. (@distinctSize mset == Set.size ('toSet' mset)@).
123
distinctSize :: MultiSet a -> Int
124
distinctSize (MultiSet m)
125
= M.size m
126
127
-- | /O(n)/. The number of elements in the multi set.
128
size :: MultiSet a -> Int
129
size b
130
= foldOccur (\x n m -> n+m) 0 b
131
132
-- | /O(log n)/. Is the element in the multi set?
133
member :: Ord a => a -> MultiSet a -> Bool
134
member x m
135
= (occur x m > 0)
136
137
-- | /O(log n)/. The number of occurrences of an element in the multi set.
138
occur :: Ord a => a -> MultiSet a -> Int
139
occur x (MultiSet m)
140
= case M.lookup x m of
141
Nothing -> 0
142
Just n -> n
143
144
-- | /O(n+m)/. Is this a subset of the multi set?
145
subset :: Ord a => MultiSet a -> MultiSet a -> Bool
146
subset (MultiSet m1) (MultiSet m2)
147
= M.subsetBy (<=) m1 m2
148
149
-- | /O(n+m)/. Is this a proper subset? (ie. a subset and not equal)
150
properSubset :: Ord a => MultiSet a -> MultiSet a -> Bool
151
properSubset b1 b2
152
| distinctSize b1 == distinctSize b2 = (subset b1 b2) && (b1 /= b2)
153
| distinctSize b1 < distinctSize b2 = (subset b1 b2)
154
| otherwise = False
155
156
{--------------------------------------------------------------------
157
Construction
158
--------------------------------------------------------------------}
159
-- | /O(1)/. Create an empty multi set.
160
empty :: MultiSet a
161
empty
162
= MultiSet (M.empty)
163
164
-- | /O(1)/. Create a singleton multi set.
165
single :: a -> MultiSet a
166
single x
167
= MultiSet (M.single x 0)
168
169
{--------------------------------------------------------------------
170
Insertion, Deletion
171
--------------------------------------------------------------------}
172
-- | /O(log n)/. Insert an element in the multi set.
173
insert :: Ord a => a -> MultiSet a -> MultiSet a
174
insert x (MultiSet m)
175
= MultiSet (M.insertWith (+) x 1 m)
176
177
-- | /O(min(n,W))/. The expression (@insertMany x count mset@)
178
-- inserts @count@ instances of @x@ in the multi set @mset@.
179
insertMany :: Ord a => a -> Int -> MultiSet a -> MultiSet a
180
insertMany x count (MultiSet m)
181
= MultiSet (M.insertWith (+) x count m)
182
183
-- | /O(log n)/. Delete a single element.
184
delete :: Ord a => a -> MultiSet a -> MultiSet a
185
delete x (MultiSet m)
186
= MultiSet (M.updateWithKey f x m)
187
where
188
f x n | n > 0 = Just (n-1)
189
| otherwise = Nothing
190
191
-- | /O(log n)/. Delete all occurrences of an element.
192
deleteAll :: Ord a => a -> MultiSet a -> MultiSet a
193
deleteAll x (MultiSet m)
194
= MultiSet (M.delete x m)
195
196
{--------------------------------------------------------------------
197
Combine
198
--------------------------------------------------------------------}
199
-- | /O(n+m)/. Union of two multisets. The union adds the elements together.
200
--
201
-- > MultiSet\> union (fromList [1,1,2]) (fromList [1,2,2,3])
202
-- > {1,1,1,2,2,2,3}
203
union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
204
union (MultiSet t1) (MultiSet t2)
205
= MultiSet (M.unionWith (+) t1 t2)
206
207
-- | /O(n+m)/. Intersection of two multisets.
208
--
209
-- > MultiSet\> intersection (fromList [1,1,2]) (fromList [1,2,2,3])
210
-- > {1,2}
211
intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
212
intersection (MultiSet t1) (MultiSet t2)
213
= MultiSet (M.intersectionWith min t1 t2)
214
215
-- | /O(n+m)/. Difference between two multisets.
216
--
217
-- > MultiSet\> difference (fromList [1,1,2]) (fromList [1,2,2,3])
218
-- > {1}
219
difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
220
difference (MultiSet t1) (MultiSet t2)
221
= MultiSet (M.differenceWithKey f t1 t2)
222
where
223
f x n m | n-m > 0 = Just (n-m)
224
| otherwise = Nothing
225
226
-- | The union of a list of multisets.
227
unions :: Ord a => [MultiSet a] -> MultiSet a
228
unions multisets
229
= MultiSet (M.unions [m | MultiSet m <- multisets])
230
231
{--------------------------------------------------------------------
232
Filter and partition
233
--------------------------------------------------------------------}
234
-- | /O(n)/. Filter all elements that satisfy some predicate.
235
filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet a
236
filter p (MultiSet m)
237
= MultiSet (M.filterWithKey (\x n -> p x) m)
238
239
-- | /O(n)/. Partition the multi set according to some predicate.
240
partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a,MultiSet a)
241
partition p (MultiSet m)
242
= (MultiSet l,MultiSet r)
243
where
244
(l,r) = M.partitionWithKey (\x n -> p x) m
245
246
{--------------------------------------------------------------------
247
Fold
248
--------------------------------------------------------------------}
249
-- | /O(n)/. Fold over each element in the multi set.
250
fold :: (a -> b -> b) -> b -> MultiSet a -> b
251
fold f z (MultiSet m)
252
= M.foldWithKey apply z m
253
where
254
apply x n z | n > 0 = apply x (n-1) (f x z)
255
| otherwise = z
256
257
-- | /O(n)/. Fold over all occurrences of an element at once.
258
foldOccur :: (a -> Int -> b -> b) -> b -> MultiSet a -> b
259
foldOccur f z (MultiSet m)
260
= M.foldWithKey f z m
261
262
{--------------------------------------------------------------------
263
Minimal, Maximal
264
--------------------------------------------------------------------}
265
-- | /O(log n)/. The minimal element of a multi set.
266
findMin :: MultiSet a -> a
267
findMin (MultiSet m)
268
= fst (M.findMin m)
269
270
-- | /O(log n)/. The maximal element of a multi set.
271
findMax :: MultiSet a -> a
272
findMax (MultiSet m)
273
= fst (M.findMax m)
274
275
-- | /O(log n)/. Delete the minimal element.
276
deleteMin :: MultiSet a -> MultiSet a
277
deleteMin (MultiSet m)
278
= MultiSet (M.updateMin f m)
279
where
280
f n | n > 0 = Just (n-1)
281
| otherwise = Nothing
282
283
-- | /O(log n)/. Delete the maximal element.
284
deleteMax :: MultiSet a -> MultiSet a
285
deleteMax (MultiSet m)
286
= MultiSet (M.updateMax f m)
287
where
288
f n | n > 0 = Just (n-1)
289
| otherwise = Nothing
290
291
-- | /O(log n)/. Delete all occurrences of the minimal element.
292
deleteMinAll :: MultiSet a -> MultiSet a
293
deleteMinAll (MultiSet m)
294
= MultiSet (M.deleteMin m)
295
296
-- | /O(log n)/. Delete all occurrences of the maximal element.
297
deleteMaxAll :: MultiSet a -> MultiSet a
298
deleteMaxAll (MultiSet m)
299
= MultiSet (M.deleteMax m)
300
301
302
{--------------------------------------------------------------------
303
List variations
304
--------------------------------------------------------------------}
305
-- | /O(n)/. The list of elements.
306
elems :: MultiSet a -> [a]
307
elems s
308
= toList s
309
310
{--------------------------------------------------------------------
311
Lists
312
--------------------------------------------------------------------}
313
-- | /O(n)/. Create a list with all elements.
314
toList :: MultiSet a -> [a]
315
toList s
316
= toAscList s
317
318
-- | /O(n)/. Create an ascending list of all elements.
319
toAscList :: MultiSet a -> [a]
320
toAscList (MultiSet m)
321
= [y | (x,n) <- M.toAscList m, y <- replicate n x]
322
323
324
-- | /O(n*log n)/. Create a multi set from a list of elements.
325
fromList :: Ord a => [a] -> MultiSet a
326
fromList xs
327
= MultiSet (M.fromListWith (+) [(x,1) | x <- xs])
328
329
-- | /O(n)/. Create a multi set from an ascending list in linear time.
330
fromAscList :: Eq a => [a] -> MultiSet a
331
fromAscList xs
332
= MultiSet (M.fromAscListWith (+) [(x,1) | x <- xs])
333
334
-- | /O(n)/. Create a multi set from an ascending list of distinct elements in linear time.
335
fromDistinctAscList :: [a] -> MultiSet a
336
fromDistinctAscList xs
337
= MultiSet (M.fromDistinctAscList [(x,1) | x <- xs])
338
339
-- | /O(n)/. Create a list of element\/occurrence pairs.
340
toOccurList :: MultiSet a -> [(a,Int)]
341
toOccurList b
342
= toAscOccurList b
343
344
-- | /O(n)/. Create an ascending list of element\/occurrence pairs.
345
toAscOccurList :: MultiSet a -> [(a,Int)]
346
toAscOccurList (MultiSet m)
347
= M.toAscList m
348
349
-- | /O(n*log n)/. Create a multi set from a list of element\/occurrence pairs.
350
fromOccurList :: Ord a => [(a,Int)] -> MultiSet a
351
fromOccurList xs
352
= MultiSet (M.fromListWith (+) (Prelude.filter (\(x,i) -> i > 0) xs))
353
354
-- | /O(n)/. Create a multi set from an ascending list of element\/occurrence pairs.
355
fromAscOccurList :: Ord a => [(a,Int)] -> MultiSet a
356
fromAscOccurList xs
357
= MultiSet (M.fromAscListWith (+) (Prelude.filter (\(x,i) -> i > 0) xs))
358
359
{--------------------------------------------------------------------
360
Maps
361
--------------------------------------------------------------------}
362
-- | /O(1)/. Convert to a 'Map.Map' from elements to number of occurrences.
363
toMap :: MultiSet a -> M.Map a Int
364
toMap (MultiSet m)
365
= m
366
367
-- | /O(n)/. Convert a 'Map.Map' from elements to occurrences into a multi set.
368
fromMap :: Ord a => M.Map a Int -> MultiSet a
369
fromMap m
370
= MultiSet (M.filter (>0) m)
371
372
-- | /O(1)/. Convert a 'Map.Map' from elements to occurrences into a multi set.
373
-- Assumes that the 'Map.Map' contains only elements that occur at least once.
374
fromOccurMap :: M.Map a Int -> MultiSet a
375
fromOccurMap m
376
= MultiSet m
377
378
{--------------------------------------------------------------------
379
Eq, Ord
380
--------------------------------------------------------------------}
381
instance Eq a => Eq (MultiSet a) where
382
(MultiSet m1) == (MultiSet m2) = (m1==m2)
383
384
{--------------------------------------------------------------------
385
Show
386
--------------------------------------------------------------------}
387
instance Show a => Show (MultiSet a) where
388
showsPrec d b = showSet (toAscList b)
389
390
showSet :: Show a => [a] -> ShowS
391
showSet []
392
= showString "{}"
393
showSet (x:xs)
394
= showChar '{' . shows x . showTail xs
395
where
396
showTail [] = showChar '}'
397
showTail (x:xs) = showChar ',' . shows x . showTail xs
398
399
400
{--------------------------------------------------------------------
401
Debugging
402
--------------------------------------------------------------------}
403
-- | /O(n)/. Show the tree structure that implements the 'MultiSet'. The tree
404
-- is shown as a compressed and /hanging/.
405
showTree :: (Show a) => MultiSet a -> String
406
showTree mset
407
= showTreeWith True False mset
408
409
-- | /O(n)/. The expression (@showTreeWith hang wide map@) shows
410
-- the tree that implements the multi set. The tree is shown /hanging/ when @hang@ is @True@
411
-- and otherwise as a /rotated/ tree. When @wide@ is @True@ an extra wide version
412
-- is shown.
413
showTreeWith :: Show a => Bool -> Bool -> MultiSet a -> String
414
showTreeWith hang wide (MultiSet m)
415
= M.showTreeWith (\x n -> show x ++ " (" ++ show n ++ ")") hang wide m
416
417
418
-- | /O(n)/. Is this a valid multi set?
419
valid :: Ord a => MultiSet a -> Bool
420
valid (MultiSet m)
421
= M.valid m && (M.isEmpty (M.filter (<=0) m))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1