by John Cowan (text), Wolfgang Corcoran-Mathe (implementation)

This SRFI is currently in *draft* status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to `srfi-196@nospamsrfi.schemers.org`

. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

- Received: 2020-05-17
- 60-day deadline: 2020-07-16
- Draft #1 published: 2020-05-17
- Draft #2 published: 2020-07-16
- Draft #3 published: 2020-07-19

Ranges are immutable collections that can be enumerated but are represented algorithmically rather than by a per-element data structure. This SRFI defines a large subset of the sequence operations defined on lists, vectors, and other collections. If necessary, a range can be converted to a list or vector of its elements or a generator that will lazily produce each element in the range.

One of the most common things to do in programming is to execute
a block of code a fixed number of times, with access to the index
used for the iteration. Indeed, it is so common that there is generally
a standard syntax for providing it, generally involving the keyword
`for`

(or if not, as in Fortran and Lisp, the word
`do`

). It is also usual to be able to provide a lower bound,
generally defaulting to 0 or 1, as well as step size, allowing
iterations through a sequence of odd numbers, or multiples of 10,
or whatever.

Languages with higher order functions, however, provide a second
approach to such loops: construct a sequence of numbers and apply
a function to each element of the sequence. SRFI 1's `iota`

and the standard `for-each`

procedures make this easy:
`(for-each (lambda (i) ...) (iota 0 10))`

will execute the expressions represented as `...`

with `i`

bound to the numbers 0 through 9, as
the generated list includes the lower bound and excludes the upper bound.

This approach is less feasible as the number of numbers grows.
To iterate a million times involves constructing a list of a million
numbers to be iterated over and immediately discarded as garbage.
This is not something you want to do in the inner loop of your code.
The range objects of this SRFI represent such sequences using only
a small fixed amount of storage. Using
`(range-for-each (lambda (i) ...) (numeric-range 0 1000000))`

iterates a million times but with less space overhead than
`iota`

's list of ten elements.

In addition, there are other sequences besides integers from
which a range may be drawn. In particular, inexact numbers can
also specify ranges: `(numeric-range 0.0 1.0 0.1)`

specifies the sequence 0.0, 0.1, ... 0.9. For another
example, the basic Latin capital letters A-Z can be specified using
a range constructed by ```
(range char-comparator #\A 26
(lambda (c n) (integer->char (+ (char->integer c) n))))
```

.
And to specify the geometric sequence 1, 1/2, 1/4, …, 1/512,
`(range real-comparator 1/2 10 expt)`

will do the job.
These comparators can be found in SRFI 162.

Note: The size of a range object is independent of the number of elements it contains.

`(range`

*comparator lower-bound length indexer*`)`

Returns a range whose lower bound is *lower-bound*
and whose length (number of elements) is *length*.
The *indexer* procedure returns the *n*th element
(where 0 ≤ *n* < *length*)
of the range given *lower-bound* and *n*.
The comparator object *comparator* is used to determine
if a value is within the range or not.
This procedure must run in O(1) time.

There is a constraint on indexers:
It is an error if an indexer `indexer`

does not satisfy the following identity:

`(indexer lower-bound k)`

is equal to`(indexer (indexer lower-bound k) 0)`

for all values of `k`

between 0 (inclusive)
and the highest value which will ever be passed as the
second argument to `indexer`

(exclusive).
This constraint cannot be checked by the implementation, but if
violated will cause various other procedures to misbehave.

`(numeric-range`

*start end* [*step*]`)`

Returns a numeric range, a special case of a range specified by an
inclusive lower bound *start*, an exclusive upper bound *end*, and a
*step* value (default 1), all of which can be exact or inexact real
numbers. Its comparator is the natural comparator on real numbers,
and its indexer is
`(lambda (bound n) (+ bound (* n step)))`

.
It is an error if *end* - *start* is not a
multiple of *step*.
This procedure must run in O(1) time.

Note that an effect of this definition is that the elements of a range over inexact numbers are enumerated by multiplying the index by the step value rather than by adding the step value to itself repeatedly. This reduces the likelihood of roundoff errors.

`(range?`

*obj*`)`

Returns `#t`

if *obj* is a range and `#f`

otherwise.
This procedure must run in O(1) time.

`(range-contains?`

*range value*`)`

Returns true if *value* is an element of *range*.
This procedure must run in O(*n*) time.

`(range-includes?`

*range value*`)`

Returns true if *value* is greater than or equal to
`(range-start `

and less
than or equal to *range*)`(range-end `

, whether or not it is
an element of the range.
This procedure must run in O(1) time.*range*)

`(range-empty?`

*range*`)`

Returns true if *range* is empty.
This procedure must run in O(1) time.

`(range-element-comparator`

*range*`)`

