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

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.

Paulo Matos