iset-search implementations Wolfgang Corcoran-Mathe 08 Dec 2020 20:00 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 08 Dec 2020 20:18 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 09 Dec 2020 18:07 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 10 Dec 2020 12:00 UTC
Re: iset-search implementations Arthur A. Gleckler 10 Dec 2020 16:40 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 10 Dec 2020 16:50 UTC
Re: iset-search implementations Arthur A. Gleckler 10 Dec 2020 16:51 UTC
Re: iset-search implementations John Cowan 11 Dec 2020 02:23 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 11 Dec 2020 02:47 UTC
Re: iset-search implementations John Cowan 11 Dec 2020 03:04 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 11 Dec 2020 18:41 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 12 Dec 2020 10:59 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 14 Dec 2020 17:44 UTC
Re: iset-search implementations John Cowan 16 Dec 2020 15:34 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 16 Dec 2020 15:42 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 31 Dec 2020 18:23 UTC
Re: iset-search implementations John Cowan 07 Jan 2021 21:42 UTC
Re: iset-search implementations Arthur A. Gleckler 08 Jan 2021 04:39 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 08 Jan 2021 13:31 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 08 Jan 2021 23:47 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 09 Jan 2021 13:28 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 10 Jan 2021 23:35 UTC
Re: iset-search implementations Arthur A. Gleckler 11 Jan 2021 00:04 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 11 Jan 2021 06:33 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 11 Jan 2021 00:27 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 12 Jan 2021 14:34 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 12 Jan 2021 18:55 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 18 Jan 2021 09:13 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 19 Jan 2021 18:54 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 20 Jan 2021 10:53 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 21 Jan 2021 20:31 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 11 Dec 2020 08:40 UTC

Re: iset-search implementations Wolfgang Corcoran-Mathe 08 Jan 2021 23:47 UTC

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