making a Set

[Marcin 'Qrczak' Kowalczyk]

Wed, 21 Feb 2001 18:11:22, G Murali <gmu@hotmail.com> pisze:

> makeSet:: (a->Bool)->Set a

There are operations which can be performed on sets constructible in
that way, and there are operations which cannot.

For example you can check if an element belongs to a set, or compute
an intersection of two sets. But you can't check if a set is empty
or if two sets are equal.

> I understand that we need a new type Set like
> data Set a = Set (a->Bool)

In this case the definition of makeSet is very simple:
    makeSet = Set

> what puzzles me is how to apply the funtion to all elements belonging
> to type a.

You can't find all elements of a given arbitrary type. (One reason
is that some types have infinitely many elements, and it's not the
only reason.)

You could restrict yourself to enumerable types, making an appropriate
class, or reuse existing classes:
    allElements :: (Bounded a, Enum a) => [a]
    allElements = [minBound .. maxBound]
allElements can be used to obtain a list of all values for types which
are instances of classes Bounded and Enum. Note that even for some
types which are instances of these classes, it's not very practical,
e.g. for Int (the list would have 4 billion elements).

Alternatively you could make a different representation of sets which
store all elements of a finite set in some data structure. You can't
construct such sets from arbitrary functions of type 'a -> Bool'.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK