> That resolves all issues but two, which I'll address in other postings:
> #15 comparators for sets, and #16 merger procedures.  Modulo those, I
> think that the API is now appropriate as an API for immutable (persistent)
> sets as well, omitting the ! operations of course.

Agreed. I had tabled the immutable structures proposal until SRFIs 114
and 113 were stabilized and implemented, and it looks like we are just
about at that point. I plan on submitting a SRFI with the immutable set
API as close to SRFI 113 as possible.

> Looking at ImmutableDataStructuresWortman, I see the following
> additional procedures:  iset/merger, iset-min, iset-max, iset-between,
> iset-range= and friends, iset-map/monotone, iset->ordered-list,
> and ordered-list->iset.  There is also Riastradh's universal update
> procedure, which should perhaps be added to this SRFI's sets as well;
> I'll make that #17.

Thanks, I was actually in the process of writing a post about these
operations.

iset/merger was a first attempt to deal with the same issue of duplicate
elements that needs to be resolved for SRFI 113.

minimum, maximum, and range queries: these operations are asymptotically
faster on BSTs than in lists or hash tables ( O(log n + |elements
returned|) vs O(n) ) so exposing them seems worthwhile.

The same goes for successor and predecessor queries, i.e.
(iset-successor set x)
could return the least element y in set such that x<y. In my experience
it doesn't come up very often, but when it does you really need it; for
example these operations are the bottleneck in Fortune's algorithm (
http://en.wikipedia.org/wiki/Fortune's_algorithm ).

ordered-list->iset, iset-map/monotone: can be done in O(n) time each
when the list is known to be orderered, or map procedure is known to be
monotone resp., vs O(n log n) without those preconditions.

Riastradh's update is a clean abstraction so seems worth including as well.

> Should we have ibags?  What about integer-isets using patricia trees,
> like Haskell's Data.IntSet?  Although persistent sets won't be in this
> SRFI, it makes sense to me to discuss them here.

Yes we probably should. ibags should be easy to implement on top of
imaps, which in turn are easy to implement on top of isets, especially
now that we have comparators.

Kevin Wortman