# [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