UniqSet: Implement unionManyUniqSets in terms of foldl' instead of foldr
[ghc.git] / compiler / utils / UniqSet.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The AQUA Project, Glasgow University, 1994-1998
4
5 \section[UniqSet]{Specialised sets, for things with @Uniques@}
6
7 Based on @UniqFMs@ (as you would expect).
8
9 Basically, the things need to be in class @Uniquable@.
10 -}
11
12 module UniqSet (
13 -- * Unique set type
14 UniqSet, -- type synonym for UniqFM a
15
16 -- ** Manipulating these sets
17 emptyUniqSet,
18 unitUniqSet,
19 mkUniqSet,
20 addOneToUniqSet, addOneToUniqSet_C, addListToUniqSet,
21 delOneFromUniqSet, delOneFromUniqSet_Directly, delListFromUniqSet,
22 unionUniqSets, unionManyUniqSets,
23 minusUniqSet,
24 intersectUniqSets,
25 uniqSetAny, uniqSetAll,
26 elementOfUniqSet,
27 elemUniqSet_Directly,
28 filterUniqSet,
29 sizeUniqSet,
30 isEmptyUniqSet,
31 lookupUniqSet,
32 partitionUniqSet
33 ) where
34
35 import UniqFM
36 import Unique
37 import Data.Foldable (foldl')
38
39 {-
40 ************************************************************************
41 * *
42 \subsection{The signature of the module}
43 * *
44 ************************************************************************
45 -}
46
47 emptyUniqSet :: UniqSet a
48 unitUniqSet :: Uniquable a => a -> UniqSet a
49 mkUniqSet :: Uniquable a => [a] -> UniqSet a
50
51 addOneToUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
52 addOneToUniqSet_C :: Uniquable a => (a -> a -> a) -> UniqSet a -> a -> UniqSet a
53 addListToUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
54
55 delOneFromUniqSet :: Uniquable a => UniqSet a -> a -> UniqSet a
56 delOneFromUniqSet_Directly :: UniqSet a -> Unique -> UniqSet a
57 delListFromUniqSet :: Uniquable a => UniqSet a -> [a] -> UniqSet a
58
59 unionUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
60 unionManyUniqSets :: [UniqSet a] -> UniqSet a
61 minusUniqSet :: UniqSet a -> UniqSet a -> UniqSet a
62 intersectUniqSets :: UniqSet a -> UniqSet a -> UniqSet a
63
64 elementOfUniqSet :: Uniquable a => a -> UniqSet a -> Bool
65 elemUniqSet_Directly :: Unique -> UniqSet a -> Bool
66 filterUniqSet :: (a -> Bool) -> UniqSet a -> UniqSet a
67 partitionUniqSet :: (a -> Bool) -> UniqSet a -> (UniqSet a, UniqSet a)
68
69 sizeUniqSet :: UniqSet a -> Int
70 isEmptyUniqSet :: UniqSet a -> Bool
71 lookupUniqSet :: Uniquable a => UniqSet b -> a -> Maybe b
72
73 {-
74 ************************************************************************
75 * *
76 \subsection{Implementation using ``UniqFM''}
77 * *
78 ************************************************************************
79 -}
80
81 -- Note [Unsound mapUniqSet]
82 -- ~~~~~~~~~~~~~~~~~~~~~~~~~
83 -- UniqSet has the following invariant:
84 -- The keys in the map are the uniques of the values
85 -- It means that to implement mapUniqSet you'd have to update
86 -- both the keys and the values. There used to be an implementation
87 -- that only updated the values and it's been removed, because it broke
88 -- the invariant.
89
90 type UniqSet a = UniqFM a
91
92 emptyUniqSet = emptyUFM
93 unitUniqSet x = unitUFM x x
94 mkUniqSet = foldl' addOneToUniqSet emptyUniqSet
95
96 addOneToUniqSet set x = addToUFM set x x
97 addOneToUniqSet_C f set x = addToUFM_C f set x x
98 addListToUniqSet = foldl' addOneToUniqSet
99
100 delOneFromUniqSet = delFromUFM
101 delOneFromUniqSet_Directly = delFromUFM_Directly
102 delListFromUniqSet = delListFromUFM
103
104 unionUniqSets = plusUFM
105 unionManyUniqSets = foldl' (flip unionUniqSets) emptyUniqSet
106 minusUniqSet = minusUFM
107 intersectUniqSets = intersectUFM
108
109 elementOfUniqSet = elemUFM
110 elemUniqSet_Directly = elemUFM_Directly
111 filterUniqSet = filterUFM
112 partitionUniqSet = partitionUFM
113
114 sizeUniqSet = sizeUFM
115 isEmptyUniqSet = isNullUFM
116 lookupUniqSet = lookupUFM
117
118 uniqSetAny :: (a -> Bool) -> UniqSet a -> Bool
119 uniqSetAny = anyUFM
120
121 uniqSetAll :: (a -> Bool) -> UniqSet a -> Bool
122 uniqSetAll = allUFM