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