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

 From: Paulo J. Matos (pocmatos at gmail.com) Date: Fri Feb 5 09:52:03 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]

```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)).
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

```

 Posted on the users mailing list. 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]