Am Do., 3. Sept. 2020 um 20:04 Uhr schrieb Wolfgang Corcoran-Mathe
<xxxxxx@sigwinch.xyz>:

[...]

> I agree that this is the Right Thing, but, as things stand, a major
> reimplementation effort might be needed to make it happen.  In any
> case, I suggest that anything (e.g. the complexity requirements)
> preventing such an approach be removed from the SRFI document.
>
> What we've been discussing is essentially a simple-minded version of
> the above, where ranges are "forced" as soon as they're passed to
> range-append, etc., and without any heuristics for determining whether
> this forcing is actually a win.
>
> Again, I'm not inclined to rewrite a large chunk of the sample
> implementation.  Can you briefly sketch what would have to change?
> Could the changes be concentrated in a small set of forms, e.g.
> range-append, -reverse, etc.?

As most Scheme implementations will probably just copy the sample
implementation, it is important to have, eventually, a performant one.

I would do the following changes:

- add a field "range-complexity" to the record type for ranges. This
field is generally initialized to be zero.

- range-append sums the complexity of all K ranges and adds K.

- range-reverse adds +1 to the complexity.

- the complexity doesn't change if the indexer doesn't change.

- for all range constructors where there is an increase in the
complexity, call (threshold? complexity length). When it is true, wrap
the whole range with (vector-range (range->vector
<range-to-realize>)). (As the complexity of vector-range is zero, this
will reset the complexity.)

- so one can add an internal procedure (maybe-realize <range>) that
does the check above.

- open/customizable: the threshold? procedure.

What this proposal doesn't yet include is lazily realizing the range.
I am not yet sure how to do it best because we don't want to trigger a
cascade of realizations.