Am Mo., 7. Sept. 2020 um 02:03 Uhr schrieb John Cowan <xxxxxx@ccil.org>:

> On Sun, Sep 6, 2020 at 4:40 PM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:
>
>> The current proposal says:
>>
>> a) The size of a range constructed by numeric-range is O(1), which
>> means limited by some (implementation-defined) constant.
>> b) The size of a range constructed by range-map is O(n) where n is the
>> number of elements.
>
>
> Well, anything worth describing more than once is worth naming: I'm calling them "compact ranges" and "expanded ranges".  Here's a new paragraph from the Specification section:
>
> <p>In addition, ranges come in two sizes: <dfn>compact ranges</dfn>,
> which are a small fixed size, and <dfn>expanded ranges</dfn>, whose
> size is asymptotically proportional to their length (number of elements).
> It is impossible to precisely characterize the size of a Scheme
> object due to widespread sharing of data, but an informal notion
> will serve for present purposes.  Unless otherwise noted, the
> procedures of this SRFI return compact ranges; however, if
> one or more arguments is an expanded range, the returned value
> may be an expanded range as well.</p>
>
> All later references to range size have been removed.  String-range and range-append may return either kind of range; vector-range, range-map, range-filter-map, range-filter, range-remove all return expanded ranges.  Range itself returns a compact range, with a disclaimer that the indexer may close over arbitrarily large data structures.

Actually, I have got an idea of how to make sizes precise, namely in
terms of newly allocated objects. And this seems to be the notion we
are after.

This is a proposed wording:

<p>Unless otherwise noted, the procedures in this SRFI that return
ranges allocate at most O(1) new locations in the store. By abuse of
notion, such procedures are said to return <dfn>compact ranges</dfn>.
The procedures in this SRFI that do not guarantee to return compact
ranges allocate at most O(n) new locations where n is the length of
the resulting range. Again by abuse of notion, such procedures are
said to return <dfn>extended ranges</dfn>.</p>

(So the main point is that "compact" and "extended" is, logically, a
property of the constructor, but to simplify the terminology we attach
the attribute to the range itself. But to have a meaningful
specification, we should make it once precise.)

>> So, actually, procedures like range-every (that have to
>> inspect all ranges at least once) also need addition of O(k).
>
>
> But that's done in the proc argument, and running time there is not counted.  I've made the change, but it's easy to roll back if I'm correct.

All the zillion ranges passed to range-every can be empty so proc is
never called. But range-length will have to be called on them. That's
why it needs at least O(k) time.