[project @ 2005-03-04 14:24:51 by simonmar]

[ghc-hetmet.git] / ghc / compiler / utils / ListSetOps.lhs

diff --git a/ghc/compiler/utils/ListSetOps.lhs b/ghc/compiler/utils/ListSetOps.lhs
index db43da5..b93a045 100644 (file)
--- a/ghc/compiler/utils/ListSetOps.lhs
+++ b/ghc/compiler/utils/ListSetOps.lhs
@@ -5,7 +5,7 @@
 
 \begin{code}
 module ListSetOps (
-       unionLists, minusList,
+       unionLists, minusList, insertList,
 
        -- Association lists
        Assoc, assoc, assocMaybe, assocUsing, assocDefault, assocDefaultUsing,
@@ -23,29 +23,31 @@ module ListSetOps (
 import Outputable
 import Unique  ( Unique )
 import UniqFM  ( eltsUFM, emptyUFM, addToUFM_C )
-import Util    ( isn'tIn, isIn, mapAccumR, sortLt )
+import Util    ( isn'tIn, isIn, mapAccumR, sortLe )
 import List    ( union )
 \end{code}
 
 
 %************************************************************************
 %*                                                                     *
-\subsection{Treating lists as sets}
+       Treating lists as sets
+       Assumes the lists contain no duplicates, but are unordered
 %*                                                                     *
 %************************************************************************
 
 \begin{code}
-unionLists :: (Eq a) => [a] -> [a] -> [a]
-unionLists = union
-\end{code}
+insertList :: Eq a => a -> [a] -> [a]
+-- Assumes the arg list contains no dups; guarantees the result has no dups
+insertList x xs | isIn "insert" x xs = xs
+           | otherwise          = x : xs
 
-Everything in the first list that is not in the second list:
+unionLists :: (Eq a) => [a] -> [a] -> [a]
+-- Assumes that the arguments contain no duplicates
+unionLists xs ys = [x | x <- xs, isn'tIn "unionLists" x ys] ++ ys
 
-\begin{code}
 minusList :: (Eq a) => [a] -> [a] -> [a]
-minusList xs ys = [ x | x <- xs, x `not_elem` ys]
-  where
-    not_elem = isn'tIn "minusList"
+-- Everything in the first list that is not in the second list:
+minusList xs ys = [ x | x <- xs, isn'tIn "minusList" x ys]
 \end{code}
 
 
@@ -154,10 +156,10 @@ equivClasses :: (a -> a -> Ordering)      -- Comparison
 equivClasses cmp stuff@[]     = []
 equivClasses cmp stuff@[item] = [stuff]
 equivClasses cmp items
-  = runs eq (sortLt lt items)
+  = runs eq (sortLe le items)
   where
     eq a b = case cmp a b of { EQ -> True; _ -> False }
-    lt a b = case cmp a b of { LT -> True; _ -> False }
+    le a b = case cmp a b of { LT -> True; EQ -> True; GT -> False }
 \end{code}
 
 The first cases in @equivClasses@ above are just to cut to the point