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

On 2/5/10 10:49 AM, Robby Findler wrote:
> On Fri, Feb 5, 2010 at 9:47 AM, David Van Horn<dvanhorn at ccs.neu.edu>  wrote:
>> This is an exercise we give our first semester undergraduates here at
>> Northeastern.  I'll give you a hint: you don't need lists or hash tables, go
>> back to the mathematical foundations and think characteristic functions.
>>
>> Now you do union, intersection, setminus, etc.
>
> Can you make it as efficient as hash-tables in the case that the set is finite?

I think so, but haven't thought much about it -- the characteristic 
function for a finite set can be implemented as a hash table lookup.

Intersection and union are always constant time, but testing for 
membership becomes proportional to the number of intersections (or 
unions) used to construct the set.  I think with a straight hash table 
approach all the work goes into construction since you have to join two 
hash tables.

David