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.

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.

Issues

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.

Copyright

Copyright © John Cowan, Wolfgang Corcoran-Mathe (2020).

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