Just a quick response, because I'm busy completing the sample
implementations...

Alan Manuel Gloria wrote:

> As your SRFI text points out, though, the constants involved in an O(1)
> operation may be large, and I wonder if other structures with O(log n) time
> for indexing operations may have a smaller constant than an
> equivalently-sized structure with O(1) time for indexing operations, and be
> better for a practical implementation.

Texts are special because there's only a finite range of possible
values for characters, with a strong bias toward common characters
(ASCII in some locales, BMP virtually everywhere).  We can also
use vectors and bytevectors "under the hood", and those data
structures probably provide O(1) access even if string-ref does
not.

Note also that many texts are quite short, which is why some
systems have been able to get by with UTF-8 or UTF-16.  The
binary logarithm of 32 is 5, putting O(lg n) representations
at a five-fold disadvantage, and they can't make up for that
in simplicity because the O(1) algorithms are already pretty
simple.

Will