Hi,
I have a proposal for how to support programmer control over duplicate elements.
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.
(set some-comparator x y)
where (=? some-comparator x y) but (not (eq? x y)).
Only one of x and y will be contained in the resulting set. In many common use cases it doesn't matter which, but in some cases it does, and, as discussed previously, the programmer needs control over that behavior.
The specific use case I am thinking of is implementing a "map" data structure on top of a set, where each entry is a pair with a key in car and value in cdr, as with an alist. I would like to be able to update an association with
(set-adjoin association-set (cons same-key new-value))
but for that to work, I need a guarantee that the new pair will replace the old one in association-set.
My proposal is to create a disjoint type called "selector" inspired by the comparator type. A selector wraps one procedure, so that
(selector-select selector-object left right)
chooses and returns one of the duplicates left and right to go into a set. We also define a default-selector that does something straightforward like always return the left argument (or maybe the right).
Then, any of the set constructors accept up to two arguments called "behaviorals." A behavioral may be a comparator, selector, or set object. If no behaviorals are supplied, a new set uses default-comparator and default-selector. If a comparator or selector is passed, it overrides the default. If a set is passed, its comparator and selector override both defaults.
With this definition, conveniently, in the common use case of not caring about comparators and selectors, client code can omit them, e.g.
(set 1 2 3)
works with default-comparator and default-selector. Also conveniently, if one has a set s, they can create a new set with a compatible comparator with
(set s <elements ...>) .
Currently you would either need visibility to s' comparator, or to do
(set-adjoin (set-empty-copy s) <elements...>) .
In my map use case, I can do
(set (make-car-comparator key-comparator) right-selector (cons key value)) .
Finally, the "up to two behaviorals" behavior means that it is still possible to insert comparators or selectors into a set, if one wanted to do that for some abstruse reason.
Kevin Wortman