6 Programming with Sets

1. try:

   use set;
   
   k:set(num);
   k <= 1 & empty;
   
   m:set(num);
   m <= 2 & empty;
   
   k U m;
   
   z:set(num);
   z <= k U m;
   
   choose(z);
   
   let (a,b) == choose(z) 
   in a;
   
   let (a,b) == choose(z) 
   in b;
   
   card (z);
   

2. Evaluate the following expressions:

   1. 3 & empty;
      

   2. "dog" & "cat" & empty;
      

   3. ('a' & empty) U ('b' & empty);
      

   4. 'a' isin ('a' & empty);
      

   5. "cat" isin ("dog" & empty);
      

   6. "cat" isin ("cat" & "dog" & empty);
      

3. What does the function gg, below do?

   gg: set(alpha) -> num;
   gg(S) <=  if S = empty
             then 0
             else let (a,T) == choose(S)
                  in 1 + gg(T);
   

4. What does the function ff, below do?

   ff: set(alpha) X set(alpha) -> set(alpha);
   ff(S1,S2) <=  if S1 = empty
                 then empty
                 else let (a,S3) == choose(S1)
                      in if a isin S2
                         then a & ff(S3,S2)
                         else ff(S3,S2);
   

5. The set difference between $X$ and $Y$ is the set of elements that are in $X$ but not in $Y$. Define, similarly to ff above, the function

   setDifference: set(alpha) X set(alpha) -> set(alpha);
   

   in Hope.

   diff: set(alpha) X set(alpha) -> set(alpha);
   diff(S1,S2) <=  if S1 = empty
                 then empty
                 else let (a,S3) == choose(S1)
                      in if a isin S2
                         then diff(S3,S2)
                         else a & diff(S3,S2);