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

 From: hendrik at topoi.pooq.com (hendrik at topoi.pooq.com) Date: Fri Feb 5 12:00:16 EST 2010 Previous message: [plt-scheme] Is there a set data-type? Next message: [plt-scheme] Is there a set data-type? Messages sorted by: [date] [thread] [subject] [author]

```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?
> >_________________________________________________
> > 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
>
> _________________________________________________