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

iset-search implementations Wolfgang Corcoran-Mathe 08 Dec 2020 20:00 UTC

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