Title

Range Objects

Author

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, ranges can be converted to a list 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 of 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 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

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.

(numeric-range start end [step])

Returns a numeric range, a special case of a range specified by an inclusive lower bound (default 0), an exclusive upper bound, 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 upper-bound - lower-bound is not a multiple of step.

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.

(range-contains? range value)

Returns true if value is an element of range.

(range-includes? range value)

Returns true if value is greater than or equal to the range start and less than or equal to the range end, whether or not it is an element of the range.

(range-empty? range)

Returns true if range is empty.

Accessors

(range-element-comparator range)

Returns the comparator of range.

(range-length range)

Returns the length (number of elements) of range.

(range-indexer range)

Returns the indexer of range.

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

(range-start range)

Shorthand for (range-ref range 0).

(range-end range)

Shorthand for (range-ref range (- (range-length range) 1)).

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.

(range-take range count)

Returns a range which contains the first count elements of range.

(range-take-right range count)

Returns a range which contains the last count elements of range.

(range-drop range count)

Returns a range which contains all except the first count elements of range.

(range-drop-right range count)

Returns a range which contains all except the last count elements of range.

(range-count pred range)

Returns the number of elements of range which satisfy pred.

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

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

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

(range-for-each proc range)

Applies proc to each element of range in order. Returns an unspecified result.

(range-filter->list pred range)

(range-remove->list pred range)

Returns a list containing the elements of range that satisfy / do not satisfy pred.

(range-fold proc nil range)

Invokes proc on each member of range in 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.

(range-fold-right proc nil range)

Invokes proc on each member of range in 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.

(range-reverse range)

Returns a range which contains the same elements as range, but in reverse order.

Searching

(range-index pred range)

Returns the index of the first element of range that satisfies pred, or #f if there is none.

(range-index-right pred range)

Returns the index of the last element of range that satisfies pred, or #f if there is none.

(range-take-while pred range)

Returns a range containing the elements of range that satisfy pred up to the first one that does not.

(range-take-while-right pred range)

Returns a range containing the trailing elements of range that satisfy pred.

(range-drop-while pred range)

Returns a range that omits elements of range that satisfy pred until the first one that does not.

(range-drop-while-right pred range)

Returns a range the omits the last elements of range that satisfy pred until the last one that does not.

Conversion

(range->list range)

Returns a list containing the elements of range in order.

(range->generator range)

Returns a SRFI 158 generator that generates the elements of range in order.

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 1 and 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