Dr Alan Watson quoting me:
> > Suppose each string s is represented by a vector of 2^21 elements,
> > where element i consists of a list of numbers, in IEEE double
> > precision, that represent the indexes within s at which the
> > character c appears, where c is the Unicode scalar value f(i),
> > where f is represented by a global association list that maps
> > scalar values to indexes (i.e. f-inverse).  SRFI-75 allows that
> > representation, yet penalizes it.  I also consider it to be a
> > poor representation.
>
> You consider this a poor representation because it does not
> allow constant-time random access or because it does not allow
> linear-time traversal? Or simply because of the space cost?

Yes.  And don't forget the implementation complexity, cost of
mutation, potential for race conditions in multithreaded systems,
and incompatibility with Java, C#, and C++ cultural expectations.

> Consider an implementation that internally represents strings
> as if they were doubly-linked lists and cached the position of
> the last index. This allows linear-time traversal but not
> constant-time random access. Would you consider this a poor
> implementation?

For some purposes, perhaps, but not for others.  IMO it is far
more reasonable than the representation I described above.

BTW, I once used a doubly-linked-list-of-lines representation to
represent the text of editor buffers in an Emacs-like editor I
wrote in Scheme.  Some of the editor's commands treated the text
as a single long linear array of characters; other commands
treated the text as an array of strings, with double indexing
(line+column) to obtain a character.  Aided by a couple of cached
index translations, this representation ran acceptably fast on an
8 MHz 68000 with 1 Mby of RAM, and ran very nicely on the faster
and larger Macintoshes that came later.  It was never released as
a product, but I used it at home for more than a decade.

That experience is one of the reasons I disregard some of the
criticisms I have read here concerning SRFI-75's alleged bias
against interesting representations.

I have expressed my opinion that implementations should provide
multiple representations for strings, transparently and adaptively,
using the API described in SRFI-75 and to be described in future
SRFIs.  Not every one of those representations has to do all things
well.  Indeed, the impossibility of doing all things well with a
single representation is the reason I favor a multiplicity.

Will