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

On Fri, Feb 05, 2010 at 07:16:33PM +0000, Paulo Matos wrote:
> 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.

I used it to represent the available storage location in a stack frame 
in a compiler.  Also the set of available registers (on a machine where 
all the registers were identical).  I picked this because the code was 
actually simpler than the obvious alternatives.

The available storage was, of course, open-ended.  The registers 
weren't.

-- hendrik