It would work.  My issue is largely depends on Gauche-specific characteristics, so I have to find a way to cope with.

The difference from set-search! and hash-table-update! is that those srfis don't expect those procedures being fundamental operators on which other procedures are built upon.

However, I agree that it's clean design to make mapping-search fundamental operator; many other operators can be built on top of it.  And if you go with pure Scheme, functional implementation, mapping-search can be pretty efficient.  And also it's desirable to have same or similar APIs to those procedures, so I support the way mapping-search is as it is, and efficiency concern is what implementations need to deal with.

Aside from the performance concern, there's a conceptual discussion on the design.  For mapping and mapping-unfold, shall we adopt "earlier-takes-precedence" rule?  It can be either way, but it's tempting to perceive that they apply mapping-set repeatedly in the order of the key/value pairs to populate the created mapping, which leads to later-takes-precedence rule.
One way to address that misconception is to add mapping-adjoin as you suggested, and explain mapping and mapping-unfold in terms of mapping-adjoin, instead of (implied) mapping-set.  It's all about programmer's mental model, so  if it is explained with the semantics of mapping-adjoin, earlier-takes-precedence rule becomes clear.




On Mon, Jul 3, 2017 at 2:51 AM, Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:
Shiro Kawai <xxxxxx@gmail.com> schrieb am Mo., 3. Juli 2017 um 13:41 Uhr:
I agree that, given an efficient mapping-search, the "earlier takes precedence" can be implemented easily and efficiently.

It can be tricky to provide mapping-search as the primitive search/alter operation, depending on how the underlying map is implemented---suppose, for example, what if one wants thread-safety for mapping API (of course, srfi-146 doesn't require mutation of maps, and we don't need to worry about thread safety if we go with purely functional data structures.  And it is technically an erroneous situation when some other thread observes mutation even when linear-update API is used.  But some other thread might be watching, e.g. debugging or intrumenting, and we don't want to expose internally inconsistent state at any moment.)

I'm implementing srfi-146 on top of Gauche's built-in tree-map, and mapping-search is the one that seems challenging to implement efficiently *and* safely.

For the ‘mapping’ constructor, you can use the algorithm using ‘mapping-set’ when you reverse the list of associations first. The same would work for ‘mapping-unfold’ if you first called the list variant ‘unfold’ and then reversed the resulting list.

Wouldn't this work?

As to ‘mapping-search’: In some sense, it is the fundamental ‘mapping’ accessor and constructor, so it is somewhat expected that it is implemented efficiently. I agree that a destructive implementation of ‘mapping-search’ will need some kind of locking in the presence of multiple accessing threads to prevent unexpected results; but this is a task an implementation is already facing when implementing ’set-search!’ from SRFI 113 or ‘hash-table-update!’ from SRFI 125.

Marc