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 19 Jan 2021 18:54 UTC

On 2021-01-18 10:13 +0100, Marc Nieper-Wißkirchen wrote:
> Whether something is called in tail position can be detected through the
> SRFI 157 continuation marks. The idea is that if I use
> `with-immediate-continuation-mark` around a call of `*-search` that the
> `success` and `failure` continuations must see it when they are called.
>
> This is what is meant by tail-calling `success` or `failure` in SRFI 146.
> (It would have been clearer, and may call for a PFN, had I added "with
> respect to the original call to `mapping-search`.)

I'm reading through SRFI 157 now.  Is John interested in using this
stronger definition of tail position for iset-search ?

More generally, what is the reasoning behind requiring a tail-call of
success or failure here?  I may be missing something obvious, but I
can't see that it's important for performance or semantics to mandate
this, and it may well result in worse performance for some structures.
I don't, at the moment, have an algorithm for constructing a
Patricia trie tail-recursively in better than O(n) time.  (Compare the
recursive iset-search, which, in the worst case, runs in
O(min(n, fx-width)) time, but usually attains log n.)

(I absolutely see the point of requiring a tail-call (by the caller)
of the insert, ignore, etc.)

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

"[F]ree flow of information is the only safeguard against tyranny.
... Beware of he who would deny you access to information, for in his
heart he dreams himself your master." --Commissioner Pravin Lal