Thu Jun 21 17:28:22 EDT 2007

```Andrew Coppin wrote:
> I don't even understand that... :-S

Ok, I'll try to explain it:

I represent sets by their characteristic function, wich returns True for
members of the set, and False for other values.

type Set a = a -> Bool

For example, the set of numbers containing only 42 is represented by

and the set of even numbers by

evenSet = even

Given this representation, we can easily encode a very fundamental set
operation, namely taking the dual set. The dual set is the set
containing all values (of a given type) except those contained in the
original set.

The dual set of the set containing only 42 is the set containing every
number except 42. The dual set of the set of even numbers is the set of
odd numbers.

To implement the dual operation, we start with it's type signature. dual
should take a set and return a set:

dual :: Set a -> Set a

By substituting the definition of Set, we have

dual :: (a -> Bool) -> (a -> Bool)

The last pair of parentheses is redundant, so we arrive at

dual :: (a -> Bool) -> a -> Bool

So dual can be seen as having two arguments, the original set and the
value to test for membership in the dual set. The implementation is
easy: the value is in the dual set, if it isn't in the original set:

>>   dual a y = not (a y)

Remember that a y is True, if and only if a contains y. so (not (a y))
is False, if and only if a contains y, wich is exactly what we want for
the characteristic function of the dual set.

(I'm not actually sure if dual sets are called dual sets. I've chosen
the word because dual sets arise from dual characteristic functions, in
the "swap the meaning of True and False" sense of dual).

The other operations are implemented likewise. If you're interested, try
to the write their type signatures to understand what each parameter means.

Tillmann
```