source: project/wiki/eggref/5/srfi-121 @ 38870

Last change on this file since 38870 was 38870, checked in by Mario Domenech Goulart, 2 months ago

eggref/5/srfi-121: add documentation for C5

File size: 20.0 KB
Line 
1== SRFI-121: Generators
2
3This SRFI defines utility procedures that create, transform, and consume
4generators. A generator is simply a procedure with no arguments that works as a
5source of a series of values. Every time it is called, it yields a value.
6Generators may be finite or infinite; a finite generator returns an end-of-file
7object to indicate that it is exhausted. For example, {{read-char}},
8{{read-line}}, and {{read}} are generators that generate characters, lines, and
9objects from the current input port. Generators provide lightweight laziness.
10
11[[toc:]]
12
13== Installation
14
15 $ chicken-install srfi-121
16
17or
18
19 $ chicken-install srfi-121 -test
20
21if you want to run the tests for the egg in addition.
22
23== SRFI Description
24
25For a full description of this SRFI, see the full SRFI
26[[http://srfi.schemers.org/srfi-121/srfi-121.html|document]]. This
27documentation covers the API only.
28
29== Generators
30
31Generators can be divided into two classes, finite and infinite. Both kinds of
32generators can be invoked an indefinite number of times. After a finite
33generator has generated all its values, it will return an end-of-file object
34for all subsequent calls. A generator is said to be exhausted if calling it
35will return an end-of-file object. By definition, infinite generators can never
36be exhausted.
37
38A generator is said to be in an undefined state if it cannot be determined
39exactly how many values it has generated. This arises because it is impossible
40to tell by inspecting a generator whether it is exhausted or not. For example,
41{{(generator-fold + 0 (generator 1 2 3) (generator 1 2))}} will compute 0 + 1 +
421 + 2 + 2 = 6, at which time the second generator will be exhausted. If the
43first generator is invoked, however, it may return either 3 or an end-of-file
44object, depending on whether the implementation of {{generator-fold}} has
45invoked it or not. Therefore, the first generator is said to be in an undefined
46state.
47
48=== Constructors
49
50The result of a generator constructor is just a procedure, so printing it
51doesn't show much. In the examples in this section we use {{generator->list}}
52to convert the generator to a list.
53
54These procedures have names ending with generator.
55
56<procedure>(generator arg ...)</procedure>
57
58The simplest finite generator. Generates each of its arguments in turn. When no
59arguments are provided, it returns an empty generator that generates no values.
60
61<procedure>(make-iota-generator count [start [step]])</procedure>
62
63Creates a finite generator of a sequence of {{count}} numbers. The sequence
64begins with {{start}} (which defaults to 0) and increases by {{step}} (which
65defaults to 1).  If both {{start}} and {{step}} are exact, it generates exact
66numbers; otherwise it generates inexact numbers. The exactness of {{count}}
67doesn't affect the exactness of the results.
68
69
70<enscript highlight="scheme">
71(generator->list (make-iota-generator 3 8))
72 â‡’ (8 9 10)
73
74(generator->list (make-iota-generator 3 8 2))
75 â‡’ (8 10 12)
76</enscript>
77
78<procedure>(make-range-generator start [end [step]])</procedure>
79
80Creates a generator of a sequence of numbers. The sequence begins with
81{{start}}, increases by {{step}} (default 1), and continues while the number is
82less than {{end}}, or forever if end is omitted. If both {{start}} and {{step}}
83are exact, it generates exact numbers; otherwise it generates inexact numbers.
84The exactness of {{end}} doesn't affect the exactness of the results.
85
86<enscript highlight="scheme">
87(generator->list (make-range-generator 3) 4)
88 â‡’ (3 4 5 6)
89(generator->list (make-range-generator 3 8))
90 â‡’ (3 4 5 6 7)
91(generator->list (make-range-generator 3 8 2))
92 â‡’ (3 5 7)
93</enscript>
94
95<procedure>(make-coroutine-generator proc)</procedure>
96
97Creates a generator from a coroutine.
98
99The {{proc}} argument is a procedure that takes one argument, {{yield}}. When
100called, {{make-coroutine-generator}} immediately returns a generator {{g}}.
101When {{g}} is called, {{proc}} runs until it calls {{yield}}. Calling {{yield}}
102causes the execution of {{proc}} to be suspended, and {{g}} returns the value
103passed to {{yield}}.
104
105Whether this generator is finite or infinite depends on the behavior of
106{{proc}}.  If {{proc}} returns, it is the end of the sequence — {{g}} returns
107an end-of-file object from then on. The return value of {{proc}} is ignored.
108
109The following code creates a generator that produces a series 0, 1, and 2
110(effectively the same as {{(make-range-generator 0 3)}} and binds it to {{g}}.
111
112<enscript highlight="scheme">
113(define g
114  (make-coroutine-generator
115   (lambda (yield)
116     (let loop ((i 0))
117       (when (< i 3) (yield i) (loop (+ i 1)))))))
118
119(generator->list g) ⇒ (0 1 2)
120</enscript>
121
122<procedure>(list->generator lis)</procedure>
123<procedure>(vector->generator vec [start [end]])</procedure>
124<procedure>(reverse-vector->generator vec [start [end]])</procedure>
125<procedure>(string->generator str [start [end]])</procedure>
126<procedure>(bytevector->generator bytevector [start [end]])</procedure>
127
128These procedures return generators that yield each element of the given
129argument. Mutating the underlying object will affect the results of the
130generator.
131
132<enscript highlight="scheme">
133(generator->list (list->generator '(1 2 3 4 5)))
134 â‡’ (1 2 3 4 5)
135(generator->list (vector->generator '#(1 2 3 4 5)))
136 â‡’ (1 2 3 4 5)
137(generator->list (reverse-vector->generator '#(1 2 3 4 5)))
138 â‡’ (5 4 3 2 1)
139(generator->list (string->generator "abcde"))
140 â‡’ (#\a #\b #\c #\d #\e)
141</enscript>
142
143The generators returned by the constructors are exhausted once all elements are
144retrieved; the optional {{start}}-th and {{end}}-th arguments can limit the
145range the generator walks across.
146
147For {{reverse-vector->generator}}, the first value is the element right before
148the {{end}}-th element, and the last value is the {{start}}-th element. For all
149the other constructors, the first value the generator yields is the
150{{start}}-th element, and it ends right before the {{end}}-th element.
151
152
153<enscript highlight="scheme">
154(generator->list (vector->generator '#(a b c d e) 2))
155 â‡’ (c d e)
156(generator->list (vector->generator '#(a b c d e) 2 4))
157 â‡’ (c d)
158(generator->list (reverse-vector->generator '#(a b c d e) 2))
159 â‡’ (e d c)
160(generator->list (reverse-vector->generator '#(a b c d e) 2 4))
161 â‡’ (d c)
162(generator->list (reverse-vector->generator '#(a b c d e) 0 2))
163 â‡’ (b a)
164</enscript>
165
166<procedure>(make-for-each-generator for-each obj)</procedure>
167
168A generator constructor that converts any collection {{obj}} to a generator
169that returns its elements using a {{for-each}} procedure appropriate for
170{{obj}}. This must be a procedure that when called as {{(for-each proc obj)}}
171calls {{proc}} on each element of {{obj}}. Examples of such procedures are
172{{for-each}}, {{string-for-each}}, and {{vector-for-each}} from R7RS. The value
173returned by {{for-each}} is ignored. The generator is finite if the collection
174is finite, which would typically be the case.
175
176The collections need not be conventional ones (lists, strings, etc.) as long as
177{{for-each}} can invoke a procedure on everything that counts as a member. For
178example, the following procedure allows {{for-each-generator}} to generate the
179digits of an integer from least to most significant:
180
181<enscript highlight="scheme">
182(define (for-each-digit proc n)
183  (when (> n 0)
184    (let-values (((div rem) (truncate/ n 10)))
185      (proc rem)
186      (for-each-digit proc div))))
187</enscript>
188
189<procedure>(make-unfold-generator stop? mapper successor seed)</procedure>
190
191A generator constructor similar to SRFI 1's {{unfold}}.
192
193The {{stop?}} predicate takes a {{seed}} value and determines whether to stop.
194The {{mapper}} procedure calculates a value to be returned by the generator
195from a seed value. The {{successor}} procedure calculates the next seed value
196from the current seed value.
197
198For each call of the resulting generator, {{stop?}} is called with the current
199seed value. If it returns true, then the generator returns an end-of-file
200object. Otherwise, it applies {{mapper}} to the current seed value to get the
201value to return, and uses {{successor}} to update the seed value.
202
203This generator is finite unless {{stop?}} never returns true.
204
205<enscript highlight="scheme">
206(generator->list (make-unfold-generator
207                      (lambda (s) (> s 5))
208                      (lambda (s) (* s 2))
209                      (lambda (s) (+ s 1))
210                      0))
211 â‡’ (0 2 4 6 8 10)
212</enscript>
213
214=== Operations
215
216The following procedures accept one or more generators and return a new
217generator without consuming any elements from the source generator(s). In
218general, the result will be a finite generator if the arguments are.
219
220The names of these procedures are prefixed with g.
221
222<procedure>(gcons* item ... gen)</procedure>
223
224Returns a generator that adds {{items}} in front of {{gen}}. Once the {{items}}
225have been consumed, the generator is guaranteed to tail-call {{gen}}.
226
227<enscript highlight="scheme">
228(generator->list (gcons* 'a 'b (make-range-generator 0 2)))
229 â‡’ (a b 0 1)
230</enscript>
231
232<procedure>(gappend gen ...)</procedure>
233
234Returns a generator that yields the items from the first given generator, and
235once it is exhausted, from the second generator, and so on.
236
237<enscript highlight="scheme">
238(generator->list (gappend (make-range-generator 0 3) (make-range-generator 0 2)))
239 â‡’ (0 1 2 0 1)
240(generator->list (gappend))
241 â‡’ ()
242</enscript>
243
244<procedure>(gcombine proc seed gen gen2 ...)</procedure>
245
246A generator for mapping with state. It yields a sequence of sub-folds over
247{{proc}}.
248
249The {{proc}} argument is a procedure that takes as many arguments as the input
250generators plus one. It is called as {{(proc v1 v2 
 seed)}}, where {{v1}},
251{{v2}}, ... are the values yielded from the input generators, and {{seed}} is
252the current seed value. It must return two values, the yielding value and the
253next seed. The result generator is exhausted when any of the {{genn}}
254generators is exhausted, at which time all the others are in an undefined
255state.
256
257<procedure>(gfilter pred gen)</procedure>
258<procedure>(gremove pred gen)</procedure>
259
260Return generators that yield the items from the source generator, except those
261on which {{pred}} answers false or true respectively.
262
263<procedure>(gtake gen k [padding])</procedure>
264<procedure>(gdrop gen k)</procedure>
265
266These are generator analogues of SRFI 1 {{take}} and {{drop}}. {{gtake}}
267returns a generator that yields (at most) the first {{k}} items of the source
268generator, while {{gdrop}} returns a generator that skips the first {{k}} items of
269the source generator.
270
271These won't complain if the source generator is exhausted before generating
272{{k}} items. By default, the generator returned by {{gtake}} terminates when
273the source generator does, but if you provide the padding argument, then the
274returned generator will yield exactly {{k}} items, using the padding value as
275needed to provide sufficient additional values.
276
277<procedure>(gtake-while pred gen)</procedure>
278<procedure>(gdrop-while pred gen)</procedure>
279
280The generator analogues of SRFI-1 {{take-while}} and {{drop-while}}. The
281generator returned from {{gtake-while}} yields items from the source generator
282as long as {{pred}} returns true for each. The generator returned from
283{{gdrop-while}} first reads and discards values from the source generator while
284{{pred}} returns true for them, then starts yielding items returned by the
285source.
286
287<procedure>(gdelete item gen [=])</procedure>
288
289Creates a generator that returns whatever {{gen}} returns, except for any items
290that are the same as {{item}} in the sense of {{=,}} which defaults to
291{{equal?}}. The {{=}} predicate is passed exactly two arguments, of which the
292first was generated by gen before the second.
293
294<enscript highlight="scheme">
295(generator->list (gdelete 3 (generator 1 2 3 4 5 3 6 7)))
296 â‡’ (1 2 4 5 6 7)
297</enscript>
298
299<procedure>(gdelete-neighbor-dups gen [=])</procedure>
300
301Creates a generator that returns whatever {{gen}} returns, except for any items
302that are equal to the preceding item in the sense of {{=}}, which defaults to
303{{equal?}}. The {{=}} predicate is passed exactly two arguments, of which the
304first was generated by {{gen}} before the second.
305
306<enscript highlight="scheme">
307(generator->list (gdelete-neighbor-dups (list->generator '(a a b c a a a d c))))
308  ⇒ (a b c a d c)
309</enscript>
310
311<procedure>(gindex value-gen index-gen)</procedure>
312
313Creates a generator that returns elements of {{value-gen}} specified by the
314indices (non-negative exact integers) generated by {{index-gen}}. It is an
315error if the indices are not strictly increasing, or if any index exceeds the
316number of elements generated by {{value-gen}}. The result generator is
317exhausted when either generator is exhausted, at which time the other is in an
318undefined state.
319
320<enscript highlight="scheme">
321(generator->list (gindex (list->generator '(a b c d e f))
322                         (list->generator '(0 2 4))))
323 â‡’ (a c e)
324</enscript>
325
326<procedure>(gselect value-gen truth-gen)</procedure>
327
328Creates a generator that returns elements of {{value-gen}} that correspond to
329the values generated by {{truth-gen}}. If the current value of {{truth-gen}} is
330true, the current value of {{value-gen}} is generated, but otherwise not. The
331result generator is exhausted when either generator is exhausted, at which time
332the other is in an undefined state.
333
334<enscript highlight="scheme">
335(generator->list (gselect (list->generator '(a b c d e f))
336                          (list->generator '(#t #f #f #t #t #f))))
337 â‡’ (a d e)
338</enscript>
339
340=== Consuming Generated Values
341
342Unless otherwise noted, these procedures consume all the values available from
343the generator that is passed to them, and therefore will not return if one or
344more generator arguments are infinite. They have names prefixed with generator.
345
346<procedure>(generator->list generator [k])</procedure>
347
348Reads items from generator and returns a newly allocated list of them. By
349default, it reads until the generator is exhausted.
350
351If an optional argument {{k}} is given, it must be a non-negative integer, and
352the list ends when either {{k}} items are consumed, or generator is exhausted;
353therefore generator can be infinite in this case.
354
355<procedure>(generator->reverse-list generator [k])</procedure>
356
357Reads items from generator and returns a newly allocated list of them in
358reverse order. By default, this reads until the generator is exhausted.
359
360If an optional argument {{k}} is given, it must be a non-negative integer, and
361the list ends when either {{k}} items are read, or generator is exhausted;
362therefore generator can be infinite in this case.
363
364<procedure>(generator->vector generator [k])</procedure>
365
366Reads items from generator and returns a newly allocated vector of them. By
367default, it reads until the generator is exhausted.
368
369If an optional argument {{k}} is given, it must be a non-negative integer, and
370the list ends when either {{k}} items are consumed, or generator is exhausted;
371therefore generator can be infinite in this case.
372
373<procedure>(generator->vector! vector at generator)</procedure>
374
375Reads items from generator and puts them into vector starting at index {{at}},
376until vector is full or generator is exhausted. Generator can be infinite. The
377number of elements generated is returned.
378
379<procedure>(generator->string generator [k])</procedure>
380
381Reads items from generator and returns a newly allocated string of them. It is
382an error if the items are not characters. By default, it reads until the
383generator is exhausted.
384
385If an optional argument {{k}} is given, it must be a non-negative integer, and the
386string ends when either {{k}} items are consumed, or generator is exhausted;
387therefore generator can be infinite in this case.
388
389<procedure>(generator-fold proc seed gen1 gen2 ...)</procedure>
390
391Works like SRFI 1 {{fold}} on the values generated by the generator arguments.
392
393When one generator is given, for each value {{v}} generated by {{gen}},
394{{proc}} is called as {{(proc v r)}}, where {{r}} is the current accumulated
395result; the initial value of the accumulated result is {{seed}}, and the return
396value from {{proc}} becomes the next accumulated result. When {{gen}} is
397exhausted, the accumulated result at that time is returned from
398{{generator-fold}}.
399
400When more than one generator is given, {{proc}} is invoked on the values
401returned by all the generator arguments followed by the current accumulated
402result. The procedure terminates when any of the {{genn}} generators is
403exhausted, at which time all the others are in an undefined state.
404
405<enscript highlight="scheme">
406(with-input-from-string "a b c d e"
407  (lambda () (generator-fold cons 'z read)))
408 â‡’ (e d c b a . z)
409</enscript>
410
411<procedure>(generator-for-each proc gen gen2 
)</procedure>
412
413A generator analogue of {{for-each}} that consumes generated values using side
414effects. Repeatedly applies proc on the values yielded by {{gen}}, {{gen2}} ...
415until any one of the generators is exhausted. The values returned from proc are
416discarded. The procedure terminates when any of the {{genn}} generators is
417exhausted, at which time all the others are in an undefined state. Returns an
418unspecified value.
419
420<procedure>(generator-find pred gen)</procedure>
421
422Returns the first item from the generator {{gen}} that satisfies the predicate
423{{pred}}, or {{#f}} if no such item is found before gen is exhausted. If
424{{gen}} is infinite, {{generator-find}} will not return if it cannot find an
425appropriate item.
426
427<procedure>(generator-count pred gen)</procedure>
428
429Returns the number of items available from the generator {{gen}} that satisfy
430the predicate {{pred}}.
431
432<procedure>(generator-any pred gen)</procedure>
433
434Applies {{pred}} to each item from {{gen}}. As soon as it yields a true value,
435the value is returned without consuming the rest of {{gen}}. If {{gen}} is
436exhausted, returns {{#f}}.
437
438<procedure>(generator-every pred gen)</procedure>
439
440Applies {{pred}} to each item from {{gen}}. As soon as it yields a false value,
441the value is returned without consuming the rest of {{gen}}. If {{gen}} is
442exhausted, returns the last value returned by {{pred}}, or {{#t}} if {{pred}}
443was never called.
444
445<procedure>(generator-unfold gen unfold arg ...)</procedure>
446
447Equivalent to {{(unfold eof-object? (lambda (x) x) (lambda (x) (gen)) (gen) arg
448...)}}. The values of {{gen}} are unfolded into the collection that {{unfold}}
449creates.
450
451The signature of the {{unfold}} procedure is {{(unfold stop? mapper successor
452seed args ...)}}. Note that the {{vector-unfold}} and {{vector-unfold-right}}
453of SRFI 43 and SRFI 133 do not have this signature and cannot be used with this
454procedure. To unfold into a vector, use SRFI 1's {{unfold}} and then apply
455{{list->vector}} to the result.
456
457<enscript highlight="scheme">
458;; Iterates over string and unfolds into a list using SRFI 1 unfold
459(generator-unfold (make-for-each-generator string-for-each "abc") unfold)
460 â‡’ (#\a #\b #\c)
461</enscript>
462
463== Repository
464
465[[https://github.com/ThatGeoGuy/srfi-121|Github]]
466
467== Version History
468
469; 1.7 : CHICKEN 5 support
470; 1.5 : Updates to the tests (see [[http://srfi-email.schemers.org/srfi-121/msg/4817161|mailing list]] for details).
471; 1.4 : Adds Kevin Wortman's fix to generator->list and generator->reverse-list
472; 1.3 : Removes hardcoded .so in setup
473; 1.2 : Adds standard README.org to repo
474; 1.1 : Fixes generator->list from upstream issue
475; 1.0 : Initial release
476
477== License
478
479Copyright (C) John Cowan (2015-2016). All Rights Reserved.
480
481Permission is hereby granted, free of charge, to any person obtaining a copy of
482this software and associated documentation files (the "Software"), to deal in
483the Software without restriction, including without limitation the rights to
484use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
485of the Software, and to permit persons to whom the Software is furnished to do
486so, subject to the following conditions:
487
488The above copyright notice and this permission notice shall be included in all
489copies or substantial portions of the Software.
490
491THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
492IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
493FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
494AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
495LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
496OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
497SOFTWARE.
Note: See TracBrowser for help on using the repository browser.