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.
> 2)
Again, the problem is: What do we mean by the size of an object? (And
again: that question was already there before my proposal.) The
subrange shares data with the original range but when the original
range gets garbage-collected, the shared data remains with the
subrange. That's why I have included it into the size bound.
Fair enough.
> 3) `range=?` lacks a running time guarantee.
Indeed. It was on my TODO list but I missed it nevertheless. The
running time should be the same as for range-every (but see below).
Fixed.
> 4) In range-append, "O(n) + O(k) time" should I think just be "O(n) time", since k is bounded above by n. The running time with k ranges of 1 element is O(n), since n = k, and the running time with 1 range of n elements is also O(n).
The problem are ranges with zero elements. I can have zillions of
empty ranges.
Right.
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.
So the remaining construction site [is this an idiom one can use in
English as well?]
Not usual, but perfectly intelligible.
John Cowan
http://vrici.lojban.org/~cowan xxxxxx@ccil.orgNobody expects the RESTifarian Inquisition! Our chief weapon is
surprise ... surprise and tedium ... tedium and surprise ....
Our two weapons are tedium and surprise ... and ruthless disregard
for unpleasant facts.... Our three weapons are tedium, surprise, and
ruthless disregard ... and an almost fanatical devotion to Roy Fielding....