On 2021-06-16 20:16 +0200, Marc Nieper-Wißkirchen wrote:
> That said, is there any conceivable case where it makes sense to implement
> fxmappings where, say, lookup takes O(n)?

Not in my opinion, but I don't consider such a bound useful.  If we
were to provide low-ball bounds which only very inefficient
implementations violate, it wouldn't give users of SRFI 224 any idea
of what they can expect from more efficient implementations.

It's also not clear to me what those low-ball bounds are.  For the
sample implementation's radix trees, lookup is O(min(n, fx-width)) in
time for a tree of n elements; in practice, it's log n time except in
unusual cases.  Be that as it may, requiring O(log n) time, for
instance, would make this an unacceptable implementation.

Coming up with acceptable general bounds for fxmapping operations is
beyond my current knowledge, and I'd want to do a decent amount of
research before adding anything of this sort to the SRFI.

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

"Nothing can transcend its smallest elements." --CEO Nwabudike Morgan