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