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.)
This extra tail-call condition that *-search has to fulfill doesn't change the algorithmic complexity: In principle, you can capture the current continuation where the non-tail recursive algorithm would call `success` or `failure`, keep this continuation in the closure of `update` and the other procedures and then use a previously captured continuation to jump to the top of the call stack where you then call `success` or `failure`. In an implementation of first-class continuations as found in Chicken, this should actually be quite fast. If your Scheme knows delimited continuations, such an approach could even be considered a very natural one.
If you don't want to use call/cc, you can maintain the call-stack data by hand instead.
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.
Now the crucial point is that the `ignore` procedure does not have to hold the reified stack segment (from above) in its closure. Thus, the space complexity may be better than preserving a snapshot implicitly in the call frames above `success` or `failure`.
This reasoning is not without a flaw, however. If `success` is called, there is no `ignore` but I have to call `update` with the original key-value pair. `Update` cannot know this in advance, so the whole tail of the computation has to be preserved as long as `update` is accessible although I would only want to use it to ignore this step.
Thus, `success` should really deliver a third callback.