Changeset 39210 in project
 Timestamp:
 11/10/20 19:50:43 (3 weeks ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/5/srfi196
r39209 r39210 67 67 <procedure>(range length indexer)</procedure> 68 68 69 Returns a range whose length (number of elements) is length. The indexer procedure returns the nth element (where {{0 â€ n < length}}) of the range, given {{n}}. This procedure must run 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.69 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 must run 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}}. 70 70 71 71 ====== Examples … … 86 86 start, (+ start step), (+ start (* 2 step)), âŠ, (+ start (* n step)), 87 87 88 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 must run in O(1) time. The average accessing time of the resulting range must be O(1).88 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 must run in O(1) time. The average accessing time of the resulting range must be O(1). 89 89 90 90 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. … … 99 99 <procedure>(iotarange length [start [step]])</procedure> 100 100 101 Returns an iotanumeric range, a special case of a range specified by a length(a nonnegative 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 sequence101 Returns an iotanumeric range, a special case of a range specified by a {{length}} (a nonnegative 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 102 102 103 103 start, (+ start step), (+ start (* 2 step)), âŠ, (+ start (* ( length 1) step)), … … 109 109 <procedure>(vectorrange vector)</procedure> 110 110 111 Returns a range whose elements are those of vector. The procedure must run in O(1) time. The average accessing time of the resulting range must be O(1). It is an error to mutate vector.111 Returns a range whose elements are those of {{vector}}. The procedure must run in O(1) time. The average accessing time of the resulting range must be O(1). It is an error to mutate {{vector}}. 112 112 ====== Example 113 113 <enscript highlight="scheme"> … … 118 118 <procedure>(stringrange string)</procedure> 119 119 120 Returns a range whose elements are those of string. It is an error to mutate string. This procedure must run in O(n) time, where {{n}} is the length of string. The average accessing time of the resulting range must be O(1).120 Returns a range whose elements are those of {{string}}. It is an error to mutate {{string}}. This procedure must run in O(''n'') time, where ''n'' is the length of {{string}}. The average accessing time of the resulting range must be O(1). 121 121 122 122 In a Scheme that guarantees O(1) random access to strings, rangeref on a range created by stringrange can simply call stringref, and the resulting range is compact. But if only O(n) access is available, this procedure may have to copy the string's characters into a vector, resulting in an expanded range. … … 129 129 <procedure>(rangeappend range ...)</procedure> 130 130 131 Returns a range whose elements are the elements of the ranges in order. This procedure must run in O(n) + O(k) time, where {{n}} is the total number of elements in all the ranges and {{k}} is the number of ranges. 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.131 Returns a range whose elements are the elements of the {{range}}s in order. This procedure must run 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 {{range}}s. 132 132 ====== Example 133 133 <enscript highlight="scheme"> … … 140 140 <procedure>(range? obj)</procedure> 141 141 142 Returns {{#t}} if objis a range and {{#f}} otherwise. This procedure must run in O(1) time.142 Returns {{#t}} if {{obj}} is a range and {{#f}} otherwise. This procedure must run in O(1) time. 143 143 144 144 <procedure>(range=? equal range1 range2 ...)</procedure> 145 145 146 Returns {{#t}} if all the ranges 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.146 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. 147 147 ====== Examples 148 148 <enscript highlight="scheme"> … … 163 163 <procedure>(rangeref range n)</procedure> 164 164 165 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. The running time of this procedure must be asymptotically equal to the average accessing time of range.165 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 must be asymptotically equal to the average accessing time of {{range}}. 166 166 ====== Examples 167 167 <enscript highlight="scheme"> … … 189 189 <procedure>(rangesplitat range index)</procedure> 190 190 191 Returns two values: {{(rangetake range index)}} and {{(rangedrop range index)}}. It is an error if index is not an exact integer between 0 and the length of range, both inclusive. This procedure must run in O(1) time.191 Returns two values: {{(rangetake range index)}} and {{(rangedrop range index)}}. It is an error if {{index}} is not an exact integer between 0 and the length of {{range}}, both inclusive. This procedure must run in O(1) time. 192 192 ====== Example 193 193 <enscript highlight="scheme"> … … 200 200 <procedure>(subrange range start end)</procedure> 201 201 202 Returns a range which contains the elements of range from index {{start}}, inclusive, through index {{end}}, exclusive. This procedure must run in O(1) time. The average accessing time of the resulting range is asymptotically bounded by the average accessing time of range.202 Returns a range which contains the elements of range from index {{start}}, inclusive, through index {{end}}, exclusive. This procedure must run in O(1) time. The average accessing time of the resulting range is asymptotically bounded by the average accessing time of {{range}}. 203 203 ====== Examples 204 204 <enscript highlight="scheme"> … … 212 212 <procedure>(rangesegment range length)</procedure> 213 213 214 Returns a list of ranges representing the consecutive subranges of length length. The last range is allowed to be shorter than length. The procedure must run 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.214 Returns a list of ranges representing the consecutive subranges of length {{length}}. The last range is allowed to be shorter than {{length}}. The procedure must run 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}}. 215 215 216 216 <enscript highlight="scheme"> … … 228 228 <procedure>(rangetakeright range count) 229 229 ====== Description 230 Returns a range which contains the first/last count elements of range. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time of range.230 Returns a range which contains the first/last {{count}} elements of {{range}}. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time of {{range}}. 231 231 ====== Examples 232 232 <enscript highlight="scheme"> … … 244 244 245 245 ====== Description 246 Returns a range which contains all except the first/last count elements of range. These procedures must run in O(1) time. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time respectively of range.246 Returns a range which contains all except the first/last {{count}} elements of {{range}}. These procedures must run in O(1) time. The average accessing time of the resulting ranges is asymptotically bounded by the average accessing time respectively of {{range}}. 247 247 248 248 <enscript highlight="scheme"> … … 256 256 <procedure>(rangecount pred range1 range2 ...)</procedure> 257 257 258 Applies {{pred}} elementwise to the elements of ranges 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, rangecount 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.258 Applies {{pred}} elementwise 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, rangecount 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. 259 259 ====== Examples 260 260 <enscript highlight="scheme"> … … 265 265 <procedure>(rangeany pred range1 range2 ...)</procedure> 266 266 267 Applies {{pred}} elementwise to the elements of the ranges 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, rangeany 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.267 Applies {{pred}} elementwise 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, {{rangeany}} 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. 268 268 ====== Examples 269 269 <enscript highlight="scheme"> … … 275 275 <procedure>(rangeevery pred range)</procedure> 276 276 277 Applies {{pred}} elementwise to the elements of the ranges 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, rangeevery 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.277 Applies {{pred}} elementwise 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, rangeevery 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 {{range}}s and ''k'' is the number of {{range}}s. 278 278 ====== Examples 279 279 <enscript highlight="scheme"> … … 291 291 292 292 ====== Description 293 Applies {{proc}} elementwise to the elements of the ranges 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 rangemap procedure eagerly computes its result and returns an expanded range. Its average accessing time is O(1).293 Applies {{proc}} elementwise 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 {{range}}s. The rangemap procedure eagerly computes its result and returns an expanded range. Its average accessing time is O(1). 294 294 ====== Examples 295 295 <enscript highlight="scheme"> … … 306 306 <procedure>(rangeforeach proc range1 range2 ...)</procedure> 307 307 308 Applies {{proc}} elementwise 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, rangeforeach 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.308 Applies {{proc}} elementwise to the elements of the {{range}}s in order. Returns an unspecified result. If more than one range is given and not all ranges have the same length, {{rangeforeach}} 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. 309 309 ====== Example 310 310 <enscript highlight="scheme"> … … 321 321 322 322 ====== Description 323 Applies {{proc}} elementwise 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 rangefiltermap 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.323 Applies {{proc}} elementwise to the elements of the {{range}}s 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 {{rangefiltermap}} 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 {{range}}s. 324 324 ====== Examples 325 325 <enscript highlight="scheme"> … … 345 345 346 346 ====== Description 347 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.348 349 The rangefilter and rangeremoveprocedures eagerly compute their results and return expanded ranges. Their average accessing time is O(1).347 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 {{range}}s. 348 349 The {{rangefilter}} and {{rangeremove}} procedures eagerly compute their results and return expanded ranges. Their average accessing time is O(1). 350 350 ====== Examples 351 351 <enscript highlight="scheme"> … … 369 369 370 370 ====== Description 371 Folds {{kons}} over the elements of ranges in order / reverse order. {{kons}} is applied as ({{kons}} state (rangeref range1 i) (rangeref range2 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 must be O(s) where {{s}} is the sum of the total accessing times of the ranges.371 Folds {{kons}} over the elements of {{range}}s in order / reverse order. {{kons}} is applied as {{(kons state (rangeref range1 i) (rangeref range2 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 must be O(''s'') where ''s'' is the sum of the total accessing times of the {{range}}s. 372 372 ====== Examples 373 373 <enscript highlight="scheme"> … … 395 395 396 396 ====== Description 397 Applies {{pred}} elementwise 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, rangeindex terminates when the shortest range is exhausted. It is an error if the ranges passed to rangeindexright do not all have the same lengths. The runtime of these procedures must be O(s) where {{s}} is the sum of the total accessing times of the ranges.397 Applies {{pred}} elementwise to the elements of {{range}}s 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, {{rangeindex}} terminates when the shortest range is exhausted. It is an error if the ranges passed to {{rangeindexright}} do not all have the same lengths. The runtime of these procedures must be O(''s'') where ''s'' is the sum of the total accessing times of the {{range}}s. 398 398 ====== Examples 399 399 <enscript highlight="scheme"> … … 413 413 414 414 ====== Description 415 Returns a range containing the leading/trailing elements of rangethat 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).415 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). 416 416 ====== Examples 417 417 <enscript highlight="scheme"> … … 431 431 432 432 ====== Description 433 Returns a range that omits leading/trailing elements of rangethat 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).433 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). 434 434 ====== Examples 435 435 <enscript highlight="scheme"> … … 452 452 453 453 ====== Description 454 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.454 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}}. 455 455 ====== Examples 456 456 <enscript highlight="scheme"> … … 465 465 <procedure>(vector>range vector)</procedure> 466 466 467 Returns an expanded range whose elements are those of vector. Note that, unlike vectorrange, 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 must run in O(n) where {{n}} is the length of vector. Otherwise, this procedure is equivalent to vectorrange.467 Returns an expanded range whose elements are those of {{vector}}. Note that, unlike {{vectorrange}}, 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 must run in O(''n'') time, where ''n'' is the length of {{vector}}. Otherwise, this procedure is equivalent to {{vectorrange}}. 468 468 ====== Example 469 469 <enscript highlight="scheme"> … … 473 473 <procedure>(range>generator range)</procedure> 474 474 475 Returns a SRFI 158 generator that generates the elements of range in order. This procedure must run in O(1) time, and the running time of each call of the generator is asymptotically bounded by the average accessing time of range.475 Returns a SRFI 158 generator that generates the elements of {{range}} in order. This procedure must run in O(1) time, and the running time of each call of the generator is asymptotically bounded by the average accessing time of {{range}}. 476 476 ====== Example 477 477 <enscript highlight="scheme">
Note: See TracChangeset
for help on using the changeset viewer.