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

From: Paulo J. Matos (pocmatos at gmail.com)
Date: Fri Feb 5 11:03:08 EST 2010

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.

> Robby

Posted on the users mailing list.