ghc/compiler/utils/ListSetOps.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1995
   3 %
   4 \section[ListSetOps]{Set-like operations on lists}
   5
   6 \begin{code}
   7 module ListSetOps (
   8         unionLists,
   9         intersectLists,
  10         minusList
  11 #if ! defined(COMPILING_GHC)
  12         , disjointLists, intersectingLists
  13 #endif
  14    ) where
  15
  16 #if defined(COMPILING_GHC)
  17 import Ubiq{-uitous-}
  18
  19 import Util     ( isIn, isn'tIn )
  20 #endif
  21 \end{code}
  22
  23 \begin{code}
  24 unionLists :: (Eq a) => [a] -> [a] -> [a]
  25 unionLists []     []            = []
  26 unionLists []     b             = b
  27 unionLists a       []           = a
  28 unionLists (a:as) b
  29   | a `is_elem` b = unionLists as b
  30   | otherwise     = a : unionLists as b
  31   where
  32 #if defined(COMPILING_GHC)
  33     is_elem = isIn "unionLists"
  34 #else
  35     is_elem = elem
  36 #endif
  37
  38 intersectLists :: (Eq a) => [a] -> [a] -> [a]
  39 intersectLists []     []                = []
  40 intersectLists []     b                 = []
  41 intersectLists a      []                = []
  42 intersectLists (a:as) b
  43   | a `is_elem` b = a : intersectLists as b
  44   | otherwise     = intersectLists as b
  45   where
  46 #if defined(COMPILING_GHC)
  47     is_elem = isIn "intersectLists"
  48 #else
  49     is_elem = elem
  50 #endif
  51 \end{code}
  52
  53 Everything in the first list that is not in the second list:
  54 \begin{code}
  55 minusList :: (Eq a) => [a] -> [a] -> [a]
  56 minusList xs ys = [ x | x <- xs, x `not_elem` ys]
  57   where
  58 #if defined(COMPILING_GHC)
  59     not_elem = isn'tIn "minusList"
  60 #else
  61     not_elem = notElem
  62 #endif
  63 \end{code}
  64
  65 \begin{code}
  66 #if ! defined(COMPILING_GHC)
  67
  68 disjointLists, intersectingLists :: Eq a => [a] -> [a] -> Bool
  69
  70 disjointLists []     bs = True
  71 disjointLists (a:as) bs
  72   | a `elem` bs = False
  73   | otherwise   = disjointLists as bs
  74
  75 intersectingLists xs ys = not (disjointLists xs ys)
  76 #endif
  77 \end{code}