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

 From: Paulo Matos (pocmatos at gmail.com) Date: Fri Feb 5 14:16:33 EST 2010 Previous message: [plt-scheme] Is there a set data-type? Next message: [plt-scheme] Is there a set data-type? Messages sorted by: [date] [thread] [subject] [author]

```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?
>>> _________________________________________________
>>> 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. Previous message: [plt-scheme] Is there a set data-type? Next message: [plt-scheme] Is there a set data-type? Messages sorted by: [date] [thread] [subject] [author]