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

Re: handling duplicate elements

This page is part of the web mail archives of SRFI 113 from before July 7th, 2015. The new archives for SRFI 113 contain all messages, not just those from before July 7th, 2015.

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