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