[Haskell-cafe] Collections

[Tillmann Rendel]

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

   answerSet = (== 42)

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