iset-search implementations

*Wolfgang Corcoran-Mathe*08 Dec 2020 20:00 UTCHi 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