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_