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

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Fri Feb 5 10:59:57 EST 2010

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

Just a thought, of course. :)


Posted on the users mailing list.