Am Sa., 9. Jan. 2021 um 00:47 Uhr schrieb Wolfgang Corcoran-Mathe
<xxxxxx@sigwinch.xyz>:
>
> 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.

In what sense does the cost go up on other procedures so implemented?
If we restrict the new key to be equivalent to the old one, a decent
implementation should detect if the programmer breaches this contract.
So a test has to be made anyway.

> 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'?

The second pass is not needed for, say, `mapping-adjoin`. As long as
the branch to a second pass is not taken, this shouldn't make
`mapping-search` any slower.

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

Why does it have to create a new structure? Of course, it depends on
the particular implementation, but it can test whether the update
arguments won't do anything.

Alternatively, you can use call/cc with *-search to implement
*-contains?. I know that some Schemes have slow implementations of
call/cc, but this should really be fixed by these Schemes.

-- Marc

> 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