## SRFI-196: Range Objects

Ranges are collections somewhat similar to vectors, except that they are immutable and have algorithmic representations instead of the uniform per-element data structure of vectors. The storage required is usually less than the size of the same collection stored in a vector and the time needed to reference a particular element is typically less for a range than for the same collection stored in a list. This SRFI defines a large subset of the sequence operations defined on lists, vectors, strings, and other collections. If necessary, a range can be converted to a list, vector, or string of its elements or a generator that will lazily produce each element in the range.

## SRFI Description

This page includes excerpts from the SRFI document, but is primarily intended to document the forms exported by the egg. For a full description of the SRFI, see the SRFI document.

## Specification

Ranges belong to a disjoint type.

Ranges provide certain running time guarantees. With each range, we associate two lengths of time, the average accessing time and the total accessing time. The total accessing time is the average accessing time multiplied by the length of the range. In the runtime guarantees below, the time spent in arguments designated by *pred*, equal, or *proc* is ignored.

Unless otherwise noted, procedures in this SRFI that return ranges allocate at most O(1) new locations (see R[57]RS section 3.4 for further information). Such ranges are known as compact ranges. Procedures marked as returning expanded ranges allocate at most O(*n*) locations, where *n* is the number of elements in the range.

The following names are used for arguments to procedures:

obj |
Any Scheme object. |

range |
A range object. |

pred |
A predicate that accepts zero or more arguments. |

equal |
A predicate that accepts two arguments and returns a boolean value. It is not necessarily an equivalence relation. |

length |
An exact positive integer. |

proc |
A procedure that accepts zero or more arguments and returns zero or more values. |

list |
A Scheme list. |

vector |
A Scheme vector. |

string |
A Scheme string. |

It is an error (unless otherwise noted) if the procedures are passed arguments that do not have the type implied by the argument names.

### Constructors

*[procedure]*

`(range length indexer)`

Returns a range whose length (number of elements) is *length*. The indexer procedure returns the *n*th element (where 0 ≤ *n* < *length*) of the range, given *n*. This procedure runs in O(1) time. The range returned is compact, although *indexer* may close over arbitrarily large data structures. The average accessing time of the resulting range is the average time needed to run *indexer*.

Examples:

