iset-search implementations Wolfgang Corcoran-Mathe (08 Dec 2020 20:01 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:52 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 02:24 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (11 Dec 2020 02:47 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 03:05 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:40 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (08 Jan 2021 13:32 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:05 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:28 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