Hi all,

I've found an implementation issue with iset-search(!), in particular
with the behavior of the `update' continuation.  As I've implemented
(non-destructive) iset-search, the results of the continuations
(insert, ignore, remove, and update) are used "in place" to construct
the new iset.  isets are sample-implemented as compact radix tries[1],
so this means that new elements are inserted recursively.  (This is
precisely analogous to inserting elements into a binary tree.) As an
example, (iset-search set x failure success) would traverses to where
x "should be" in the trie representing set; if x isn't present,
`failure' is called, and the value of that call (either the integer x
or an "empty" value) is used as the element to place at this point in
the trie--and this is indeed the *right* place for x.  So far, so
good.

However, whereas `insert' can only insert the element we searched for,
the `update' continuation is not so limited; it can insert *any*
integer into the set at the point at which the `success' continuation
is called.  This can be used to construct broken tries.  Just as if a
positive integer were inserted into the "negative half" of a binary
search tree, the new value will be ignored by the conventional lookup
algorithm.

It may be possible to handle this situation (hackily) by using an
escape procedure to discard the in-construction set and use
iset-adjoin to insert the new element.  At the moment, though, I think
the ability to insert an arbitrary element with iset-search is a
misfeature.

I hope Marc doesn't mind my including him in this thread.  I've used
his SRFI 146 mapping-search implementation as a guide, and I'd be
grateful for any insights that he might have.

[1] https://en.wikipedia.org/wiki/Radix_tree

Best regards,

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

"The art of doing mathematics consists in finding that special case
which contains all the germs of generality." --David Hilbert