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

 From: David Van Horn (dvanhorn at ccs.neu.edu) Date: Fri Feb 5 10:47:48 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 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?
>> _________________________________________________
>> 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

```

 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]