Kevin Wortman scripsit:

> Great! I've been rewriting my immutable data structures, but have been
> holding off on proposing a SRFI until this one is finalized. I'd like
> the interface to the immutable structures to be as close to identical
> to SRFI 113 as practicable.

Excellent.  Since SRFI 113 is now defined to provide linear update in
the sense of SRFI 1, it's sufficient to have the same interface with
the exception of the linear-update procedures, all of which end in !.
In addition, however, there should be order-specific procedures like
getting the next and previous elements in a set, and something to
convert a persistent set to a transient one.  IIRC your proposal has
these already.  You should check the Haskell libraries to see if anything
else is missing.

> I have to admit that I've always had a hard time grokking the intended
> distinction between eq? and eqv?.

`eqv?` is the identity predicate of Scheme; when you put an object into a
container and then take it out again, you'll get an object which is eqv?
to the original object.  By the same token, given two objects which are
not `eqv?`, mutating one will not affect the other.

`eq?` is an optimized identity predicate which can be portably used
instead of `eqv?` when you are sure that the arguments are not
numbers, characters, or procedures.  In practice, `eq?` handles
characters and procedures fine, as well as small exact integers --
but the definition of "small" varies from Scheme to Scheme; see
<http://trac.sacrideo.us/wg/wiki/FixnumInfo>.  It cannot be trusted
to give correct results on other numbers.

> Duplicates may arise in the constructor, e.g. [...].
> The list passed to list->set and list->set! may have duplicates, so they
> are implicated in this too. [...]
> And, set-map may create duplicates if the mapping procedure is not
> injective. I think this is the subtlest of these cases and the most likely
> to catch programmers by surprise.

Okay, I'll have to think about these, especially the last.

> This is one of the reasons I had an imap/monotone procedure in my draft
> immutable library; monotone procedures are a common special case of
> injective function. In hindsight, though, I think it should be
> imap/nondecreasing instead of imap/monotone.

What distinction are you making between monotone and non-decreasing?
<https://en.wikipedia.org/wiki/Monotonic_function> says they are synonyms.
Perhaps the latter name is clearer, though.

> > 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.
>
> So this suggestion is that set-adjoin and set-replace use "second argument
> beats first" and all other procedures use "first argument beats second."

No, only set-replace is special.  All others use "first argument beats
second", where an element already in the set is understood to be first.

> This behavior would accommodate my intended use case, of implementing an
> association-map on top of a set. So I could live with it.
>
> But I'm not 100% happy with it, because it conflates two orthogonal issues:
> the differences between set-union and set-adjoin are that, in set-adjoin
> the right argument(s) are elements instead of sets, _and_ that set-adjoin
> uses "second argument beats first" while set-union uses "first argument
> beats first."

No, only the first difference is correct in my proposal.  Unioning two sets
is exactly adjoining the members of the second to the first.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
If I read "upcoming" in [the newspaper] once more, I will be downcoming
and somebody will be outgoing.