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

On 02/05/10 17:00, hendrik at topoi.pooq.com wrote:
> On Fri, Feb 05, 2010 at 02:52:03PM +0000, 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)). 
> 
> I did that once with a slightly different notation.  The set is 
> represented by a list.  Each entry in the list turns inclusion on and 
> off.
> 
> This instead of {1,2,3,4,8,9} being ((1 . 4) (8 . 9)), it's (1, 5, 8, 
> 10).  Some infinite sets can he represented by open-ended 
> intervals.  {1,2,3,4,8,9, 10, 11, 12, 13, 14, ...} becomes  (1, 
> 5, 8)  There's no shutoff at ten, so the inclusion starting at 8 just 
> keeps going on forever.
> 

That's also a neat representation but seems to have the same drawback as
mine as David pointed out. You can't actually represent the set of all
even numbers.