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

From: Paulo Matos (pocmatos at gmail.com)
Date: Fri Feb 5 14:16:33 EST 2010

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.


Posted on the users mailing list.