[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: handling duplicate elements

Kevin Wortman scripsit:

> I have a proposal for how to support programmer control over duplicate
> elements.

This is very timely, because I am currently working on a new release of
the SRFI, this time with a completely new implementation for sets and
bags.  The integer-set implementation will follow in a later release.

> By "duplicate elements," I mean two objects inserted into a set (I
> will use "set" to refer to any of the set-like containers in this
> SRFI) that are equivalent according to the set's comparator, but not
> the same object according to e.g. eq?, e.g.

Eqv? would be the relevant predicate, given that when you put something
into a standard Scheme data structure such as a pair or vector, what you
get out is guaranteed to be eqv? to what went in, per R5RS/R7RS 3.4.

> My proposal is to create a disjoint type called "selector" inspired by
> the comparator type.

I considered this approach, but I decided that it was overkill.  Other
than set-adjoin(!), the only procedures that need such selection are the
set operations set-union(!) and set-intersection(!), and since they are
commutative, a simple rule of "first argument beats second argument"
will suffice.

So I am suggesting that set-adjoin(!) never replaces existing elements,
and adding a new operation set-replace(!) with three arguments: the set,
the element, and a default.  If the set contains the element, it is
deleted and the element is adjoined (this is a no-op if they are eqv?);
if not, the default is inserted.

This also gets rid of set-intern!, which was rather ugly.

> With this definition, conveniently, in the common use case of not
> caring about comparators and selectors, client code can omit them,

I don't want to go there because of the possibility of creating a set
containing comparators.  That won't work with the sampe implementation
of default-comparator, but a better implementation would allow it, in
which case omitting the comparator is ambiguous.

> Currently you would either need visibility to s' comparator,

I've added that to my new draft.  There is no reason to conceal it.

John Cowan          http://www.ccil.org/~cowan        cowan@xxxxxxxx
Heckler: "Go on, Al, tell 'em all you know.  It won't take long."
Al Smith: "I'll tell 'em all we *both* know.  It won't take any longer."