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

[[toc:]]

== SRFI Description

This page includes excerpts from the
[[https://srfi.schemers.org/srfi-196/srfi-196.html|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:
<table>
<tr><td>''obj''</td><td>Any Scheme object.</td></tr>
<tr><td>''range''</td><td>A range object.</td></tr>
<tr><td>''pred''</td><td>A predicate that accepts zero or more arguments.</td></tr>
<tr><td>''equal''</td><td>A predicate that accepts two arguments and returns a boolean value. It is not necessarily an equivalence relation.</td></tr>
<tr><td>''length''</td><td>An exact positive integer.</td></tr>
<tr><td>''proc''</td><td>A procedure that accepts zero or more arguments and returns zero or more values.</td></tr>
<tr><td>''list''</td><td>A Scheme list.</td></tr>
<tr><td>''vector''</td><td>A Scheme vector.</td></tr>
<tr><td>''string''</td><td>A Scheme string.</td></tr>
</table>

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)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(numeric-range start end [step])</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(iota-range length [start [step]])</procedure>

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)</procedure>

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:

<enscript highlight="scheme">
(range->list (vector-range #(1 3 5 7 9)))
  ⇒ (1 3 5 7 9)
</enscript>

<procedure>(string-range string)</procedure>

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:

<enscript highlight="scheme">
(range->list (string-range "abcde"))
  ⇒ (#\a #\b #\c #\d #\e)
</enscript>

<procedure>(range-append range …)</procedure>

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:

<enscript highlight="scheme">
(range->list (range-append (numeric-range 0 3)
                           (numeric-range 3 6)))
  ⇒ (0 1 2 3 4 5)
</enscript>

=== Predicates

<procedure>(range? obj)</procedure>

Returns {{#t}} if ''obj'' is a range and {{#f}} otherwise.

<procedure>(range=? equal range1 range2 …)</procedure>

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:

<enscript highlight="scheme">
(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
</enscript>

=== Accessors

<procedure>(range-length range)</procedure>

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

Example:

<enscript highlight="scheme">
(range-length (numeric-range 10 30)) ⇒ 20
</enscript>

<procedure>(range-ref range n)</procedure>

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:

<enscript highlight="scheme">
(range-ref (numeric-range 10 30) 5) ⇒ 15
(range-ref (range 2 (lambda (i) (not (zero? i)))) 1) ⇒ #t
</enscript>

<procedure>(range-first range)</procedure>

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

Example:

<enscript highlight="scheme">
(range-first (numeric-range 10 30)) ⇒ 10
</enscript>

<procedure>(range-last range)</procedure>

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

Example:

<enscript highlight="scheme">
(range-last (numeric-range 10 30)) ⇒ 29
</enscript>

=== Iteration

<procedure>(range-split-at range index)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(subrange range start end)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-segment range length)</procedure>

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:

<enscript highlight="scheme">
(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))
</enscript>

<procedure>(range-take range count)</procedure>

<procedure>(range-take-right range count)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-drop range count)</procedure>

<procedure>(range-drop-right range count)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-count pred range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(range-count even? (numeric-range 0 10)) ⇒ 5
(range-count < (numeric-range 0 10 2) (numeric-range 5 15)) ⇒ 5
</enscript>

<procedure>(range-any pred range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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
</enscript>

<procedure>(range-every pred range)</procedure>

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:

<enscript highlight="scheme">
(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
</enscript>

<procedure>(range-map proc range₁ range₂ …)</procedure>

<procedure>(range-map->list proc range₁ range₂ …)</procedure>

<procedure>(range-map->vector proc range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-for-each proc range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-filter-map proc range₁ range₂ …)</procedure>

<procedure>(range-filter-map->list proc range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-filter pred range)</procedure>

<procedure>(range-filter->list pred range)</procedure>

<procedure>(range-remove pred range)</procedure>

<procedure>(range-remove->list pred range)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-fold kons nil range₁ range₂ …)</procedure>

<procedure>(range-fold-right kons nil range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

=== Searching

<procedure>(range-index pred range₁ range₂ …)</procedure>

<procedure>(range-index-right pred range₁ range₂ …)</procedure>

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:

<enscript highlight="scheme">
(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
</enscript>

<procedure>(range-take-while pred range)</procedure>

<procedure>(range-take-while-right pred range)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

<procedure>(range-drop-while pred range)</procedure>

<procedure>(range-drop-while-right pred range)</procedure>

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:

<enscript highlight="scheme">
(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)
</enscript>

=== Conversion

<procedure>(range->list range)</procedure>

<procedure>(range->vector range)</procedure>

<procedure>(range->string range)</procedure>

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:

<enscript highlight="scheme">
(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"
</enscript>

<procedure>(vector->range vector)</procedure>

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

<enscript highlight="scheme">
(range->list (vector->range #(1 3 5 7 9))) ⇒ (1 3 5 7 9)
</enscript>

<procedure>(range->generator range)</procedure>

Returns a [[srfi-158|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

<enscript highlight="scheme">
(generator->list (range->generator (numeric-range 0 10)))
  ⇒ (0 1 2 3 4 5 6 7 8 9)
</enscript>

== About This Egg

=== Dependencies

The [[srfi-1]] and [[srfi-133]] eggs are required.
[[test]] 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

[[https://github.com/Zipheir/srfi-196|GitHub]]

=== Version history

; [[https://github.com/diamond-lizard/srfi-196/releases/tag/0.1|0.1]] : Ported to Chicken Scheme 5
; 0.2 : Update maintainer information.
; 0.2.1 : Add types, adjust compile options, and minor cleanup.
; 1.0.0 : Fix types, type checks and other assertions are now mandatory.

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