week4/mart/StdSet.icl

   1 implementation module StdSet
   2
   3 import StdEnv
   4 import StdClass
   5
   6 ::      Set a = Set [a]
   7
   8 toSet   :: [a]             -> Set a | Eq a
   9 toSet s = Set (removeDup s)
  10
  11 fromSet :: (Set a)         -> [a]
  12 fromSet (Set s) = s
  13
  14 isEmptySet      :: (Set a)         -> Bool
  15 isEmptySet s = isEmpty (fromSet s)
  16
  17 isDisjoint      :: (Set a) (Set a) -> Bool  | Eq a
  18 isDisjoint s1 s2 = nrOfElements (intersection s1 s2) == 0
  19
  20 isSubset        :: (Set a) (Set a) -> Bool  | Eq a
  21 isSubset s1 s2 = nrOfElements s1 == nrOfElements (intersection s1 s2)
  22
  23 isStrictSubset  :: (Set a) (Set a) -> Bool  | Eq a
  24 isStrictSubset s1 s2 = isSubset s1 s2 && nrOfElements s1 < nrOfElements s2
  25
  26 memberOfSet     :: a       (Set a) -> Bool  | Eq a
  27 memberOfSet a (Set []) = False
  28 memberOfSet a (Set [x:xs]) = a == x || memberOfSet a (Set xs)
  29
  30 union   :: (Set a) (Set a) -> Set a | Eq a
  31 union (Set s1) (Set s2) = toSet (s1 ++ s2)
  32
  33 intersection    :: (Set a) (Set a) -> Set a | Eq a
  34 intersection (Set s1) s2 = Set [e \\ e <- s1 | memberOfSet e s2]
  35
  36 nrOfElements    :: (Set a) -> Int
  37 nrOfElements s = length (fromSet s)
  38
  39 without :: (Set a) (Set a) -> Set a | Eq a
  40 without (Set s1) s2 = Set [e \\ e <- s1 | not (memberOfSet e s2)]
  41
  42 product :: (Set a) (Set b) -> Set (a,b)
  43 product (Set s1) (Set s2) = Set [(e1, e2) \\ e1 <- s1, e2 <- s2]
  44
  45 instance zero (Set a)
  46 where zero = Set []
  47
  48 instance == (Set a) | Eq a
  49 where (==) s1 s2 = isSubset s1 s2 && isSubset s2 s1
  50
  51 powerSet        :: (Set a)         -> Set (Set a)
  52 powerSet (Set a) = Set [(Set x) \\ x <- powerSet2 a]
  53 where
  54         powerSet2       :: [a] -> [[a]]
  55         powerSet2 [] = [[]]
  56         powerSet2 [e:xs] = (powerSet2 xs) ++ [[e:x] \\ x <- powerSet2 xs]