On 2021-01-08 14:31 +0100, Marc Nieper-Wißkirchen wrote:
> I think I have to retract what I said before.
>
> The procedure `mapping-replace` from SRFI 146 should be directly
> implementable through `mapping-search` as well. For this to work, we
> need the full generality of `mapping-search`, which is currently in
> the spec (this is what I missed).

I can't see that allowing arbitrary keys in order to allow more
procedures to be implemented in terms of *-search makes sense,
because I think it might impose a cost on other procedures
so implemented.

I understand that this can be seen as just an implementation detail,
but can `mapping-search' be implemented with (d) semantics without
making a second pass?  If the answer is no, wouldn't that make
mapping-search an inefficient substrate for, say, `mapping-adjoin'?

Similar thoughts apply to the current SRFI 217 sample implementation.
I've used iset-search to implement a small set of procedures, but only
because the current (eqv?  keys only) version requires only one
traversal of the structure in all cases.  I probably wouldn't use it
at all if we returned to allowing arbitrary keys, since multiple
traversals might be unavoidable.

(There are further problems with *-search as a general interface.
I don't consider it suitable for implementing *-contains? procedures,
for example; since *-search must normally return a new structure,
such an implementation will likely create a great deal of garbage in
order to simply return a boolean.  (The linear-update variant of
search may be a more reasonable alternative--if it's actually a
distinct procedure.))

We're stuck with *-search, I suppose, but if it can't be made
efficient, there's not much reason to use it as the general interface
it's intended to be.  Hence I'd only favor allowing arbitrary keys if
the majority of affected SRFI implementations can handle this
without simply composing a bunch of other, simpler operations.

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"Types provide the means to put the meaning on machines,
to program computation as an act of explanation." --Conor McBride