John Cowan <xxxxxx@ccil.org> schrieb am Di., 4. Juli 2017 um 21:02 Uhr:

On Tue, Jul 4, 2017 at 2:22 AM, Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:

1) A way to create sets using comparators that only provide an order predicate (because code using SRFI 113 in a portable fashion will have to provide both an order predicate and a hash function because the underlying implementation is opaque).

2) Explicit immutability of sets.

Correct, except that I would word (1) in terms of being able to take advantage  of having an order predicate so as to process the set in order, which SRFI 113 does not portably allow.
 
If we have explicitly immutable ordered sets, there is no reason not to include explicitly immutable mappings with ordered keys

The (srfi 142) library already offers such a guarantee of ordering, or the ordering-dependent functions won't work.

I was referring to the "immutability". Concerning mappings, we currently have (srfi 146) and (srfi 146 hash). For full orthogonality, we would have to add a library for *immutable* ordered mappings which could very be much a subset of (srfi 146), i.e. we just have to remove the procedures with an "!".
 
 
yielding a new SRFI (combining SRFI 146 and SRFI 153).

Sets and mappings were once in a single pre-SRFI, and Arthur said it was too big to review, with which I agreed in retrospect.  So I do not want to see them combined again.

Again, I should have been clearer in my wording. By the combination I meant an interface as the one in SRFI 146 (with !-procedures) but for sets, not mappings.

So we would end up with 6 libraries:

- ordered mappings
- immutable ordered mappings
- hash mappings
- ordered sets and bags
- immutable ordered sets and bags
- hash sets and bags

(On top of that, we have the hash-table library, which could be made a subset function-wise of the hash mappings as you have suggested on the mailing list of SRFI 146.) 

And, possibly (as discussed below):

- immutable hash mappings
- immutable hash sets and bags
 
 Furthermore, there are legitimate use cases for immutable mappings based on (persistent, functional) hash tables.

To answer my own question from the other thread, there seems to be no persistent mapping implementation that has O(1) retrieval, less than O(n) storage.

Whether we have O(1) retrieval or O(log n) retrieval, or O(n) storage or O(n log(n)) storage may not matter much in many cases.

On the other hand, not all sets of keys possess a natural order (or determining the relative order would take too much time), so for those use cases we are left with hash-based data structures. And in a functional programming language, we want to be able to write purely functional code.

As I have mentioned somewhere else, symbol tables in block-scoped languages are modelled best with functional hash tables. The symbols or identifiers themselves (think of wrapped identifiers in hygienic macro expansion!) possess no natural order that can be calculated in O(1) (with respect to the length of the identifiers representation if there is any) but can be suitable for hashing. The data structure has to be functional because I don't want to overwrite the symbol table of an outer block when I adjoin symbols of an inner block.


So we would create just another SRFI for explicitly immutable mappings with hashed keys.

Simple immutable hash tables with O(n) mutation time (that is, by copying) are already optionally provided by SRFI 125.  The sample implementation does provide them unless it is built directly on an implementation's own SRFI 69 (I think).

A mutation time of O(n) does not make a very usable functional data structure.
 
But what users will care about, I believe is: (1) Is cheap and safe mutation guaranteed? and (2) Is ordering guaranteed?  With this SRFI we now have:

Guaranteed for sets: SRFI 153
Guaranteed for mappings: (srfi 146)

Not guaranteed for sets: SRFI 113
Not guaranteed for mappings: (srfi 146 hash)

I don't get what you mean by "guaranteed" in this table? That the order is preserved? Or that mutation is not possible? But with respect to mutability/immutability, (srfi 146) and (srfi 146 hash) are completely analogous. 

So I would strongly like to suggest to remove mentioning "immutability" from SRFI 153 and let the interface of SRFI 153 be the same as that of (srfi 146) with "mapping" replaced by "set" (and "bag").
 
So my question is: Why don't you make SRFI 153 spec-wise a thin layer over SRFI 113

Primarily because of the post-finalization errata of SRFI 113, which needed to be incorporated into SRFI 113.

So if you want to supersede SRFI 113, we would also need a revision for sets with hash functions.
 
Marc