[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
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"
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."