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