fp1/week4/camil/StdSet.icl

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