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 #ifdef COMPILING_GHC
   8 #include "HsVersions.h"
   9 #endif
  10
  11 module ListSetOps (
  12         unionLists,
  13         intersectLists,
  14         minusList
  15 #ifndef COMPILING_GHC
  16         , disjointLists, intersectingLists
  17 #endif
  18    ) where
  19
  20 #if defined(COMPILING_GHC)
  21 IMP_Ubiq(){-uitous-}
  22
  23 import Util     ( isIn, isn'tIn )
  24 #endif
  25 \end{code}
  26
  27 \begin{code}
  28 unionLists :: (Eq a) => [a] -> [a] -> [a]
  29 unionLists []     []            = []
  30 unionLists []     b             = b
  31 unionLists a       []           = a
  32 unionLists (a:as) b
  33   | a `is_elem` b = unionLists as b
  34   | otherwise     = a : unionLists as b
  35   where
  36 #if defined(COMPILING_GHC)
  37     is_elem = isIn "unionLists"
  38 #else
  39     is_elem = elem
  40 #endif
  41
  42 intersectLists :: (Eq a) => [a] -> [a] -> [a]
  43 intersectLists []     []                = []
  44 intersectLists []     b                 = []
  45 intersectLists a      []                = []
  46 intersectLists (a:as) b
  47   | a `is_elem` b = a : intersectLists as b
  48   | otherwise     = intersectLists as b
  49   where
  50 #if defined(COMPILING_GHC)
  51     is_elem = isIn "intersectLists"
  52 #else
  53     is_elem = elem
  54 #endif
  55 \end{code}
  56
  57 Everything in the first list that is not in the second list:
  58 \begin{code}
  59 minusList :: (Eq a) => [a] -> [a] -> [a]
  60 minusList xs ys = [ x | x <- xs, x `not_elem` ys]
  61   where
  62 #if defined(COMPILING_GHC)
  63     not_elem = isn'tIn "minusList"
  64 #else
  65     not_elem = notElem
  66 #endif
  67 \end{code}
  68
  69 \begin{code}
  70 #if ! defined(COMPILING_GHC)
  71
  72 disjointLists, intersectingLists :: Eq a => [a] -> [a] -> Bool
  73
  74 disjointLists []     bs = True
  75 disjointLists (a:as) bs
  76   | a `elem` bs = False
  77   | otherwise   = disjointLists as bs
  78
  79 intersectingLists xs ys = not (disjointLists xs ys)
  80 #endif
  81 \end{code}