(range->list (range 26 (lambda(n) (integer->char (+ 65 n))))) ⇒ (#\A #\B #\C #\D #\E … #\Z) (range->list (range 10 (lambda(n) (expt 1/2 n)))) ⇒ (1 1/2 1/4 … 1/512)

*[procedure]*

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

This constructor produces the sequence

start, (+ start step), (+ start (* 2 step)), …, (+ start (* n step)),

where *n* is the greatest integer such that `(+ start (* n step)) < end` if *step* is positive, or such that `(+ start (* n step)) > end` if *step* is negative. It is is an error if an *n* satisfying this condition cannot be determined, or if *step* is numerically zero. This procedure runs in O(1) time. The average accessing time of the resulting range is O(1).

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.

Examples:

(range->list (numeric-range 0 1 1/10)) ⇒ (0 1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10) (range->list (numeric-range 5 -5 -3)) ⇒ (5 2 -1 -4)

*[procedure]*

`(iota-range length [start [step]])`

Returns an iota-numeric range, a special case of a range specified by a *length* (a non-negative exact integer) as well as an inclusive lower bound *start* (default 0) and a *step* value (default 1), both of which can be exact or inexact real numbers. This constructor produces the sequence

start, (+ start step), (+ start (* 2 step)), …, (+ start (* (- length 1) step)),

This procedure runs in O(1) time. The average accessing time of the resulting range is O(1).

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.

*[procedure]*

`(vector-range vector)`

Returns a range whose elements are those of *vector*. This procedure runs in O(1) time. The average accessing time of the resulting range is O(1). It is an error to mutate *vector*.

Example:

(range->list (vector-range #(1 3 5 7 9))) ⇒ (1 3 5 7 9)

*[procedure]*

`(string-range string)`

Returns a range whose elements are those of *string*. It is an error to mutate *string*. This procedure runs in O(*n*) time, where *n* is the length of *string* (in the sense of `string-length`). The average accessing time of the resulting range is O(1).

In this implementation, `string-range` is equivalent to `(compose vector-range string->vector)`.

Example:

(range->list (string-range "abcde")) ⇒ (#\a #\b #\c #\d #\e)

*[procedure]*

`(range-append range …)`

Returns a range whose elements are the elements of the *ranges* in order. This procedure runs in O(*n*) + O(*k*) time, where *n* is the total number of elements in all the ranges and *k* is the number of *range*s. The result is usually expanded but may be compact. The average accessing time of the resulting range is asymptotically bounded by maximum of the average accessing times of the *ranges*.

Example:

(range->list (range-append (numeric-range 0 3) (numeric-range 3 6))) ⇒ (0 1 2 3 4 5)

### Predicates

*[procedure]*

`(range? obj)`

Returns `#t` if *obj* is a range and `#f` otherwise.

*[procedure]*

`(range=? equal range1 range2 …)`

Returns `#t` if all the *range*s are of the same length and if their corresponding values are the same in the sense of *equal*, and `#f` otherwise. The runtime of this procedure is O(*s*) + O(*k*), where *s* is the sum of the total accessing times of the ranges and *k* is the number of ranges.

Examples:

(range=? = (numeric-range 10 30) (numeric-range 10 30)) ⇒ #t (range=? = (numeric-range 5 10) (numeric-range 6 11)) ⇒ #f (range=? eqv? (numeric-range 0 0) (range 0 (lambda(i) i))) ⇒ #t

### Accessors

*[procedure]*

`(range-length range)`

Returns the length (number of elements) of *range*. Runs in O(1) time.

Example:

(range-length (numeric-range 10 30)) ⇒ 20

*[procedure]*

`(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*. The running time of this procedure is asymptotically equal to the average accessing time of *range*.

Examples:

(range-ref (numeric-range 10 30) 5) ⇒ 15 (range-ref (range 2 (lambda(i) (not (zero? i)))) 1) ⇒ #t

*[procedure]*

`(range-first range)`

Equivalent (in running time as well) to `(range-ref range 0)`.

Example:

(range-first (numeric-range 10 30)) ⇒ 10

*[procedure]*

`(range-last range)`

Equivalent (in running time as well) to `(range-ref range (- (range-length range) 1))`.

Example:

(range-last (numeric-range 10 30)) ⇒ 29

### Iteration

*[procedure]*

`(range-split-at range index)`

Returns two values: `(range-take range index)` and `(range-drop range index)`. It is an error if *index* is not an exact integer between 0 and the length of *range*, both inclusive. Runs in O(1) time.

Example:

(let-values (((ra rb) (range-split-at (numeric-range 10 20) 5))) (values (range->list ra) (range->list rb))) ⇒ (10 11 12 13 14) (15 16 17 18 19)

*[procedure]*

`(subrange range start end)`

Returns a range which contains the elements of range from index *start*, inclusive, through index *end*, exclusive. Runs in O(1) time. The average accessing time of the resulting range is asymptotically bounded by the average accessing time of *range*.

Examples:

(range->list (subrange (numeric-range 5 15) 5 8)) ⇒ (10 11 12) (range->list (subrange (string-range "abcdefghij") 2 8)) ⇒ (#\c #\d #\e #\f #\g #\h)

*[procedure]*

`(range-segment range length)`

Returns a list of ranges representing the consecutive subranges of length *length*. The last range is allowed to be shorter than *length*. The procedure runs in O(*k*) time, where *k* is the number of ranges returned. The average accessing time of the ranges is asymptotically bounded by the average accessing time of *range*.

Examples:

(map range->list (range-segment (numeric-range 0 12) 4)) ⇒ ((0 1 2 3) (4 5 6 7) (8 9 10 11)) (map range->list (range-segment (numeric-range 0 2 1/3) 4)) ⇒ ((0 1/3 2/3 1) (4/3 5/3))

*[procedure]*

`(range-take range count)`

*[procedure]*

`(range-take-right range count)`

Returns a range which contains the first/last *count* elements of *range*. These procedures run in O(1) time. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time of *range*.

Examples:

(range->list (range-take (numeric-range 0 10) 5)) ⇒ (0 1 2 3 4) (range->list (range-take-right (numeric-range 0 10) 5)) ⇒ (5 6 7 8 9)

*[procedure]*

`(range-drop range count)`

*[procedure]*

`(range-drop-right range count)`

Returns a range which contains all except the first/last *count* elements of *range*. These procedures run in O(1) time. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time respectively of *range*.

Examples:

(range->list (range-drop (numeric-range 0 10) 5)) ⇒ (5 6 7 8 9) (range->list (range-drop-right (numeric-range 0 10) 5)) ⇒ (0 1 2 3 4)

*[procedure]*

`(range-count pred range₁ range₂ …)`

Applies *pred* element-wise to the elements of *range*s and returns the number of applications which returned true values. If more than one range is given and not all ranges have the same length, range-count terminates when the shortest range is exhausted. The runtime of this procedure is O(*s*) where *s* is the sum of the total accessing times of the *range*s.

Examples:

(range-count even? (numeric-range 0 10)) ⇒ 5 (range-count < (numeric-range 0 10 2) (numeric-range 5 15)) ⇒ 5

*[procedure]*

`(range-any pred range₁ range₂ …)`

Applies *pred* element-wise to the elements of the *range*s and returns true if *pred* returns true on any application. Specifically it returns the last value returned by *pred*. Otherwise, `#f` is returned. If more than one range is given and not all ranges have the same length, *range-any* terminates when the shortest range is exhausted. The runtime of this procedure is O(*s*) where *s* is the sum of the total accessing times of the *ranges*.

Examples:

(range-any odd? (numeric-range 0 10)) ⇒ #t (range-any odd? (numeric-range 0 10 2)) ⇒ #f (range-any < (numeric-range 0 10 2) (numeric-range 5 15)) ⇒ #t

*[procedure]*

`(range-every pred range)`

Applies *pred* element-wise to the elements of the *range*s and returns true if *pred* returns true on every application. Specifically it returns the last value returned by *pred* , or `#t` if *pred* was never invoked. Otherwise, `#f` is returned. If more than one range is given and not all ranges have the same length, range-every terminates when the shortest range is exhausted. The runtime of this procedure is O(*s*) + O(*k*), where *s* is the sum of the total accessing times of the *ranges* and *k* is the number of *ranges*.

Examples:

(range-every integer? (numeric-range 0 10)) ⇒ #t (range-every odd? (numeric-range 0 10)) ⇒ #f (range-every < (numeric-range 0 10 2) (numeric-range 5 15)) ⇒ #f

*[procedure]*

`(range-map proc range₁ range₂ …)`

*[procedure]*

`(range-map->list proc range₁ range₂ …)`

*[procedure]*

`(range-map->vector proc range₁ range₂ …)`

Applies *proc* element-wise to the elements of the *range*s and returns a range/list/vector of the results, in order. If more than one range is given and not all ranges have the same length, these procedures terminate when the shortest range is exhausted. The dynamic order in which *proc* is actually applied to the elements is unspecified. The runtime of these procedures is O(*s*) where *s* is the sum of the total accessing times of the *ranges*. The range-map procedure eagerly computes its result and returns an expanded range. Its average accessing time is O(1).

Examples:

(range->list (range-map square (numeric-range 5 10))) ⇒ (25 36 49 64 81) (range->list (range-map + (numeric-range 0 5) (numeric-range 5 10))) ⇒ (5 7 9 11 13) (range-map->list square (numeric-range 5 10)) ⇒ (25 36 49 64 81) (range-map->vector square (numeric-range 5 10)) ⇒ #(25 36 49 64 81)

*[procedure]*

`(range-for-each proc range₁ range₂ …)`

Applies *proc* element-wise to the elements of the *ranges* in order. Returns an unspecified result. If more than one range is given and not all ranges have the same length, `range-for-each` terminates when the shortest range is exhausted. The runtime of this procedure is O(*s*) where *s* is the sum of the total accessing times of the *range*s.

Example:

(let((vec (make-vector 5))) (range-for-each (lambda(i) (vector-set! vec i (* i i))) (numeric-range 0 5)) vec) ⇒ #(0 1 4 9 16)

*[procedure]*

`(range-filter-map proc range₁ range₂ …)`

*[procedure]*

`(range-filter-map->list proc range₁ range₂ …)`

Applies *proc* element-wise to the elements of the *ranges* and returns a range/list of the true values returned by *proc*. If more than one range is given and not all ranges have the same length, these procedures terminate when the shortest range is exhausted. The dynamic order in which *proc* is actually applied to the elements is unspecified. The `range-filter-map` procedure eagerly computes its result and returns an expanded range. The runtime of these procedures is O(*n*) where *n* is the sum of the total accessing times of the *ranges*.

Examples:

(range->list (range-filter-map (lambda(x) (and (even? x) (* x x))) (numeric-range 0 10))) ⇒ (0 4 16 36 64) (range-filter-map->list (lambda(x y) (and (< x y) (* x y))) (numeric-range 0 10 2) (numeric-range 5 15)) ⇒ (0 12 28 48 72)

*[procedure]*

`(range-filter pred range)`

*[procedure]*

`(range-filter->list pred range)`

*[procedure]*

`(range-remove pred range)`

*[procedure]*

`(range-remove->list pred range)`

Returns a range/list containing the elements of *range* that satisfy / do not satisfy *pred*. The runtime of these procedures is O(*s*) where *s* is the sum of the total accessing times of the *ranges*.

The `range-filter` and `range-remove` procedures eagerly compute their results and return expanded ranges. Their average accessing time is O(1).

Examples:

(range->list (range-filter even? (numeric-range 0 10))) ⇒ (0 2 4 6 8) (range-filter->list odd? (numeric-range 0 10)) ⇒ (1 3 5 7 9) (range->list (range-remove even? (numeric-range 0 10))) ⇒ (1 3 5 7 9) (range-remove->list odd? (numeric-range 0 10)) ⇒ (0 2 4 6 8)

*[procedure]*

`(range-fold kons nil range₁ range₂ …)`

*[procedure]*

`(range-fold-right kons nil range₁ range₂ …)`

Folds *kons* over the elements of *range*s in order / reverse order. *kons* is applied as `(kons state (range-ref range₁ i) (range-ref range₂ i) …)` where `state` is the result of the previous invocation and *i* is the current index. For the first invocation, *nil* is used as the first argument. Returns the result of the last invocation, or *nil* if there was no invocation. If more than one range is given and not all ranges have the same length, these procedures terminate when the shortest range is exhausted. The runtime of these procedures is O(*s*) where *s* is the sum of the total accessing times of the *ranges*.

Examples:

(range-fold (lambda(n _) (+ 1 n)) 0 (numeric-range 0 30)) ⇒ 30 (range-fold + 0 (numeric-range 0 100) (numeric-range 50 70)) ⇒ 1380 (range-fold-right xcons '() (numeric-range 0 10)) ⇒ (0 1 2 3 4 5 6 7 8 9) (range-fold-right (lambda(lis x y) (cons (+ x y) lis)) '() (numeric-range 3 6) (numeric-range 5 12)) ⇒ (8 10 12)

### Searching

*[procedure]*

`(range-index pred range₁ range₂ …)`

*[procedure]*

`(range-index-right pred range₁ range₂ …)`

Applies *pred* element-wise to the elements of *ranges* and returns the index of the first/last element at which *pred* returns true. Otherwise, returns `#f`. If more than one range is given and not all ranges have the same length, `range-index` terminates when the shortest range is exhausted. It is an error if the ranges passed to `range-index-right` do not all have the same lengths. The runtime of these procedures is O(*s*) where *s* is the sum of the total accessing times of the *ranges*.

Examples:

(range-index (lambda(x) (> x 10)) (numeric-range 5 15)) ⇒ 6 (range-index odd? (numeric-range 0 10 2)) ⇒ #f (range-index = (numeric-range 0 12 2) (numeric-range 5 15)) ⇒ 5 (range-index-right odd? (numeric-range 0 5)) ⇒ 3

*[procedure]*

`(range-take-while pred range)`

*[procedure]*

`(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. The runtime of these procedures is asymptotically bounded by the total accessing time of the range. The average accessing time of the resulting range is O(1).

Examples:

(range->list (range-take-while (lambda(x) (< x 10)) (numeric-range 5 15))) ⇒ (5 6 7 8 9) (range->list (range-take-while-right (lambda(x) (> x 10)) (numeric-range 5 15))) ⇒ (11 12 13 14)

*[procedure]*

`(range-drop-while pred range)`

*[procedure]*

`(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. The runtime of these procedures is asymptotically bounded by the total accessing time of the range. The average accessing time of the resulting range is O(1).

Examples:

(range->list (range-drop-while (lambda(x) (< x 10)) (numeric-range 5 15))) ⇒ (10 11 12 13 14) (range->list (range-drop-while-right (lambda(x) (> x 10)) (numeric-range 5 15))) ⇒ (5 6 7 8 9 10)

### Conversion

*[procedure]*

`(range->list range)`

*[procedure]*

`(range->vector range)`

*[procedure]*

`(range->string range)`

Returns a list/vector/string containing the elements of *range* in order. It is an error to modify the result of `range->vector` or of `range->string`. In the case of `range->string`, it is an error if any element of *range* is not a character. The running times of these procedures is O(*s*) where *s* is the total accessing time for *range*.

Examples:

(range->list (numeric-range 0 0)) ⇒ () (range->vector (range 2 (lambda(i) (not (zero? i))))) ⇒ #(#f #t) (range->string (range 5 (lambda(i) (integer->char (+ 65 i))))) ⇒ "ABCDE"

*[procedure]*

`(vector->range vector)`

Returns an expanded range whose elements are those of *vector*. Note that, unlike `vector-range`, it is not an error to mutate *vector*; future mutations of *vector* are guaranteed not to affect the range returned by `vector->range`. This procedure runs in O(*n*) time, where *n* is the length of *vector*. Otherwise, this procedure is equivalent to `vector-range`.

Example

(range->list (vector->range #(1 3 5 7 9))) ⇒ (1 3 5 7 9)

*[procedure]*

`(range->generator range)`

Returns a SRFI 158 generator that generates the elements of *range* in order. This procedure runs in O(1) time, and the running time of each call of the generator is asymptotically bounded by the average accessing time of *range*.

Example

(generator->list (range->generator (numeric-range 0 10))) ⇒ (0 1 2 3 4 5 6 7 8 9)

## About This Egg

### Dependencies

The srfi-1, srfi-133, and srfi-145 eggs are required. srfi-78 is required to run the provided tests.

### Author

John Cowan & Wolfgang Corcoran-Mathe

Ported to Chicken 5 by Sergey Goldgaber

### Maintainer

Wolfgang Corcoran-Mathe

wcm at sigwinch dot xyzzy minus the zy

### Repository

### Version history

- 0.1
- Ported to Chicken Scheme 5
- 0.2
- Update maintainer information.
- 0.2.1
- Add types, adjust compile options, and minor cleanup.

### License

© 2020 John Cowan, Wolfgang Corcoran-Mathe.

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.