[plt-dev] scheme/set

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Tue Feb 23 15:20:08 EST 2010

At Tue, 23 Feb 2010 14:09:02 -0500, Carl Eastlund wrote:
> The one real issue I see is the name make-set.  I would much prefer
> make-hash-set (with *eq and *eqv versions), which indicates explicitly
> what kind of set it is, and leaves us open to future kinds of sets.

The flip side is that `make-set' doesn't commit to a particular
implementation --- just a particular equivalence predicate.

I think Java uses the `make-hash-set' strategy a lot, and I'm pretty
sure the following has happened to me on more than one occasion:

 * I've wanted a Foo.

 * I discover that Foo is an interface with specific implementations
   XFoo, YFoo, and ZFoo.

 * It turns out that any of X, Y, or Z would work for my simple
   purposes, but I have to learn about them and pick one.

 * I'd really rather just say `new Foo' and let someone else pick a
   good default implementation for me.

In contrast to Java, nothing prevents us from having `make-set' (the
equivalent of `new Foo') while later making `set?' an interface-like
predicate, should we eventually decide that the generality is

Along similar lines, we could embed "equal" in the name `make-set', but
`equal?' is such a good default for the equivalence relation that it's
nicer in practice to just call it `make-set'.

> Just like we don't call make-hash "make-dict", because there are many
> kinds of dicts,

Does anyone use dictionaries other than hash tables? So far,
`scheme/dict' doesn't seem to be worth even the day or two I spent on

The sequence generalization, in contrast, has definitely paid off. I
think it's because we so often need to combine different kinds of
sequences, such as iterating over a list and natural numbers in
parallel; otherwise, we'd just use `map', `vector-map', etc. I don't
see lots of applications that need to deal with two different
representations of sets at the same time, though.

> Similarly for set-eq? and set-eqv?; we should have hash-set-eq? and
> hash-set-eqv?, because these predicates don't mean anything for "sets"
> in general. 

It seems like the notion of equality used by a set is relevant to
operations on the set. What does it mean to union two sets that have
different notions of equivalent elements?

Again: I'm not going to stand in the way of anyone who wants to make
the `scheme/set' library more generalizable and extensible. But please
don't take away `make-set'.

Posted on the dev mailing list.