# 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 and is the set of elements that are in but not in . 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);
```

s.danicic@gold.ac.uk
Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2011-03-15