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

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.

Coding operations on sets is tricky, but the resulting code ins 
neat.  You have to keep track during the straightforward recursions 
which arguments are currently in insert mode or remove mode, and you 
have to be careful with deMorgan's laws.

I wonder if I can still find the code.

-- hendrik

> 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
> 
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme