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

On Fri, Feb 05, 2010 at 10:05:29AM -0600, Robby Findler wrote:
>* 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).
*
For inumeration, you'd have a function that would return an element and
the rest of the set. Rather like car, cdr, and null? for lists.
>*
*>* Robby
*>* _________________________________________________
*>* For list-related administrative tasks:
*>* http://list.cs.brown.edu/mailman/listinfo/plt-scheme
*