source: project/wiki/eggref/5/sequences @ 40224

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

eggref/5/sequences: fix usage (s/require-extension/import/)

File size: 12.3 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== sequences
5
6=== Introduction
7
8Operations over generic or user-defined sequences.
9
10''Note: this is currently under review - the API might still change''
11
12=== Usage
13
14<enscript highlight=scheme>
15(import sequences)
16</enscript>
17
18=== Requirements
19
20[[fast-generic]]
21
22=== Documentation
23
24A ''sequence'' is a collection of objects and may be either one of the
25built-in types vector, list or string, or the result of the
26sequence-constructors {{make-linear-sequence}} and
27{{make-random-access-sequences}}. A ''linear'' sequence is a sequence
28that only allows element-by-element access (i.e. a list), a ''random
29access'' sequences allows access to arbitrary elements through an index
30(i.e. vectors or strings).
31
32An ''iterator'' is an object that designates a particular position
33in a linear or random-access sequence.
34
35==== Basic sequence operations
36
37===== size
38
39<procedure>(size S)</procedure>
40
41Returns the number of elements in the sequence {{S}}. For linear
42sequences, this operation traverses all elements.
43
44===== elt
45
46<procedure>(elt S I)</procedure>
47
48Returns the {{I}}-th element of {{S}}. {{I}} may be an exact integer or
49an iterator (see below).
50
51A sequence-element can be modified with {{(set! (elt S I) X)}}.
52
53If {{I}} is an iterator, then {{S}} must be the same sequence that had
54been used to construct the iterator.
55
56===== rev
57
58<procedure>(rev S)</procedure>
59
60Returns a new sequence of the same type with the elements of {{S}} in
61reverse order.
62
63===== foldl
64
65<procedure>(foldl PROC SEED S)</procedure>
66
67Performs a left "fold" over the sequence {{S}}, where the procedure
68{{PROC}} is applied to its previous result (or {{SEED}} for the first
69element) and each sequence-element.
70
71===== foldr
72
73<procedure>(foldr PROC SEED S)</procedure>
74
75A right "fold" over sequence {{S}}, {{PROC}} is applied to each
76sequence element and the result of its last invocation (or {{SEED}}
77for the first element).
78
79===== sub
80
81<procedure>(sub S START [END])</procedure>
82
83Returns a new sequence with the elements of {{S}}, starting at position
84{{START}} up to but not including the element at position {{END}}.
85If {{END}} is not given, all remaining elements are returned. {{START}}
86and {{END}} may be exact integers or iterators.
87
88A range of elements may be modified by executing
89{{(set! (sub S1 START [END]) S2)}}, which assigns the elements of {{S2}}
90to the designated locations of sequence {{S1}}.
91
92===== pos
93
94<procedure>(pos PRED S)</procedure>
95
96Returns the index of the first element in {{S}} that for which the
97one argument procedure {{PRED}} returns true. If {{PRED}} returns
98false for all arguments, {{#f}} is returned.
99
100===== take
101
102<procedure>(take PRED S)</procedure>
103
104Returns a new sequence of the same type as {{S}} with the
105elements up to but not including the first element for
106which the one-argument procedure {{PRED}} returns {{#f}}.
107
108===== drop
109
110<procedure>(drop PRED S)</procedure>
111
112Returns a new sequence of the same type as {{S}} with the
113elements from the first element for
114which the one-argument procedure {{PRED}} returns {{#f}}.
115
116===== split
117
118<procedure>(split PRED S)</procedure>
119
120Returns two sequences of the same type as {{S}} holding
121the elements split at the first position for which the
122one-argument procedure {{PRED}} returns {{#f}}.
123
124===== partition
125
126<procedure>(partition PRED S)</procedure>
127
128Returns two sequences of the same type as {{S}} holding those elements
129for which the one-argument procedure {{PRED}} returns true and false,
130respectively.
131
132===== fill!
133
134<procedure>(fill! PROC S [START [END]])</procedure>
135
136Calls {{PROC}} with the sequence {{S}} and an iterator object over
137the elements in {{S}} starting at position {{START}} up to
138but not including {{END}} and returns the modified sequence.
139
140===== all?
141
142<procedure>(all? PROC S)</procedure>
143
144Returns true if {{PROC}} returns true for all elements of {{S}}.
145
146===== thereis?
147
148<procedure>(thereis? PROC S)</procedure>
149
150Returns {{#t}} if {{S}} contains an element for which {{PROC}} returns
151true.
152
153===== empty?
154
155<procedure>(empty? S)</procedure>
156
157Returns true if {{S}} is of size 0.
158
159===== peek
160
161<procedure>(peek S)</procedure>
162
163Returns the first element of {{S}}.
164
165===== pop
166
167<procedure>(pop S)</procedure>
168
169Returns all but the first element of {{S}}.
170
171===== filter
172
173<procedure>(filter PROTO PROC S)</procedure>
174
175Returns a new sequence of the same type as {{PROTO}} with all elements
176of {{S}} for which {{PROC}} returns true.
177
178
179==== Set-operations
180
181===== intersection
182
183<procedure>(intersection PROTO COMPARE S1 ...)</procedure>
184
185Returns the intersection of sequences {{S1 ...}} using the two-argument procedure
186{{COMPARE}} to compare the elements. The returned sequence is of the same type
187as {{PROTO}}.
188
189
190===== difference
191
192<procedure>(difference PROTO COMPARE S1 S2 ...)</procedure>
193
194Returns the set-difference of sequences {{S2 ...}} taken from {{S1}}
195using the two-argument procedure {{COMPARE}} to compare the
196elements. The returned sequence is of the same type as {{PROTO}}.
197
198
199===== union
200
201<procedure>(union PROTO COMPARE S1 ...)</procedure>
202
203Returns the union of sequences {{S1 ...}} using the two-argument procedure
204{{COMPARE}} to compare the elements. The returned sequence is of the same type
205as {{PROTO}}.
206
207
208==== Predicates over sequence types
209
210===== sequence?
211
212<procedure>(sequence? X)</procedure>
213
214Returns {{#t}} if {{X}} is a sequence or {{#f}} otherwise.
215
216===== linear-sequence?
217
218<procedure>(linear-sequence? X)</procedure>
219
220Reurns {{#t}} if {{X}} is a list or a sequence created with
221{{make-linear-sequence}} or {{#f}} otherwise.
222
223===== random-access-sequence?
224
225<procedure>(random-access-sequence? X)</procedure>
226
227Returns {{#t}} if {{X}} is a vector, a string or a sequence created
228with {{make-random-access-sequence}}, or {{#f}} otherwise.
229
230==== Sequence constructors
231
232===== make-random-access-sequence
233
234<procedure>(make-random-access-sequence MAKE ELT SIZE)</procedure>
235
236Returns an object representing a sequence that allows random access
237to its elements. {{MAKE}} should be a procedure of two arguments,
238a size count and an initial value and should return a collection
239of elements which will be stored as "data" in the sequence object.
240{{ELT}} should be a procedure of two arguments receiving the
241"data" and an exact integer index and should return the element
242inside the data collection at the given position. {{SIZE}} should
243be a procedure that receives the data and returns the number of
244elements in that collection.
245
246Note that the "data" may be anything - the operators fully
247define how it is interpreted.
248
249===== make-linear-sequence
250
251<procedure>(make-linear-sequence MAKE ELT NEXT)</procedure>
252
253Returns an object representing a sequence that only allows sequential
254"on-at-a-time" access to its elements. {{MAKE}} should be a procedure
255of two arguments, a size count and an initial value and should return
256a collection of elements which will be stored as "state" in the
257sequence object.  {{ELT}} should be a procedure of one argument
258receiving the "state" and should return the element inside the
259collection that is represented by the currently stored state. {{NEXT}}
260should be a procedure that receives the current state and returns a
261new state representing the underlying collection that will make
262the next element accessible via {{ELT}}. If the collection has
263run out of elements, {{NEXT}} should return {{#f}}.
264
265===== make
266
267<procedure>(make S LENGTH INIT)</procedure>
268
269Creates a sequence of the same type as {{S}} with {{LENGTH}}
270elements that have the initial value {{INIT}}.
271
272===== sequence
273
274<procedure>(sequence S X1 ...)</procedure>
275
276Creates a sequence of the same type as {{S}} with {{X1, ...}} as
277its initial elements.
278
279==== Iterators
280
281===== iterator?
282
283<procedure>(iterator? X)</procedure>
284
285Returns {{#t}} if {{X}} is an iterator object or {{#f}} otherwise.
286
287===== linear-iterator?
288
289<procedure>(linear-iterator? X)</procedure>
290
291Returns {{#t}} if {{X}} is an iterator on a linear sequence or {{#f}} otherwise.
292
293===== random-access-iterator?
294
295<procedure>(random-access-iterator? X)</procedure>
296
297Returns {{#t}} if {{X}} is an iterator on a random-access sewuence or {{#f}} otherwise.
298
299===== iterator
300
301<procedure>(iterator S [INDEX])</procedure>
302
303Returns an iterator object over sequence {{S}}, optionally starting at
304osition {{INDEX}} (an exact integer).
305
306===== at-end?
307
308<procedure>(at-end? ITERATOR)</procedure>
309
310Returns {{#t}} if {{ITERATOR}} points past the lat element of its
311associated sequence or {{#f}} otherwise.
312
313===== advance
314===== advance!
315
316<procedure>(advance ITERATOR [STEPS])</procedure>
317<procedure>(advance! ITERATOR [STEPS])</procedure>
318
319Returns a new iterator (or modifies the given iterator in case of
320{{advance!}}) pointing to the next element of the associated sequence
321or to the element at the position I + {{STEPS}}, where I is the
322current index of {{ITERATOR}}.
323
324===== index
325
326<procedure>(index ITERATOR)</procedure>
327
328Returns the exact integer index of the position to which {{ITERATOR}}
329points to.
330
331==== Iteration constructs
332
333===== for
334===== for*
335
336<procedure>(for PROC S)</procedure>
337<procedure>(for* PROC S)</procedure>
338
339Invokes {{PROC}} for each element in sequence and returns an undefined
340result. {{for*}} operates as {{for}} but invokes {{PROC}} with the
341sequence {{S}} and an iterator pointing to the current element.
342
343===== smap
344===== smap*
345
346<procedure>(smap S1 PROC S2)</procedure>
347<procedure>(smap S1 PROC S2)</procedure>
348
349Applies {{PROC}} to each element in the sequence {{S2}} and returns
350a new sequence of the same type as {{S1}} constructed of the results
351returned by {{PROC}}.
352
353==== Other operations
354
355===== coerce
356
357<procedure>(coerce S1 S2)</procedure>
358
359Returns a new sequence of the same type as {{S1}} containing
360the elements of {{S2}}.
361
362===== copy
363
364<procedure>(copy S)</procedure>
365
366Returns a copy of the sequence {{S}}.
367
368===== is?
369
370<procedure>(is? X)</procedure>
371
372Returns a single-argument procedure that returns {{#t}} if
373the argument is {{equal?}} to {{X}} or {{#f}} otherwise.
374
375
376==== SRFI-42 comprehensions
377
378(This code was kindly contributed by Thomas Chust)
379
380SRFI-42 comprehensions for sequences are provided using the {{:seq}}
381generator, here an example:
382
383  (string-ec (:seq x "aAbBcC") (if (char-lower-case? x)) x)  ==>  "abc"
384
385This is mostly useful with user-defined sequences created by
386{{make-linear-sequence}} and {{make-random-access-sequence}}.
387
388To use this feature, execute
389
390  (require-extension sequence-comprehensions)
391
392
393=== Author
394
395[[/users/felix winkelmann|felix]]
396
397=== Repository
398
399This egg is hosted on the CHICKEN Subversion repository:
400
401[[https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/sequences|https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/sequences]]
402
403If you want to check out the source code repository of this egg and
404you are not familiar with Subversion, see [[/egg-svn-checkout|this page]].
405
406=== License
407
408 Copyright (c) 2010-2011, Felix L. Winkelmann and Thomas Chust
409 All rights reserved.
410 
411 Redistribution and use in source and binary forms, with or without
412 modification, are permitted provided that the following conditions
413 are met:
414 1. Redistributions of source code must retain the above copyright
415    notice, this list of conditions and the following disclaimer.
416 2. Redistributions in binary form must reproduce the above copyright
417    notice, this list of conditions and the following disclaimer in the
418    documentation and/or other materials provided with the distribution.
419 3. The name of the authors may not be used to endorse or promote products
420    derived from this software without specific prior written permission.
421 
422 THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
423 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
424 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
425 IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
426 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
427 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
428 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
429 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
430 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
431 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
432
433=== Version History
434
435; 0.5.1 : Fix segfault when calling certain procedures with non-fixnum as indices and step sizes (fixes #1631)
436; 0.5 : ported to CHICKEN 5
437; 0.4 : removed {{replicate}}, renamed {{contains?}} to {{thereis?}}, performance tuning
438; 0.3 : added {{replicate}}, various bugfixes
439; 0.2 : added set-operations and some more
440; 0.1 : initial release
441
Note: See TracBrowser for help on using the repository browser.