# [plt-scheme] Is there a set data-type?

On 2/5/10 9:52 AM, Paulo J. Matos wrote:
>* Matthias Felleisen wrote:
*>>*
*>>* On Feb 5, 2010, at 8:29 AM, Todd O'Bryan wrote:
*>>*
*>>>* What do people use for a set data-type? If there isn't one built-in,
*>>>* we're going to use a hash-table with #t as all the values.
*>>*
*>>* Just a tease: how would you use hashtable to represent infinite sets?
*>>* _________________________________________________
*>>* For list-related administrative tasks:
*>>* http://list.cs.brown.edu/mailman/listinfo/plt-scheme
*>*
*>* This is an interesting issue.
*>*
*>* Recently I had to implement infinite integer sets with union,
*>* intersection, setminus, etc... so I devised a very simple implementation
*>* based on assoc lists, where each pair is an interval. The set {1, ...
*>* 10} is represented as: ((1 . 10)), and {1,2,3,4,8,9} is ((1 . 4) (8 .
*>* 9)). Obviously I don't allow intervals to interset in the set
*>* representation and two intervals which can be represented as one should
*>* be merged. So, we cannot have ((2 . 4) (3 . 6)) or ((2 . 4) (5 . 10)).
*>*
*>* The set {2,4,6,8} however is ((2 . 2) (4 . 4) (6 . 6) (8 . 8)).
*>* Obviously not so good in this case but in general seems to behave quite
*>* well. The representation is simple but I found that the code for
*>* setminus for example, gets quite messy. I wonder if someone else would
*>* think about a different approach.
*
Uh, how do you represent the set of all even numbers, for example?
This is an exercise we give our first semester undergraduates here at
Northeastern. I'll give you a hint: you don't need lists or hash
tables, go back to the mathematical foundations and think characteristic
functions.
Now you do union, intersection, setminus, etc.
David