[Haskell-cafe] Collections
Tillmann Rendel
rendel at rbg.informatik.tu-darmstadt.de
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
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
More information about the Haskell-Cafe
mailing list