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