[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