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 Wolfgang Corcoran-Mathe 21 Jan 2021 20:31 UTC

Thanks for the clear explanation.  Thinking of these calls as occurring
as steps in a tail-loop made this design much easier for me to grasp.
Adapting the radix tree search procedure to tail-call form also turns
out to be straightforward, and I'll update the implementation soon.

On 2021-01-20 11:53 +0100, Marc Nieper-Wißkirchen wrote:
> Now on why the tail-call guarantee can be important for general use of
> *-search: You may want to loop over a range of elements you search for so
> in each `success` or `failure` continuation, you issue another call to
> *-search. To get an iterative loop, you need the tail-call guarantee. Now
> you may object that we don't have to do the iteration inside the `success`
> or `failure` continuation. This, however, won't be possible if we have to
> postpone the decision of calling `insert`, `update`, `ignore`, or `remove`
> of earlier iterations until the end of the loop.

While this reasoning makes sense to me, I think that this is likely to be
a space-inefficient use of *-search due to the accumulation of partial
structures, which I've mentioned before.  *-search can't know that we
intend to discard the structure.

Talking to Taylor Campbell on IRC about this, it seems that an early
version (which he claims "might well have served as the prototype for
the whole business") of the *-search concept appears in [1] as two
separate procedures: an "update" form, which is more or less identical
to the current *-search procedure pattern, and a similar "search" form
which does not construct a new tree.  This two-procedure pattern makes
a great deal of sense to me; since there are many cases in which we
want to traverse a structure without constructing a new one, *-search
is not a suitable Swiss Army knife on its own.

[1] https://mumble.net/~campbell/scheme/bb-tree.scm

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

"More shall come after us than have gone before; the world
is not yet middle-aged." --Herman Melville, _White-Jacket_