[r6rs-discuss] Re: [Formal] formal comment (ports, characters, strings, Unicode)

From: William D Clinger <will>
Date: Tue Mar 20 17:07:57 2007

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.

Shiro Kawai wrote:

> Sorry for my ignorance, but is there an important algorithm
> that requires string-set!, even if you have both (a) means
> to construct strings sequentially, like string ports, and
> (b) means to create a vector of characters then convert it
> to a string efficiently, like vector->string?

Probably. I apologize for my ignorance also.

What I do know is that, if the vector operations are O(1),
then any O(f(N)) and Omega(N) time and space algorithm that
uses string-set! can be replaced by an O(f(N)) and Omega(N)
algorithm that doesn't use string-set!. You just convert
your string to a vector at the beginning of the algorithm
and convert back at the end.

> If there are such algorithms, then again, which is important,
> O(1) string-set! or O(1) substring (assuming that string
> positions are given in a way to guarantee O(1) access),
> under existence of preemptive threads?

Important to whom? That's why this stuff is so controversial:
We don't even have an objective objective function.

> (It is highly likely that I don't have enough brain;

We share that problem.

> can we have both?)

Silly answer: Yes, provided you're willing to abandon O(1)
string-ref.

Serious answer: I don't know. Probably not.

Will
Received on Tue Mar 20 2007 - 17:07:48 UTC