# [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