Re: handling duplicate elements

[Kevin Wortman <kwortman@xxxxxxxxx>]

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.

Yes, the plan is to start with SRFI 113, drop all procedures ending in !, and add predecessor, successor, min, max, and range queries since those are fast operations in binary search trees. Also, construction from a list in strict increasing order, since that can be O(n), versus construction from an arbitrary list which is O(n log n) with a lot of GC churn.

We've also discussed a universal update procedure, although now that I've implemented some of this, I'm having second thoughts about whether that really adds anything.

Looking at Haskell's Data.Set, the only other things I see are a partition procedure, which is easy to implement and potentially useful; and a Show instance declaration, which doesn't seem relevant.

`eqv?` is the identity predicate of Scheme...

Thanks, that explanation was helpful.

 

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

The definitions I'm familiar with are that "monotonic increasing" means non-decreasing, "monotonic decreasing" means non-increasing, and unqualified "monotonic" means either monotonic increasing or monotonic decreasing. In the context of set map operations, we need the procedure to be specifically monotonic increasing to be able to reuse tree structure.

The wiki page goes on to say...

"The term monotonic transformation can also possibly cause some confusion because it refers to a transformation by a strictly increasing function."

...and I think we are experiencing some of that confusion. We could use the term "monotonic transform" instead of just "monotonic." Haskell uses "monotonic" along with notation that clarifies that they mean "monotonic increasing."

http://www.haskell.org/ghc/docs/6.12.3/html/libraries/containers-0.3.0.0/Data-Set.html#v%3AmapMonotonic

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.

I guess that's sufficient for my association set application; I can change a mapping by removing any pre-existing association then adjoining a new one. It's not ideal, though, since that is two data structure operations instead of just one.

I agree that "first argument beats second" should be the default behavior, since it is less expensive.

Looking at the Haskell library reminded me that referential transparency bypasses this whole issue; there is no such thing as a distinction between eqv? and =? in Haskell. C++ uses "first argument beats second":
http://www.cplusplus.com/reference/set/set/insert/

Python has a set and frozenset, but the "beats" behavior seems to be unspecified:
https://docs.python.org/3/library/stdtypes.html#set

Kevin Wortman