fp2/week3/camil/StdDynSet.icl

   1 implementation module StdDynSet
   2
   3 import StdEnv
   4 import StdMaybe
   5 import StdDynamic
   6
   7 isEqual:: Dynamic t -> Bool | Set t
   8 isEqual (x :: t^) a = x == a
   9 isEqual _ _ = False
  10
  11 class Set a | TC, ==, toString a
  12
  13 :: Set = Set [(Dynamic, Dynamic -> Bool, String)]
  14
  15 instance zero     Set
  16 where zero = Set []
  17
  18 instance toString Set
  19 where toString (Set [(_,_,a):as]) = "{" +++ a +++ (foldl (+++) "" ["," +++ s \\ (_,_,s) <- as]) +++ "}"
  20
  21 instance == Set
  22 where == a b = nrOfElts a == nrOfElts b && isSubset a b
  23
  24 toSet :: a -> Set | Set a
  25 toSet e = Set [(dynamic e, \x = isEqual x e, toString e)]
  26
  27 nrOfElts :: Set -> Int
  28 nrOfElts (Set a) = length a
  29
  30 isEmptySet :: Set -> Bool
  31 isEmptySet a = (nrOfElts a) == 0
  32
  33 memberOfSet :: a Set -> Bool | Set a
  34 memberOfSet _ (Set []) = False
  35 memberOfSet x (Set [(y,_,_):ys]) = isEqual y x || memberOfSet x (Set ys)
  36
  37 dynMemberOfSet :: Dynamic Set -> Bool
  38 dynMemberOfSet _ (Set []) = False
  39 dynMemberOfSet x (Set [(_,eq,_):ys]) = eq x || dynMemberOfSet x (Set ys)
  40
  41 isSubset :: Set Set -> Bool
  42 isSubset a b = (nrOfElts a) == (nrOfElts (intersection a b))
  43
  44 isStrictSubset :: Set Set -> Bool
  45 isStrictSubset a b = isSubset a b && nrOfElts a < nrOfElts b
  46
  47 union :: Set Set -> Set
  48 union (Set a) (Set b) = Set (a ++ (fromSet (without (Set b) (Set a))))
  49 where
  50         fromSet :: Set -> [(Dynamic, Dynamic -> Bool, String)]
  51         fromSet (Set x) = x
  52
  53 intersection :: Set Set -> Set
  54 intersection as (Set []) = as
  55 intersection (Set as) (Set bs) = Set [(a,eq,ts) \\ (a,eq,ts) <- as | dynMemberOfSet a (Set bs)]
  56
  57 without :: Set Set -> Set
  58 without (Set as) (Set bs) = Set [(a,eq,ts) \\ (a,eq,ts) <- as | not (dynMemberOfSet a (Set bs))]
  59
  60 Start = toString (union (toSet 1) (toSet 2))