ghc/lib/misc/Set.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1995
   3 %
   4 \section[Set]{An implementation of sets}
   5
   6 This new (94/04) implementation of sets sits squarely upon our
   7 implementation of @FiniteMaps@.  The interface is (roughly?) as
   8 before.
   9
  10 (95/08: This module is no longer part of the GHC compiler proper; it
  11 is now just a GHC library module).
  12
  13 \begin{code}
  14 module Set (
  15         Set,          -- abstract
  16                       -- instance of: Eq
  17
  18         emptySet,     -- :: Set a
  19         mkSet,        -- :: Ord a => [a]  -> Set a
  20         setToList,    -- :: Set a -> [a]
  21         unitSet,      -- :: a -> Set a
  22         singletonSet, -- :: a -> Set a
  23
  24         union,          -- :: Ord a => Set a -> Set a -> Set a
  25         unionManySets,  -- :: Ord a => [Set a] -> Set a
  26         minusSet,       -- :: Ord a => Set a -> Set a -> Set a
  27         mapSet,         -- :: Ord a => (b -> a) -> Set b -> Set a
  28         intersect,      -- :: Ord a => Set a -> Set a -> Set a
  29
  30         elementOf,      -- :: Ord a => a -> Set a -> Bool
  31         isEmptySet,     -- :: Set a -> Bool
  32
  33         cardinality     -- :: Set a -> Int
  34     ) where
  35
  36 import FiniteMap
  37 import Maybe
  38 \end{code}
  39
  40 \begin{code}
  41 -- This can't be a type synonym if you want to use constructor classes.
  42 newtype Set a = MkSet (FiniteMap a ())
  43
  44 emptySet :: Set a
  45 emptySet = MkSet emptyFM
  46
  47 unitSet :: a -> Set a
  48 unitSet x = MkSet (unitFM x ())
  49 singletonSet = unitSet -- old;deprecated.
  50
  51 setToList :: Set a -> [a]
  52 setToList (MkSet set) = keysFM set
  53
  54 mkSet :: Ord a => [a]  -> Set a
  55 mkSet xs = MkSet (listToFM [ (x, ()) | x <- xs])
  56
  57 union :: Ord a => Set a -> Set a -> Set a
  58 union (MkSet set1) (MkSet set2) = MkSet (plusFM set1 set2)
  59
  60 unionManySets :: Ord a => [Set a] -> Set a
  61 unionManySets ss = foldr union emptySet ss
  62
  63 minusSet  :: Ord a => Set a -> Set a -> Set a
  64 minusSet (MkSet set1) (MkSet set2) = MkSet (minusFM set1 set2)
  65
  66 intersect :: Ord a => Set a -> Set a -> Set a
  67 intersect (MkSet set1) (MkSet set2) = MkSet (intersectFM set1 set2)
  68
  69 elementOf :: Ord a => a -> Set a -> Bool
  70 elementOf x (MkSet set) = isJust (lookupFM set x)
  71
  72 isEmptySet :: Set a -> Bool
  73 isEmptySet (MkSet set) = sizeFM set == 0
  74
  75 mapSet :: Ord a => (b -> a) -> Set b -> Set a
  76 mapSet f (MkSet set) = MkSet (listToFM [ (f key, ()) | key <- keysFM set ])
  77
  78 cardinality :: Set a -> Int
  79 cardinality (MkSet set) = sizeFM set
  80
  81 -- fair enough...
  82 instance (Eq a) => Eq (Set a) where
  83   (MkSet set_1) == (MkSet set_2) = set_1 == set_2
  84   (MkSet set_1) /= (MkSet set_2) = set_1 /= set_2
  85
  86 -- but not so clear what the right thing to do is:
  87 {- NO:
  88 instance (Ord a) => Ord (Set a) where
  89   (MkSet set_1) <= (MkSet set_2) = set_1 <= set_2
  90 -}
  91 \end{code}