iset-search implementations Wolfgang Corcoran-Mathe (08 Dec 2020 20:01 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:52 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 02:24 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (11 Dec 2020 02:47 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 03:05 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:40 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (08 Jan 2021 13:32 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:05 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:28 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