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