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 10 Jan 2021 23:35 UTC

Thanks for your thoughts.

On 2021-01-09 14:28 +0100, Marc Nieper-Wißkirchen wrote:
> 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.

You're absolutely right.  I thought I had an example of a procedure
which would incur an additional cost regardless of whether a check
was done, but I can't remember what it was supposed to be.

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

I may be wrong about this, but it seems that using *-search to,
well, search for an element will consume O(n) space when traversing
most recursive structures, with or without call/cc.  As perhaps the
simplest possible example, consider this version of *-search for
list-sets:

    (define (lset-search lis key failure success)
      (letrec
       ((search
         (match-lambda
           (()
            (failure (lambda (obj)  ; insert
                       (values `(,key) obj))
                     (lambda (obj)  ; ignore
                       (values '() obj))))
           ((x . xs)
            (if (eqv? x key)
                (success key
                         (lambda (new obj)  ; update
                           (values (cons new xs) obj))
                         (lambda (obj)      ; remove
                           (values xs obj)))
                (let-values (((xs* obj) (search xs)))  ; recur
                  (values (cons x xs*) obj)))))))

        (search lis)))

An lset-contains?  procedure implemented in terms of a call/cc-wrapped
lset-search will accumulate frames through recursive `search' calls.
Sure, this garbarge will probably be reclaimed quickly, but we can
avoid creating it entirely by using tail recursion.  It's precisely
the same situation we'd have if we used fold-right or direct recursion
instead, things that most functional programmers try to avoid when
implementing a simple `contains?' function.

I'd point to this as an example of why *-search is not, in general,
a prudent way to implement some other core procedures.

In any case, this is tangential to the main point.  I like John's
PFN text, since I think it allows a choice of approaches.

Best regards,

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"Earth is the cradle of the mind, but one cannot live in a
cradle forever." --Konstantin Tsiolkovsky