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

On Fri, Feb 5, 2010 at 10:03 AM, Paulo J. Matos <pocmatos at gmail.com> wrote:
>* Robby Findler wrote:
*>>*
*>>* On Fri, Feb 5, 2010 at 9:54 AM, Paulo J. Matos <pocmatos at gmail.com> wrote:
*>>>*
*>>>* I guess the characteristic function approach involves using lambdas to
*>>>* represent a set... :-/ I am worried with efficiency but I will give it a
*>>>* try.
*>>*
*>>* FWIW, there are some sets that are far more efficiently represented
*>>* using functions than other data structures if you can write the
*>>* function directly (eg, (lambda (x) (< 0 x 100000)) is far better than
*>>* checking membership in a 100000 element list), but when you pile up a
*>>* series of unions and intersections and things like that you end up
*>>* getting something like linear work in the original construction of the
*>>* set. If you want to do better maybe the right thing is to considering
*>>* developing a little PL and interpreting it (with special purpose
*>>* optimizations in there for the things you expect to happen
*>>* frequently).
*>>*
*>>* Just a thought, of course. :)
*>>*
*>*
*>* Thanks for the thoughts on performance.
*>* Another thing I will have to think about is computing the cardinality of the
*>* set which might return +inf.0 of course. I am not even sure this
*>* representation allows the computation of cardinality in a finite amount of
*>* time.
*
You could use objects that have to implement various methods, member?,
cardinality, union, enumerate (to debug; for infinite sets it would
just stop after a while).
Robby