Returns the comparator of *range*.
This procedure must run in O(1) time.

`(range-length`

*range*`)`

Returns the length (number of elements) of *range*.
This procedure must run in O(1) time.

`(range-indexer`

*range*`)`

Returns the indexer of *range*.
This procedure must run in O(1) time.

`(range-ref`

*range n*`)`

Returns the *n*th element of *range*. It is an error if
*n* is less than 0 or greater than or equal to the length of
*range*.
This procedure must run in O(*n*) time.

`(range-start`

*range*`)`

Equivalent to `(range-ref`

*range*
`0)`

.
This procedure must run in O(1) time.

`(range-end`

*range*`)`

Equivalent to `(range-ref`

*range* ```
(-
(range-length
```

*range*`) 1))`

.
This procedure must run in O(1) time.

`(range-split-at`

*range index*`)`

Returns two values which are ranges. The first value contains all elements
of *range* from the zeroth element to the *index*th element
exclusive. The second value contains all elements of *range* from the
*index*th element inclusive to the last element. Both ranges share
the same element comparator with *range*.
This procedure must run in O(1) time.

`(subrange`

*range start end*`)`

`(range-take`

*range count*`)`

`(range-take-right`

*range count*`)`

`(range-drop`

*range count*`)`

`(range-drop-right`

*range count*`)`

Returns a range which contains all except the first/last *count* elements
of *range* and shares the same element comparator.
These procedures must run in O(1) time.

`(range-count`

*pred range*`)`

Returns the number of elements of *range* which satisfy
*pred*.
This procedure must run in O(*n*) time.

`(range-any`

*pred range*`)`

Returns true if any of the elements of *range* satisfy *pred*.
Specifically it returns the last value returned by *pred*. Otherwise,
`#f`

is returned.
This procedure must run in O(*n*) time.

`(range-every`

*pred range*`)`

Returns true if all the elements of *range* satisfy *pred*,
specifically it returns the last value returned by *pred* or
`#t`

if *pred* was never invoked. Otherwise, `#f`

is returned.
This procedure must run in O(*n*) time.

`(range-map->list`

*proc range*`)`

Returns a list of the results of applying *proc* to each
element of *range* in order. However, the order in which
*proc* is actually applied to the elements is unspecified.
This procedure must run in O(*n*) time.

`(range-for-each`

*proc range*`)`

Applies *proc* to each element of *range* in order. Returns an
unspecified result.
This procedure must run in O(*n*) time.

`(range-filter->list`

*pred range*`)`

`(range-remove->list`

*pred range*`)`

Returns a list containing the elements of *range* that satisfy / do
not satisfy *pred*.
This procedure must run in O(*n*) time.

`(range-fold`

*proc nil range*`)`

`(range-fold-right`

*proc nil range*`)`

Invokes *proc* on each member of *range* in order / reverse order, passing the
result of the previous invocation as a second argument. For the first
invocation, *nil* is used as the second argument. Returns the result of
the last invocation, or *nil* if there was no invocation.
These procedures must run in O(*n*) time.

`(range-reverse`

*range*`)`

Returns a range which contains the same elements as *range*, but in
reverse order, and which shares the same element comparator.
This procedure must run in O(1) time.

`(range-index`

*pred range*`)`

`(range-index-right`

*pred range*`)`

Returns the index of the first/last element of *range* that satisfies
*pred*, or `#f`

if there is none.
These procedures must run in O(*n*) time.

`(range-take-while`

*pred range*`)`

`(range-take-while-right`

*pred range*`)`

Returns a range containing the leading/trailing elements of *range* that satisfy
*pred* up to the first/last one that does not,
using the same element comparator.
These procedures must run in O(*n*) time.

`(range-drop-while pred`

*range*`)`

`(range-drop-while-right`

*pred range*`)`

Returns a range that omits leading/trailing elements of *range* that satisfy
*pred* until the first/last one that does not,
using the same element comparator.
These procedures must run in O(*n*) time.

`(range->list`

*range*`)`

`(range->vector`

*range*`)`

Returns a list/vector containing the elements of *range* in order.
These procedures must run in O(*n*) time.

`(range->generator`

*range*`)`

Returns a SRFI 158 generator that generates the elements of *range*
in order.
This procedure must run in O(1) time,
and each call of the generator must run in O(1) time.

The sample implementation is in the repository of this SRFI.
An R7RS library file and a separate file containing the actual
implementation are provided, along with a test file that
works with SRFI 78, but is self-contained if SRFI 78 does not exist.
The implementation needs SRFI 128, and can take
advantage of SRFI 145 (`assume`

) if it is present.

Without Python's `range`

object, this SRFI would not exist.
Thanks also to the contributors on the SRFI 196 mailing list.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler