On 2020-12-13 21:57 +0900, Alex Shinn wrote:
> Using such an approach you get whatever balancing
> characteristics the generic tree provides.  The Chibi
> implementation at least is very concise and has zero
> such dependencies.

Thanks for the explanation.  Again, I think it could only improve the
SRFI to provide the highly space-efficient Chibi implementation as
well.  The only critical change needed, I think, would be the
integration of the balancing routines.  That, and the addition of the
remaining SRFI 217 forms.

> I wasn't necessarily suggesting using the Chibi implementation,
> which is heavily tailored to its own use case, but wanted to point
> out the prior art and general idea.  Also, while unoptimized trie's
> are simple and give predictable runtime performance, they are an
> especially space inefficient data structure.

For the record, the current sample implementation doesn't rely on naïve
binary tries, but on the variant radix trie structure described by
Chris Okasaki and Andrew Gill in "Fast Mergeable Integer Maps", which
Haskell has been using for its Data.IntMap library since the mid-90s.

With regard to the charset tests, I'm confident that bitmap
compression will improve space usage greatly in the case of dense sets
such as these.  This is the prime TODO with the sample implementation.

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

"Industry has surrounded people with artifacts whose inner workings
only specialists are allowed to understand." --Ivan Illich