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 Marc Nieper-Wißkirchen 09 Jan 2021 13:28 UTC

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