# 196: Range Objects

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

## Status

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.

• Draft #1 published: 2020-05-17
• Draft #2 published: 2020-07-16
• Draft #3 published: 2020-07-19

## Abstract

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.

None at present.

## Rationale

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.

## Specification

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

### Constructors

`(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 nth 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.

### Predicates

`(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 range)` and less than or equal to `(range-end range)`, whether or not it is an element of the range. This procedure must run in O(1) time.

`(range-empty?` range`)`

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

### Accessors

`(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 nth 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.

### Iteration

`(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 indexth element exclusive. The second value contains all elements of range from the indexth 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`)`

Returns a range which contains the elements of range from index start, inclusive, through index end, exclusive and shares the same element comparator. This procedure must run in O(1) time.

`(range-take` range count`)`
`(range-take-right` range count`)`

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

`(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.

### Searching

`(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.

### Conversion

`(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.

## Implementation

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.

## Acknowledgements

Without Python's `range` object, this SRFI would not exist. Thanks also to the contributors on the SRFI 196 mailing list.