Forwarding mistakenly privately posted message...

---------- Forwarded message ---------
Von: Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de>
Date: Sa., 5. Sept. 2020 um 12:35 Uhr
Subject: Re: Remaining changes
To: John Cowan <xxxxxx@ccil.org>

Please take into consideration that, as Wolfgang observed, vectors
have no O(1) random access guarantee. There are meaningful
implementions of vectors conceivable that have, say, O(log n) random
access time.

Instead of writing O(1), it seems better if the SRFI compares access
time directly to vectors.

John Cowan <xxxxxx@ccil.org> schrieb am Sa., 5. Sep. 2020, 05:41:
>
>
>
> On Fri, Sep 4, 2020 at 1:12 PM Wolfgang Corcoran-Mathe <xxxxxx@sigwinch.xyz> wrote:
>
>>
>> As discussed in an earlier subthread, I think that any statements
>> about indexer time-complexity should be removed or moved to an
>> "implementation notes" section.  Indexers are no longer used in the
>> description of ranges, and are not mentioned in the SRFI document
>> outside of the `range' constructor, where the indexer procedure
>> is caller-supplied.
>
>
> I've removed the passage from the top of the Specification section to the
> discussion of `range`, and rewritten it as follows:
>
> This SRFI recommends that *indexer* run in O(1) time. If it does not, the asymptotic guarantees of this SRFI's other procedures do not hold.

What is it supposed to mean that the indexer procedure runs in O(1)?
As the indexer procedure is just a procedure of an argument that takes
only finitely many values, such a statement is meaningless.

It would only make sense for a uniform family of indexers indexed by
the natural numbers.

Maybe you, Wolfgang and I can find some time to chat about it and
discuss how turn rewrite the relevant paragraphs so that size and
running time asymptotics are actually enforced.

Marc

>
>
>
> John Cowan          http://vrici.lojban.org/~cowan        xxxxxx@ccil.org
> There are three kinds of people in the world:
> those who can count, and those who can't.
>