[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